church-encoding.py

#type: ignore
from math import pi

# Original haskell code from: https://www.haskellforall.com/2021/01/the-visitor-pattern-is-essentially-same.html

# -- | This plays the same role as the old `Shape` type
# type Shape = forall shape
#     .  (Double -> Double -> Double -> shape)
#     -> (Double -> Double -> Double -> Double -> shape)
#     -> shape

# -- | This plays the same role as the old `Circle` constructor
# _Circle :: Double -> Double -> Double -> Shape
# _Circle x y r = \_Circle _Rectangle -> _Circle x y r
def Circle(x, y, r):
    return lambda circle, rectangle: circle(x, y, r)

# -- | This plays the same role as the old `Rectangle` constructor
# _Rectangle :: Double -> Double -> Double -> Double -> Shape
# _Rectangle x y w h = \_Circle _Rectangle -> _Rectangle x y w h
def Rectangle(x, y, w, h):
    return lambda circle, rectangle: rectangle(x, y, w, h)

# exampleCircle :: Shape
# exampleCircle = _Circle 2.0 1.4 4.5
example_circle = Circle(2.0, 1.4, 4.5)

# exampleRectangle :: Shape
# exampleRectangle = _Rectangle 1.3 3.1 10.3 7.7 
example_rectangle = Rectangle(1.3, 3.1, 10.3, 7.7)

# area :: Shape -> Double
# area shape = shape
#     (\x y r   -> pi * r ^ 2)
#     (\x y w h -> w * h)
def area(shape):
    return shape(
        circle=lambda x, y, r: pi * r**2,
        rectangle=lambda x, y, w, h: w * h
    )

# main :: IO ()
# main = do
#     print (area exampleCircle)
#     print (area exampleRectangle)
print(area(example_circle))
print(area(example_rectangle))

#### Recursive algebraic type, with recursion removal

# type Tree = forall tree
#     .  (Int -> tree -> tree -> tree)  -- Node :: Int -> Tree -> Tree -> Tree
#     -> tree                           -- Leaf :: Tree
#     -> tree

# _Node :: Int -> Tree -> Tree -> Tree
# _Node value left right =
#     \_Node _Leaf -> _Node value (left _Node _Leaf) (right _Node _Leaf)
def Node(value, left, right):
    return lambda node, leaf: node(value, left(node, leaf), right(node, leaf))

# _Leaf :: Tree
# _Leaf = \_Node _Leaf -> _Leaf
def Leaf():
    return lambda node, leaf: leaf()

# exampleTree :: Tree
# exampleTree = _Node 1 (_Node 2 _Leaf _Leaf) (_Node 3 _Leaf _Leaf)
example_tree = Node(1, Node(2, Leaf(), Leaf()), Node(3, Leaf(), Leaf()))

# preorder :: Tree -> [Int]
# preorder tree = tree
#     (\value left right -> value : left ++ right)
#     []
def preorder(tree):
    return tree(
        node=lambda value, left, right: [value, *left, *right],
        leaf=lambda : []
    )

# main :: IO ()
# main = print (preorder exampleTree)
print(preorder(example_tree))

#### Recursive algebraic type, without recursion removal (not in the article)
def Node(value, left, right):
    return lambda node, leaf: node(value, left, right)

# Leaf stays the same

example_tree = Node(1, Node(2, Leaf(), Leaf()), Node(3, Leaf(), Leaf()))

def preorder(tree):
    return tree(
        node=lambda value, left, right: [value, *preorder(left), *preorder(right)],
        leaf=lambda : []
    )
print(preorder(example_tree))