Haskell Datatypes and Folds: Part I

Wel­come to this little ex­plan­a­tion on how to de­term­ine the fold of a Haskell data­type. First we’ll look at how we define func­tions over lists, some­thing every­one start­ing with Haskell should be suf­fi­ciently fa­mil­iar with, after which we move on to the data­types. You’ll see dif­fer­ent ways how to cal­cu­late the sum of a list, how to fold over a list, what data­types are and, how to fold over a data­type, spe­cific­ally the BinTree a data­type. Most im­port­antly, I hope you will grow to un­der­stand what a fold is, and why they are so im­port­ant and use­ful when pro­gram­ming Haskell.

Dur­ing our func­tional pro­gram­ming course at Utrecht Uni­ver­sity I no­ticed stu­dents hav­ing anxi­ety of data­types and even more for folds. Not be­cause they couldn’t grasp the work­ings of a single ex­ample but more a lack of a view on the com­plete pic­ture and lack of ex­per­i­ence with the Haskell data­type way.

So, what are data­types? Data­types are a way of not­at­ing the ab­stract struc­ture of your data. There are sev­eral data­struc­tures known to man, such as lists and trees.

Lists

sum :: [Int] -> Int
sum []     = 0
sum (x:xs) = x + sum xs
-- sum [1..4] = 10

Would we be cal­cu­lat­ing the product of the list, we’d do the same ex­cept we mul­tiply in­stead of adding.

product :: [Int] -> Int
product []     = 1
product (x:xs) = x * product xs
-- product [1..4] = 24

Look­ing at these two ex­amples we can see that we have two sim­il­ar­it­ies. We al­ways have re­cur­sion on the tail of the list and we do some­thing with the head of the list and the res­ult of the re­cur­sion. In the first ex­ample we add them to­gether, and in product we mul­tiply them. An­other prop­erty of most func­tions over lists is that there is a base case for the empty list. We call this the iden­tity of our func­tion, some­times also re­ferred to as unit. The iden­tity of ad­di­tion is 0 and the iden­tity of mul­ti­plic­a­tion is 1.

Now we look at one of the folds over lists defined in the pre­lude, foldr. Make sure you know what each para­meter stands for. Note: There are some down­sides to this func­tion, mostly that it will not work for large lists, you’ll see more on this later.

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)
-- The line above can also be written as:
-- foldr f z (x:xs) = x `f` (foldr f z xs)

Now, take a mo­ment to let this func­tion soak in and try to think of how you would define sum and product in terms of this foldr. Cru­cial at this point is to no­tice that we do not see any type hard­coded in the type of foldr It may be help­ful to look at this fold, which is the iden­tity func­tion for lists:

idList :: [a] -> [a]
idList list = foldr (:) [] list
-- Recall: [1,2,3,4,5] == 1 : 2 : 3 : 4 : 5 : []

If we look at our sum func­tion, the op­er­ator between each re­curs­ive call is (+) and our base case is 0. So that’s what we are go­ing to use for our sum in terms of foldr.

sumList :: [Int] -> Int
sumList list = foldr (+) 0 list
-- sumList [1..4] = 10

Thus far we only have lists of Int for our ex­amples. How­ever, for sake of us­ab­il­ity we will now move on to lists of nu­meric ele­ments. Be­cause (+) is defined for all num­bers. (If you wish to read more on this sub­ject please look up classes and in­stances.) No­tice how the type of sumList changes while it’s defin­i­tion re­mains un­altered.

sumList :: Num a => [a] -> a
sumList list = foldr (+) 0 list

Now that we have seen how we can de­term­ine the func­tion and iden­tity for our fold from our re­curs­ive func­tion to a defin­i­tion in terms of foldr. And most im­port­antly, the foldr takes care of the re­curs­ive nature of the list for us and the only thing it asks us in re­turn for that is an op­er­ator and an iden­tity for your op­er­a­tion. So the fold can now be used to define sev­eral op­er­a­tions on lists.

I told you about a prob­lem of foldr. De­pend­ing on the size of your list the above sumList may not work. Try the fol­low­ing on your ma­chine:

$ ghci
Prelude> let sumList = foldr (+) 0
Prelude> sumList [1..1000000]
*** Exception: stack overflow

Now try:

$ ghci
Prelude> let sumList = Data.List.foldl' (+) 0
Prelude> sumList [1..1000000]
500000500000

For a com­plete over­view and ana­lysis on foldr and foldl please read A tu­torial on the uni­ver­sal­ity and ex­press­ive­ness of fold, by Gra­ham Hut­ton.

Trees

Now that you have fa­mil­i­ar­ised your­self with lists we can pro­ceed to a slightly more com­plic­ated data­struc­ture. The Tree. In this ex­ample we will use a simple bin­ary tree. A bin­ary tree can be de­noted as fol­lows:

data BinTree a = Node a (BinTree a) (BinTree a) | Leaf deriving (Show, Eq)

In this case BinTree is the type con­structor and Node and Leaf the data data con­struct­ors.

