Haskell Tree foldt on Tree with variable members

Question

I'm trying to create a custom data type Tree. The definition is below:

A tree can be defined as either a leaf (identified by the keyword "Leaf") containing a single piece of information (i.e. it is a node with no child), or a node (identified by the keyword "Node") with a single piece of the information, plus a list of trees – each element in the list represent a subtree rooted at the corresponding child. Note that under this definition, a tree can never be empty. That means a tree can either be:

Leaf data; or

Node data [data, data, …] -- there can be zero or more tree inside the list

This is my code:

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

foldt :: (a -> a -> a) -> Tree a -> a
foldt f (Leaf a)     = a
foldt f (Node a [])  = a
foldt f (Node a [b]) = f a (foldt f b)

It compiles, but when I try to run:

let myTree = Node 'A' [Node 'B' [Leaf 'E', Node 'F' [Leaf 'I', Leaf 'J', Leaf 'K']], Node 'C' [Leaf 'G', Leaf 'H'], Leaf 'D']
foldt min myTree

Instead of the expected output 'A', I get the below error:

CSC207a4.hs:(6,1)-(8,38): Non-exhaustive patterns in function foldt

What part of my function is non-exhaustive, or have I defined the data type incorrectly?

Update:

I may have solved the non-exhaustive pattern, I now have this, but it claims Tree is not defined:

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

foldt :: (a -> a -> a) -> Tree a -> a
foldt f (Leaf a)     = a
foldt f (Node a [])  = a
foldt f (Node a [(Tree x)])  = f a (foldt f x)
foldt f (Node a [(Tree x):xs]) = f a (foldt f (f x (foldt f xs)))

You've only accounted for when the [Tree a] is 0 elements or 1 element. What if I had Node 1 [Leaf 2, Leaf 3]? — bheklilr
I think I found a fix for that, but now it claims that Tree does not exist when I try to use it. — Himself12794
Leaf and Node are not actually keywords—they're data constructors. — dfeuer
A keyword is something like let, if, then, etc., that is built into the language syntax. Data constructors are how you build up values in Haskell out of smaller pieces. Pattern matching on data constructors is then how you take the smaller pieces out of the values. — dfeuer

dfeuer dfeuer · Accepted Answer · 2015-03-18T03:54:47

You can get some help from GHC by turning on warnings. The "big hammer" is -Wall:

-- At the very top of the file
{-# OPTIONS_GHC -Wall #-}

A less noisy approach will work too:

{-# OPTIONS_GHC -fwarn-incomplete-patterns #-}

Either of these will give you an explicit list of the patterns you failed to match, at compile time.

The reason putting Tree in your pattern won't work is that Tree is a type constructor (the sort you make by putting them on the left hand sides of data or newtype declarations). Only data constructors (the sort you make by putting them on the right hand sides of data or newtype declarations) can be matched in patterns.

Haskell Tree foldt on Tree with variable members

2 Answers