Pattern matching on custom constructors Haskell

Question

My Custom type is:

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

I need to write a function

foo :: Eq a => a -> Tree a -> [Tree a]

Example

foo 3 (Node [Leaf 1, Leaf 3, Node [Leaf 5, Leaf 3, Leaf 6], Leaf 4, Leaf 3, Leaf 44, Leaf 3])

-- this should print [Node [leaf 5, leaf 3, leaf 6], leaf 6, leaf 44] i.e - all elements that follow a "Leaf 3" in the Tree

My code is as follows (using pattern matching)

foo n (Leaf _) = []

foo n (Node (Node z):y:xs) = if length (Node z):y:xs < 2 then [] 
                else (foo n (Node z)):(foo n y:xs)

foo n (Node (Leaf z):y:xs) = if length (Leaf z):y:xs < 2 then [] 
                else if Leaf n == Leaf z then [y]:(foo n y:xs)
                else (foo n y:xs)

However I get an error:

• Couldn't match expected type ‘Tree a’ with actual type ‘[Tree a]’

• In the pattern: Node (Node z) : y : xs

But the pattern Node (Node z) : y : xs could represent the input

Node [Node [Leaf 4, Leaf 2], Leaf 6, Leaf 9, Leaf 1]

Am I wrong in saying that? It seems perfect to me.

Why then, is the pattern matching failing?

Node (Node z) is evaluated first, because it is function application, but it can't evaluate, because the first Node is expecting a [Tree] but receiving what appears to be a Tree. Try Node (Node z:y:xs). (Similarly parenthesize _:_:_s in the sequel). — aplainzetakind
I can spot several code smells above, beyond the wrong parentheses. The list (Leaf z):y:xs surely has length >=2, so testing for that looks wrong. The test Leaf n == Leaf z is weird, why not n == z? More in general, using length is often the wrong way: pattern matching already gives us information about the list length. — chi

Paul Parker Paul Parker · Accepted Answer · 2017-12-29T03:08:27

I set up an example on repl.it, but the code is below.

The first thing I did was add a more concrete signature to the function so that it was easier to reason about. Feel free to change it back to your origin signature once you've worked through everything. It's easier to move from the concrete to the abstract, than the other way around.

The first problem was a lack of brackets in the pattern (this meant that instead of Tree a, you were trying to match against [Tree a]. The original (Node (Node z):y:xs) evaluated like this: ((Node (Node z)):y:xs). I added the all@ at pattern below for my own convenience, but you can replace that, it is not essential.
The second problem was that you really were trying to jam a [Tree a] into a Tree a, because that's what y:xs means in foo n y:xs, so I replaced it with Node (y:xs) which is a Tree a.
Third problem was that the pattern matching for foo was non-exhaustive, added a catch-all at the end, you'll want to consider your intended behaviour and clean that up.

The code follows:

module Main where

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

foo :: Int -> Tree Int -> [Tree Int]
foo n (Leaf _) = []

foo n (Node all@((Node z):xs)) = if length all < 2 then [] 
            else (foo n (Node z)) ++ (foo n (Node xs) )

foo n (Node all@((Leaf z):y:xs)) = if length all < 2 then [] 
            else if Leaf n == Leaf z then [y] ++ (foo n (Node (y:xs)))
            else (foo n (Node (y:xs)))
foo _ _ = []

myTree :: Tree Int
myTree = Node [Leaf 1, Leaf 3, Node [Leaf 5, Leaf 3, Leaf 6], Leaf 4, Leaf 3, Leaf 44, Leaf 3]


main :: IO ()
main = do
  print (foo 3 myTree)

Output:

[Node [Leaf 5,Leaf 3,Leaf 6],Leaf 6,Leaf 44]

Pattern matching on custom constructors Haskell

1 Answers