Re­mem­ber that the goal of folds is to sep­ar­ate the im­ple­ment­a­tion of the re­cur­sion from the ac­tual op­er­a­tion we want to ex­ecute on the data­type. So we have one func­tion, the fold, that takes care of the re­cur­sion and sev­eral other func­tions that use this fold to spe­cify cer­tain se­mantics on the data­type. We are go­ing to cal­cu­late the sum of all ele­ments in this tree.

The above bin­ary tree has ele­ments in the nodes and noth­ing in the leaves. You can no­tice the re­curs­ive oc­cur­rence of ``BinTree a' in the node. We see two constructors in this datatype, NodeandLeaf. The Node constructor expects some value of type aand two subtrees of typeBinTree a, and the Leaf` con­structor has no para­met­ers. In Haskell:

Node :: a -> BinTree a -> BinTree a -> BinTree a
Leaf :: BinTree a

No­tice that our list also has two con­struct­ors, namely the (:) con­structor that adds an ele­ment and the con­structor for the empty list, []. Ana­log­ously we have the Node and Leaf con­struct­ors. If we were al­lowed to use the (:) and [] con­structor in our own Haskell code, the data­type for a list would look like this:

data List a = (:) a (List a) | []

Also, it is cus­tom­ary to keep the ar­gu­ments for the func­tions in the same or­der as the con­struct­ors are defined in the data­type, and to name the iden­ti­fi­ers con­tain­ing the func­tions the same as the con­structor func­tion but in lower­case. Ap­ply­ing this we get:

foldBinTree :: (a -> BinTree a -> BinTree a -> BinTree a) -> (BinTree a) -> BinTree a -> ??
foldBinTree node leaf = f
  where f (Node x left right) = node x (f left) (f right)
        f (Leaf)              = leaf

I left out the res­ult type of this fold, try to find it your­self be­fore con­tinu­ing.

By fol­low­ing our code we can see that every case, the case for Node and the one for Leaf, res­ult in a BinTree a. Con­sequently the com­plete res­ult of the func­tion is a BinTree a

Now re­call that we pre­vi­ously used a fold to cal­cu­late the sum of a list. With that fold we were not re­stric­ted to a list. Which is also clearly vis­ible by look­ing at the type of foldr it con­tains only type vari­ables. As we want to cal­cu­late sum of the ele­ments in this tree, which is some­thing of type a and not of type BinTree a we have to re­vise the type of our fold. No­tice the re­cur­rence of the data­type in it’s de­clar­a­tion, BinTree a. We will re­place all of these oc­cur­rences in the types of our func­tions with a free type vari­able, say r:

foldBinTree :: (a -> r -> r -> r) -> (r) -> BinTree a -> r
foldBinTree node leaf = f
  where f (Node x left right) = node x (f left) (f right)
        f (Leaf)              = leaf

Keep in mind that I used ’eta reduction’ in the above code. This means that the last para­meter (in this case the tree) isn’t ex­pli­citly spe­cified as it would ap­pear at the very end of the para­meter list and ath the very end of the defin­i­tion. (More on eta re­duc­tion.) So, now let’s do some­thing with this fold. Sup­pose we have the fol­low­ing tree:

bintree = Node 1
            (Node 2
              (Node 3 Leaf Leaf)
              (Node 3 Leaf Leaf)
            )
            (Node 2
              (Node 3 Leaf Leaf)
              (Node 3 Leaf Leaf)
            )

A visual rep­res­ent­a­tion:

            1
/  \
2    2
/ \  / \
3   3 3  3

Now we can define sev­eral tra­versals over this tree. Let’s cal­cu­late the sum of all val­ues in the tree.

sumBinTree :: Num a => BinTree a -> a
sumBinTree = foldBinTree (\val res_left res_right -> val + res_left + res_right)
                         0

Algebras

So now we define an al­gebra for our data struc­ture. To do this we again look at each data con­structor and de­term­ine it’s type. The fold func­tion takes care of the re­cur­sion, so ap­ply­ing this thought con­sequently gives us the fol­low­ing types and fold.

Keep in mind that we have to change the type of our fold, but not the defin­i­tion of the fold it­self!

type BinTreeAlgebra a r = (a -> r -> r -> r, -- Node
                           r -- Leaf
                          )

foldBinTree :: BinTreeAlgebra a r -> BinTree a -> r

Now we can again define a sum on all Num a trees. No­tice that we went from to seper­ate para­met­ers for the func­tions to one tuple with two ele­ments.

sumBinTree :: Num a => BinTree a -> a
sumBinTree = foldBinTree (\val res_left res_right -> val + res_left + res_right,
                          0)

$ ghci bintree.hs
*Main> bintree
Node 1 (Node 2 (Node 3 Leaf Leaf) (Node 3 Leaf Leaf)) (Node 2 (Node 3 Leaf Leaf) (Node 3 Leaf Leaf))
*Main> sumBinTree bintree
19

That’s it for now. If you did not un­der­stand everything by the end of this art­icle, don’t panic. It will sink in even­tu­ally. Let this rest a day or two, and then read this art­icle again and you’ll un­der­stand folds bet­ter. :)