Swift visitor design pattern

2

Swift visitor design pattern swift theswiftdev.com
via napkindrawing 1 year ago | archive
Archive.org Archive.today Ghostarchive
| 1 comment

1

4
Axman6 edited 1 year ago | link
When learning functional programming, and the day you learn what a catamorphism is, is an enlightening day. There’s a lot of boilerplate here for what is essentially the definition of a sum type, and a function which takes one argument corresponding to each constructor. In Haskell, the first few catamorphisms people are generally introduced to are:
```
bool :: a -> a -> Bool -> a
bool f t b = case b of
    False -> f
    True  -> t

maybe :: b -> (a -> b) -> Maybe a -> b
maybe nothing just maybeA = case maybeA of
    Nothing -> nothing
    Just a -> just a

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr cons nil list = case list of
    []     -> nil
    x : xs -> cons a (foldr cons nil XS)
```
and it turns out that these functions are universal; any function you can write on each of these types (Bool, Maybe, list) can be written using these functions. The pattern is simple: for each constructor in your type, your catamorphism will take an argument which is is a function that accepts values of the types each constructor contains - and anywhere there’s a recursive reference to the same type, you accept a value of the result type.

For example, we can define a binary tree with b’s at the nodes and a’s in the leaves:
```
data BinTree b a = Leaf a | Node b (BinTree b a) (BinTree b a)
```
and the catamorphism would be
```
foldTree :: (a -> r) -> (b -> r -> r -> r) -> BinTree b a -> r
foldTree leaf node  tree = case tree of
    Leaf a -> leaf a
    Node b l r -> node  b (foldTree leaf node l) (foldTree leaf node r)
```
which we can use to do things like count all the nodes and leaves:
```
countStructure = foldTree 
    (\_a -> (1,0))
    (\b (leavesLeft,nodesLeft) (leavesRight,nodesRight) 
        -> (leavesLeft + leavesRight, 1 + nodesLeft + nodesRight))
```
it should be pretty easy to see you can then do things like collect all leaves and nodes, calculate the depth using max instead of plus, or even map from one type to another by making r also be a tree:
```
mapBoth :: (a -> c) -> (b -> d) -> BinTree b a -> BinTree b c
mapBoth aToC bToD = foldTree
    (\a -> aToC a)
    (\b l r -> Node (bToD b) l r)
```
Generally you can identify that you have a catamorphism when you can provide it with the structure’s constructors and end up creating the identity function:
```
treeIdentity :: BinTree b a -> BinTree b a
treeIdentity = foldTree Leaf Node

             = \tree -> case tree of
                 Leaf a     -> Leaf a
                 Node b l r -> Node b (treeIdentity Leaf Node l) 
                                      (treeIdentity Leaf Node l)
           
            = id -- assuming that 
                 -- (treeIdentity Leaf Node l) == l, and 
                 -- (treeIdentity Leaf Node l) == r
```
If you’ve made it this far, and want some Haskell exercises, try implementing:
Inverting the binary tree, so all the branches are flipped (easy)

Collecting a list of all values in the Leaves (easy)

collecting a list of all b values in the Nodes in a) preorder, b) in order and c) post order. (moderate-hard)

Labeling each leaf with its order from left to right: label :: BinTree b a -> BinTree b (Int,a) (hard)

define a catamorphism on the following type (hard):
```
data BinTree b a = 
    = Leaf a 
    | Node b (BinTree a b) (BinTree a b) -- Note: the recursive type is not the same, 
                                         --the a's and b's have been swapped!
```