2

I've recently looked up some guides on recursion schemes in Haskell, however most articles don't go much beyond implementing the basic infrastructure required for these concepts.

Given a recursive data type like a binary tree

data Tree a = 
    Leaf a
    | Node a (Tree a) (Tree a)

we would also implement a similar structure which replaces the recursive parts of the definition with a type parameter, in order to be able to use generic folds like cata and ana and so on

data TreeF a r =
    LeafF a
    | NodeF a r r

along with a fix point combinator

newtype Fix f = In { out :: f (Fix f) }

which allows us to express an arbitrarily nested tree with our new representation.

So my question is quite straight forward (and maybe stupid): Which representation of the data structure do we actually use in the rest of our program? Do we need both? Theoretically we could use TreeF only, however from what I found when playing around with an expression grammar tree that was implemented this way, that tends to be a little problematic, mainly since you now have to wrap each level of the tree in the new data constructor and as far as I noticed you can no longer automatically derive from the basic typeclasses like Show or Eq.

string_loginUsername
  • 417
  • 1
  • 4
  • 14
  • You can automatically derive `Show` and `Eq`. It will set the fact that `f` is an instance of `Show` as a condition. – Willem Van Onsem Feb 08 '20 at 22:16
  • 2
    There is a Template Haskell machinery that lets you write only the first type and generate the rest, saving a lot of time. An example is in [this answer at the bottom](https://stackoverflow.com/a/58440463/3234959). – chi Feb 08 '20 at 22:50

0 Answers0