CODEWITHSUNDEEP
haskell
user3277633
user3277633

Reputation: 1923

extract each element in a list using list comprehension

I am really new to haskell sorry if this is a relatively easy

I have the following Tree

data Tree a =
    Branch a [Tree a]
  | Finish a
  deriving (Eq, Show)

and I want to write a function foldTree :: ([a] -> a) -> Tree a -> a that replaces all the Finish node in the tree with just the data (a) and all Branch node with a call to f such that f :: ([a] -> a)

Here is my attempt

foldTree :: ([a] -> a) -> Tree a -> a
foldTree f (Finish a) = a
foldTree f (Branch a tree) =  f [foldTree f tree]

Right now in my Branch, the tree in f [ foldTree f tree ] is still a list. How do I extract every element out of tree and apply f to each element?

Upvotes: 2

Views: 320

Answers (1)

leftaroundabout
leftaroundabout

Reputation: 120711

foldTree f (Branch a tree) = ...

here we have the following types:

   f :: [a] -> a
   a :: a
   tree :: [Tree a]

We also have

   foldTree f :: Tree a -> a

which we obviously need to feed the contents of tree somehow, it's the only function that can consume Trees. How? Well, let's call Tree a simply b, then we need something that takes a function b -> a and a [b] list, and gives us something else. Perhaps hoogle knows about such a thing? Turns out it does.

map :: (b -> a) -> [b] -> [a]

i.e. in our case

map :: (Tree a -> a) -> [Tree a] -> [a]

therefore

map (foldTree f) :: [Tree a] -> [a]

and 

map (foldTree f) tree :: [a]

now we're almost done: you could feed this right to f, but wait... we also still have a! Perhaps you want to prepend that first.

foldTree f (Branch a tree) = f $ a : map (foldTree f) tree

Upvotes: 6

Related Questions