Implementation of Foldable in Haskell

Question

For example, I have some data type. Let it be a binary tree:

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

For example, I implemented traversal of the tree:

treeFoldt :: Tree t -> [t]
treeFoldt = foldt1 (:) []

It works pretty good. But I want to implement Foldable interface.

I think, that I should write something like that:

instance Foldable Tree where
  foldr = treeFoldt

But it does not work. How can I fix this?

Answer 1

I could try to tell you where the problem with your code is but sadly you did not give the definition for foldt1

But this should work (if your implementation of treeFoldt is ok - remember: [] is an instance of Foldable):

instance Foldable Tree where
  foldr f s = Data.Foldable.foldr f s . treeFoldt

---

basic definition using Monoid

Anyway, I think the easiest way in this case is to implement just the foldMap part:

import Data.Foldable
import Data.Monoid

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

instance Foldable Tree where
 foldMap f (Leaf a)     = f a
 foldMap f (Branch l r) = foldMap f l `mappend` foldMap f r 

and this surely works.

Examples / Usage

λ> let t = Branch (Branch (Leaf $ Sum 2) (Leaf $ Sum 4)) (Leaf $ Sum 6)
λ> fold t
Sum {getSum = 12}

or

λ> let t = Branch (Branch (Leaf 2) (Leaf 4)) (Leaf 6)
λ> foldMap Sum t
Sum {getSum = 12}

and of course you don't need the Monoid part at all - the default implementations work just fine:

λ> Data.Foldable.foldr1 (+) t
12

by the way: it's most likely not obvious how foldr1 (+) can be expressed just in terms of foldMap and it's a nice (advanced) exercise to try to do it on your own :D

---

external resources

I think Foldable and Traversable by A. Arnold is quite a nice blog post on Foldable (and Traversable) in general - maybe you find it helpful too