CODEWITHSUNDEEP
haskell
Seba
Seba

Reputation: 61

Haskell fold function on tree

I'm struggling with this example:

Write a fold function that folds a function over a tree. (Thus, for example, fold min t would find the smallest element in tree.)

fold :: (a -> a -> a) -> Tree -> a

*That's my script 

data Tree = Leaf Int
          | Fork Tree Int Tree
     deriving Show


t0 = Leaf 0
t1 = Fork (Fork (Leaf 1) 2 (Leaf 3)) 4 (Fork (Leaf 5) 6 (Leaf 7))
t2 = Fork (Fork (Fork (Leaf 1) 2 (Leaf 3)) 4 (Leaf 5)) 6 (Leaf 7)

fold :: (a -> a -> a) -> Tree -> a
fold f v (Leaf n) = v
fold f v (Fork l n r) = f (Folk l) (fold f v (Fork r))

Thanks for any advice

Upvotes: 1

Views: 3244

Answers (2)

ephrion
ephrion

Reputation: 2697

Folds can be somewhat mechanically derived from any type. Here's foldMaybe:

data Maybe a = Nothing | Just a

foldMaybe :: r -> (a -> r) -> Maybe a -> r
foldMaybe _ k (Just a) = k a
foldMaybe d _ Nothing  = d

To "fold" a data type means that we are going to provide a way of combining each of the possible constructors for that type into a final type r. Here, Maybe has two constructors: one with 0 values, and one with a single value of type a. So, to fold it, we need to provide a value for the Nothing case, and a function to convert the Just a into an r.

Let's look at list, and see how foldr is derived from it.

data List a = Nil | Cons a (List a)

           [1]   [2    3    4]             [4]
foldList :: r -> (a -> r -> r) -> List a -> r
  1. This is the value to use when replacing the Nil in the list.
  2. This is the function to use for combining the Cons case. Since Cons has an a as it's first value, the function must take an a.
  3. The second value that Cons takes is a (List a), so why are we taking an r? Well! We're defining a function that can take a List a and return an r, so we'll process the rest of the list before combining with the current node.
  4. The fold function returns r.

What does the implementation look like?

foldList nil cons list = case list of
    Nil -> nil
    Cons a as -> cons a (foldList nil cons list)

So we replace all of the constructors with their "destructor" counterparts, recursing where necessary.

For trees:

data Tree = Leaf Int | Fork Tree Int Tree

We have two constructors: one takes an Int, and the other takes three parameters Tree, Int, and Tree.

Let us write the type signature!

treeFold :: LeafCase r -> ForkCase r -> r

Ah, but we have to define LeafCase:

type LeafCase r = Int -> r

Since Leaf takes a single Int as parameter, that's what the type of this function must be.

type ForkCase r = r -> Int -> r -> r

Likewise, we replace all the recursive uses of Tree in Fork with the r type parameter. So our full function looks like:

foldTree :: (Int -> r) -> (r -> Int -> r -> r) -> Tree -> r

The implementation might start like:

foldTree leaf fork tree = case tree of
    Leaf i -> error "halp"
    Fork l i r -> error "complete me?"

and I feel confident that you can fill in those holes :)

Upvotes: 4

David Lilue
David Lilue

Reputation: 631

One thing, in the signature of your function fold, you're saying that it'll receive 2 arguments, a binary function (could be an operator), a Tree and returns an a. Now, in the defintion you have 3 arguments, f, some v and a constructor of Tree.

The solution could be this one:

fold :: (Int -> Int -> Int) -> Tree -> Int
fold f (Leaf n) = n
fold f (Fork l n r) = f n m
    where
        m = f (fold f l) (fold f r)

You need to say that you are returning a Int because your Tree holds Int.

EDIT

Furthermore, you can redefine your data with a rigid type variable. 

data Tree a = Leaf a
            | Fork (Tree a) a (Tree a)
     deriving Show


fold :: (a -> a -> a) -> Tree a -> a
fold f (Leaf n) = n
fold f (Fork l n r) = f n m
    where
        m = f (fold f l) (fold f r)

I suggest you to read the documentation of Data.Foldable. They have an example with a Tree data type.

Upvotes: 4

Related Questions