Search code examples
haskellsyntaxtreezipwith

Couldn't match expected type 'MultTree b' with '[MultTree b]'

I'm relatively new to Haskell.

I'm trying to create a function zipWithMult :: (a -> b -> c) -> MultTree a -> MultTree b -> MultTree c that behaves similar to the function zipWith for lists. It should combine the two input trees using the given function of type a -> b -> c.

MultTree represents non-empty trees whose nodes may have arbitrary many children:

data MultTree a = MultNode a [MultTree a] deriving Show

For example, when i have the following two trees:

t1 :: MultTree Integer
t1 = MultNode 8 [MultNode 3 [MultNode (-56) [], MultNode 4 [], MultNode 987 []], MultNode 4 [MultNode 6 []]]

t2 :: MultTree Integer
t2 = MultNode (-2) [MultNode 5 [MultNode 16 [], MultNode 7 []], MultNode (-9) [MultNode 1 [], MultNode 5 []]]

The application of the function zipWithMult (+) t1 t2 should result in:

MultNode 6 [MultNode 8 [MultNode (-40) [], MultNode 11 []], MultNode (-5) [MultNode 7 []]]

Nodes that have no corresponding node in the other tree should be simply dropped.

What i have so far:

zipWithMult :: (a -> b -> c) -> MultTree a -> MultTree b -> MultTree c
zipWithMult f (MultNode x []) (MultNode y ys) = MultNode (f x y) []
zipWithMult f (MultNode x xs) (MultNode y []) = MultNode (f x y) []
zipWithMult f (MultNode x xs) (MultNode y ys) = MultNode (f x y) (zipWithMult f xs ys)

I don't understand why i get this error for my third exression in zipWithMult

Couldn't match expected type `MultTree b'
              with actual type `[MultTree b]'
* In the third argument of `zipWithMult', namely `ys'
  In the second argument of `MultNode', namely
    `(zipWithMult f xs ys)'
  In the expression: MultNode (f x y) (zipWithMult f xs ys)

I feel like i did a mistake with the syntax in Haskell, but i'm not sure.

Solution

  • zipWithMult returns a simple MultTree, so for MultNode (f x y) (zipWithMult f xs ys) we have a problem.

    You can work with zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] to process two lists (the items of the first and second parameter), and return this as a list of MultTrees:

    zipWithMult :: (a -> b -> c) -> MultTree a -> MultTree b -> MultTree c
zipWithMult f (MultNode x xs) (MultNode y ys)
    = MultNode (f x y) (zipWith (zipWithMult f) xs ys)

    For the given sample data, we then obtain:

    Prelude> zipWithMult (+) t1 t2
MultNode 6 [MultNode 8 [MultNode (-40) [],MultNode 11 []],MultNode (-5) [MultNode 7 []]]