Creating polymorphic recursive types in Haskell

Question

Hi

I'm trying to create a Tree type in Haskell. I've used this simple data constructor for storing a tree in which each node can either be empty, be a leaf containing an integer, or be a node containing an integer with branches to two other leaves/nodes. Here's what I've got:

module Tree ( Tree(Empty, Leaf, Node) ) where

data Tree = Empty
| Leaf Int
| Node Tree Int Tree
deriving(Eq, Ord, Show, Read)

That works fine, but I need to make the Tree type polymorphic. I've tried simply replacing 'Int' with 'a' but it doesn't seem to work. Is there another system for making these types polymorphic?

Answer 1

data Tree a = Empty
           | Leaf a
           | Node (Tree a) a (Tree a)

Answer 2

Replacing Int with a is the right start, but you also need to replace each occurrence of Tree with Tree a (parenthesizing it where necessary). The data Tree part needs the a to declare that Tree has one type argument called a. The Node Tree Int Tree needs to signify that the subtrees are themselves of type Tree a and not some other treetype.

Answer 3

Indeed, you can give the Tree a type parameter, as in Alexander Poluektov's example. Simple enough! But why stop there? We can have a bit more fun than just that. Instead of just a recursive structure with polymorphic data, you can make the structure polymorphic in the recursion itself!

First, abstract away the tree's references to itself, in the same fashion as abstracting away the references to Int, replacing the recursive references with a new parameter t. That leaves us with this rather vague data structure:

data TNode t a = Empty
               | Leaf a
               | Node (t a) a (t a)
               deriving (Eq, Ord, Show, Read)

This has been renamed as TNode here because it isn't really a tree anymore; just a simple data type. Now, to recover the original recursion and create a tree, we twist TNode around and feed it to itself:

newtype Tree a = Tree (TNode Tree a) deriving (Eq, Ord, Show, Read)

Now we can use this Tree recursively, though sadly at the cost of some extra verbiage, like so:

Tree (Node (Tree Empty) 5 (Tree (Leaf 2)))

So what does this give us, besides extra typing, you ask? Simply that we've separated the fundamental tree structure from both the data it contains and the method by which the data is constructed and processed, allowing us to write more generic functions to deal with one aspect or another.

For instance, we can decorate trees with extra data, or splice extra stuff into the tree, without impacting any generic tree functions. Say we wanted to give a name to each piece of the tree:

newtype NameTree a = NameTree (String, TNode NameTree a) deriving (Eq, Ord, Show, Read)

On the other hand, we can write generic tree traversal logic:

toList f t = toList' f (f t) []
    where toList' f (Node t1 x t2) xs = toList' f (f t1) (x : toList' f (f t2) xs)
          toList' f (Leaf x) xs = x:xs
          toList' _ Empty xs = xs

Given a function to extract the current TNode from a recursive tree, we can use this on any such structure:

treeToList = toList (\(Tree t) -> t)
nameTreeToList = toList (\(NameTree (_, t)) -> t)

Of course, this probably goes far beyond what you're looking to do, but it's a nice taste of just how much polymorphism and generic code Haskell allows (nay, encourages) a programmer to create.

Answer 4

Try reading a bit about type constructor kind.

If you have a polymorphic type depending on some type variables, then your type constructor must have a kind that reflects that.

For example, the type constructor MyBool defined in:

data MyBool = False | True

is of kind *. That is, my type constructor MyBool take no parameters to define a type. If I write something like:

data MyMaybe a = Just a | Nothing

then the type constructor MyMaybe have kind *->*, that is, it needs a "type argument" to define a type.

You can compare how type constructor kinds works with how data constructor type works.

The data constructor True can be a data value of type MyBool on it's own, without any parameter. But the data constructor Just is a value of type a -> MyMaybe a, it will operate over a value of type a to create another value of type MyMaybe a - like for example in this ghci session:

> let x = Just 5
> :t x
Maybe Int
> let y = Just
> :t y
a -> Maybe a

This is more or less comparable with the difference between the type constructors MyMaybe and MyBool. Given that MyBool have kind *, you can have values with type MyBool, without any additional type parameter. But MyMaybe is not a type on its own - it's a type constructor that "operates" on a type to create another type, that is, its kind is * -> *. And so, you can't have things of type MyMaybe, but things of type MyMaybe Int, MyMaybe Bool, MyMaybe [Int], etc...

If a type is polymorphic, it needs to be at least of kind * -> *, but it could be *->*->*, like in:

 data MyPair a b = Pair a b

MyPair needs two type parameters to define a type, like in MyPair Int Bool, MyPair Int Int, etc...

The take home message is something like: as value constructors have type signatures, type constructors have kind signatures, and this must be taken into account when you are planning a new data type.

http://en.wikipedia.org/wiki/Kind_%28type_theory%29