How can I build a recursive tree with concrete data types in Haskell?

Question

I'd like to build a tree in Haskell where each node has a concrete data type. Ultimately I want to build and use my own, more complicated types, but I can't quite figure out how to get the toy example below to work.

I'd like to create a tree of Integers, starting with a large value at the trunk, getting smaller as you traverse down to the leaves.

data Tree x = Empty | Node x (Tree x) (Tree x) deriving (Show, Read, Eq) 

copyBox :: Int -> Tree x
copyBox x
    | x <= 0 = Node x Empty Empty
    | x > 0  = Node x (copyBox (x-1)) (copyBox (x-1))

I would expect to be able to build a small tree like this:

let newtree = copyBox 3

ghci throws an error "Couldn't match expected type 'x' with actual type 'Int'" at line 5.

If I replace the function declaration above with the more general version below, there is no problem:

copyBox :: (Ord x, Num x) => x -> Tree x

Why isn't the type of x just "Int" in both cases?

amalloy amalloy · Accepted Answer · 2014-11-11T00:43:53

copyBox :: Int -> Tree x promises to return a Tree of any type at all, at the caller's whim. So I can write copyBox 5 :: Tree String, which is a legal call based on your type signature. But of course this will fail: you're putting x in the Nodes; and you're trying to subtract 1 from it, which only works if it's a numeric type; and you're comparing it to 0, which only works if it's an ordered type...

You probably just intend copyBox :: Int -> Tree Int, since you are clearly only building a Tree with Int values in it.

How can I build a recursive tree with concrete data types in Haskell?

1 Answers