CODEWITHSUNDEEP
haskelltypesmutual-recursion
147pm
147pm

Reputation: 2239

Clarification of Haskell mutual recursion

I've come across these discussions of mutual recursion, initially in the context of the let expression, i.e., a let allows for bindings to refer to one another with no mind for order. (See here.) I then saw this discussion in Wikipedia. This gives an example in the form of a data type in SML

datatype 'a tree = Empty | Node of 'a * 'a forest
and      'a forest = Nil | Cons of 'a tree * 'a forest

As I recall, the and is necessary for a mutual recursive relationship. It led to this version in Haskell

data Tree a = Empty
            | Node (a, Forest a)
data Forest a = Nil
              | Cons (Tree a) (Forest a)

I have an intuitive grasp of this, but the syntax is confusion, e.g., the SML tree has

... Node of 'a * 'a forest

This is a tuple, correct? And yes, I think I'm seeing a tuple in the Haskell translation

... Node (a, Forest a)

Intuitively, this is the same as a branch capability where a tree Node may have a whole Forest of (one or many) sub-trees, correct? But then the Haskell Forest data type basically conses a new Tree element to the head of a Forest (of Tree elements) list, and yet the SML version seems to use a *

... Cons of 'a tree * 'a forest

which means create a tuple? In general, the confusing Tree definition, i.e., a Tree can have a Forest underneath it. Then there is this definition of a tree

data Tree = Leaf | Node Int Tree Tree

where the issue of sub-trees is limited to two sub-trees. Is using Forest the only way to allow one-or-many sub-nodes? Intuitively, trees don't have forests under them, rather, they are members of a forest. One question would be, Can there be a direct use of regular list consing?

data Forest a = Nil | ForestCons (Tree a) [(Tree a)] deriving (Show)

Upvotes: 2

Views: 247

Answers (1)

leftaroundabout
leftaroundabout

Reputation: 120711

Node (a, Forest a), despite being perfectly legal Haskell, is unidiomatic. The conventional form of the definition would be

data Tree' a = Empty'
             | Node' a (Forest a)

This contains the same information as your Tree, but instead of packing the fields of the Node constructor in a tuple it just gives them both as fields. The difference is that, when actually dealing with values of the type, you'd write Node' h t instead of Node' (h,t).

Likewise, your Forest is equivalent to the not recommended form

data Forest' a = Nil'
               | Cons' (Tree a, Forest a)

Upvotes: 6

Related Questions