CODEWITHSUNDEEP
haskelltree
Marcel
Marcel

Reputation: 35

Recursive Tree passing additional integer

I need this for my homework, I'm pretty much done with my solution but I have one last subproblem left that I can't figure out how to solve..

type Notes = [(Int,Int,Int,Int)]
data Tree = Leaf Notes | Node Notes [Tree]]
    deriving(Eq,Show)

identity :: Tree -> Tree
identity (Leaf mi   ) = Leaf (transformNote mi 2)
identity (Node mi xs) = Node (transformNote mi 2) (map identity xs)

So what I'm trying to achieve with this function is: take a tree, map the tree to itself but change the argument mi to (transformNote mi 2).

This code works and executes everything as expected, but what I actually need is a function 

identity :: Tree -> Int -> Tree

so that my function turns into something like this:

identity :: Tree -> Int -> Tree
identity (Leaf mi   ) amount = Leaf (transformNote mi amount)
identity (Node mi xs) amount = Node (transformNote mi amount) (map identity xs amount)

This won't work since 

(map identity xs amount) throws errors.

I tried so many ways to fix this, throw the amount variable around the terms but nothing seems to work. I can't make sense of why none of my solutions work.

Can anyone help? Thx

Upvotes: 1

Views: 52

Answers (2)

user2297560
user2297560

Reputation: 2983

This is actually easier if you generalize. Make Tree parameterized so that it's an instance of Functor:

data Tree a = Leaf a | Node a [Tree a] deriving (Eq,Show)

instance Functor Tree where
  fmap f (Leaf x) = Leaf (f x)
  fmap f (Node x xs) = Node (f x) (fmap (fmap f) xs)

Now you can transform the elements of a Tree however you see fit:

identity :: Tree Notes -> Int -> Tree Notes
identity t amount = fmap (\n -> transformNote n amount) t

By the way, identity is a bad name for a function since by mathematical (and Haskell) convention, the identity function is

id :: a -> a
id x = x

That is, the function that simply returns its argument.

Upvotes: 2

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476649

Well all subtrees s, need to be replaced with an identity s amount. That means we can write a lambda expression \s -> identity s amount that thus will convert a single subtree. We can then use that expression in a map:

identity :: Tree -> Int -> Tree
identity (Leaf mi   ) amount = Leaf (transformNote mi amount)
identity (Node mi xs) amount = Node nmi (map (\s -> identity s amount) xs)
    where nmi = transformNote mi amount

The where clause is here used only to make the code fit on the available page width.

But this is rather ugly. We can use flip :: (a -> b -> c) -> b -> a -> c that flips the two arguments. In that case, we can write it as:

identity :: Tree -> Int -> Tree
identity (Leaf mi   ) amount = Leaf (transformNote mi amount)
identity (Node mi xs) amount = Node nmi (map (flip identity amount) xs)
    where nmi = transformNote mi amount

Because it frequently introduces ugly expression, this is one of the reasons why in Haskell usually the parameters themselves are flipped:

-- flipped version
identity2 :: Int -> Tree -> Tree
identity2 amount (Leaf mi   ) = Leaf (transformNote mi amount)
identity2 amount (Node mi xs) = Node nmi (map (identity2 amount) xs)
    where nmi = transformNote mi amount

Upvotes: 1

Related Questions