Datatypes and Folds: Part II

Non-mutually recursive and Mutually recursive datatypes

Welcome back. In this post we will look at creating type algebra's and folds for more complicated data types. In essence, this exercise will not be any more difficult than the previous ones, provided that you stick with the steps. Up in this part, are the non-mutually recursive datatypes and mutually recursive datatypes.

First up, data struc­tures that are re­curs­ive into other data struc­tures. The folds for these data struc­tures are no more com­plex than their `simpler’ forms. In fact, you could treat them the same, but for clar­ity we will treat them as dis­tinct. If you want to know more about the pre­vi­ous part, it might help your search if you look for the keyword cata­morph­ism.

Non-mutually recursive datastructures

Look at the following data structure. It's data constructors refer both back to the data structure itself and to another data structure. The other data structure has no reference back to this structure. This kind of data structures are quite common.

[haskell] data MaybeTree a = Node (Maybe a) (MaybeTree a) (MaybeTree a) | Leaf (Maybe a) – This one is already defined in the pre­lude data Maybe a = Just a | Noth­ing [/haskell]

Re­call that in our pre­vi­ous folds and al­geb­ras we choose to re­place our self-recursive types with a free vari­able r. In this case we also have a ref­er­ence to an­other data struc­ture, namely Maybe a. We will de­note this by us­ing an­other free vari­able, lets say m.

[haskell] type MaybeTreeAlgebra a m r = ( ( m -> r -> r -> r – Node , m -> r – Leaf ) , ( a -> m – Just , m – Noth­ing )
) [/haskell]

No­tice that we’ve split up the the func­tions for each data type in sep­ar­ate tuples. This is to make the al­gebra some­what more read­able. It has one dis­ad­vant­age though which we’ll see later on.

We ob­tained this al­gebra by meth­od­ic­ally look­ing at the types of the con­structor func­tions and re­pla­cing any re­curs­ive types by their free vari­able coun­ter­parts, r for MaybeTree a and m for Maybe a.

Now we are go­ing to con­struct the fold func­tion. We will be do­ing this in ex­actly the same way as we did with all pre­vi­ous folds.

1. De­term­ine which data­types are used (pre­vi­ously there was only one); This step is very simple if you already have the al­gebra.
2. for each of these data­types ex­haust­ively define a fold func­tion;
3. look at the res­ult.

Fol­low­ing these steps again gives us the fold on our data­type. Please con­vince your­self that this is the case by de­fin­ing foldMaybeTree your­self.

If we do it ex­actly as de­scribed above it will provide us with the fol­low­ing fold. No­tice that we gave mean­ing­ful names to every re­place­ment func­tion stat­ing the data­type they are in­ten­ded for. Ex­cept for the top level func­tion which we called f. This is be­cause writ­ing out the whole name for that func­tion every­where would be to much of a hassle and if you use f for this way it will be quite clear in time.

[haskell] foldMaybeTree’ :: MaybeTreeAlgebra a m r -> MaybeTree a -> r foldMaybeTree’ ((node, leaf), (just, noth­ing)) = f where f (Node x l r) = node (maybe x) (f l) (f r) f (Leaf x) = leaf (maybe x) maybe (Just x) = just x maybe (Noth­ing) = noth­ing [/haskell]

No­tice that we are us­ing a data­type here that is already defined in the pre­lude. It would be wise to check whether someone didn’t already provide a fold func­tion for our little data­type Maybe a. Be­cause that’s we es­sen­tially did, we in­lined the fold for Maybe a in­side our fold for MaybeTree a. Ob­vi­ously this isn’t a prob­lem if you are sure that your data­type will stay `con­tained in’ in your data­type.

So we see that it is prudent to check for already ex­ist­ing folds if we use already ex­ist­ing data­types. And it turns out that there already is a fold for Maybe a, namely maybe.

[haskell] maybe :: b -> (a -> b) -> Maybe a -> b maybe n _ Noth­ing = n maybe _ f (Just x) = f x [/haskell]

So lets re­fine our little pro­ced­ure to de­term­ine the fold of a data­type:

1. De­term­ine which data­types are used (pre­vi­ously there was only one); This step is very simple if you already have the al­gebra.
2. for each of these data­types ex­haust­ively define a fold func­tion or check whether such a fold func­tion already ex­ists;
3. look at the res­ult.

If we now use this know­ledge our fold func­tion can be writ­ten as fol­lows:

[haskell] foldMaybeTree :: MaybeTreeAlgebra a m r -> MaybeTree a -> r foldMaybeTree ((node, leaf), (just, noth­ing)) = f where f (Node x l r) = node (fmaybe x) (f l) (f r) f (Leaf x) = leaf (fmaybe x) fmaybe = maybe noth­ing just [/haskell]

We’ve seen how to use algebra’s but we haven’t seen a step by step pro­ced­ure for cre­at­ing one. So let’s add that to our pro­ced­ure for cre­at­ing our own folds. In our or­der to cre­ate the al­geb­ras as we’ve seen them here, with tupled func­tions you can fol­low this pro­ced­ure:

For each data con­structor in your data­type: cre­ate a func­tion that takes the same para­met­ers as the con­structor func­tion and re­place every oc­cur­rence of a ref­er­ence to one of your data­types with a unique type vari­able (two oc­cur­rences to the same type should get the same vari­able). These func­tions should be grouped in tuples by their data­type. Do not for­get to name all the type vari­ables in the left-hand side of the type defin­i­tion.