Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 57 ยท Defining types

Recursive Data Types and Trees

Learn how Haskell types can refer to themselves: build lists, binary search trees and expression trees, then evaluate and fold over them.

A type is recursive when one of its constructors holds a value of the same type. That single trick gives you lists of any length, trees of any depth and whole programming languages written as data. Almost every interesting structure in Haskell is recursive, including the built-in list.

Recursive types and recursive functions fit together like a lock and key: the shape of the data tells you the shape of the function. If you have not met constructors yet, read Algebraic Data Types first.

Real Haskell is not installed on this site, so the Haskell blocks are read-only. The runnable examples are JavaScript stand-ins that use tagged objects, and each says what is real Haskell and what is imitation.

A list is a recursive type

The list you use every day could be defined by hand like this:

HASKELL
data MyList a = Nil | Cons a (MyList a)

A MyList a is either empty (Nil) or an element followed by another MyList a. The real list type works the same way, with [] for Nil and : for Cons. So [1, 2, 3] is just 1 : (2 : (3 : [])).

Functions follow the shape. One case per constructor, and the recursive case calls itself on the smaller piece:

HASKELL
myLength :: MyList a -> Int
myLength Nil         = 0
myLength (Cons _ xs) = 1 + myLength xs

This works because every recursive call receives a strictly smaller value, so it eventually reaches Nil. See Recursion for the general pattern.

Binary trees

A binary tree is either empty or a node holding a value and two subtrees:

HASKELL
data Tree a = Leaf | Node (Tree a) a (Tree a)
  deriving (Show)

The type variable a makes it work for any element type. A small tree with 2 at the root looks like this:

HASKELL
example :: Tree Int
example = Node (Node Leaf 1 Leaf) 2 (Node Leaf 3 Leaf)

Two constructors, one tree

Leaf The empty tree. No fields.
Node Left subtree, a value, right subtree.

Node mentions Tree again, so the type is recursive.

1 / 2

Counting nodes, finding the depth and listing the elements in order all follow the same recipe:

HASKELL
size :: Tree a -> Int
size Leaf         = 0
size (Node l _ r) = size l + 1 + size r

depth :: Tree a -> Int
depth Leaf         = 0
depth (Node l _ r) = 1 + max (depth l) (depth r)

toList :: Tree a -> [a]
toList Leaf         = []
toList (Node l x r) = toList l ++ [x] ++ toList r

A binary search tree

If you keep smaller values on the left and larger on the right, you get a binary search tree. Insertion needs Ord so that values can be compared (see Type Classes: Eq, Ord, Show, Read, Num):

HASKELL
insert :: Ord a => a -> Tree a -> Tree a
insert x Leaf = Node Leaf x Leaf
insert x t@(Node l y r)
  | x < y     = Node (insert x l) y r
  | x > y     = Node l y (insert x r)
  | otherwise = t

Nothing is changed in place. insert builds a new tree that shares every untouched subtree with the old one. Only the path from the root to the new position is rebuilt, which is cheap if the tree is reasonably balanced. Keep in mind that this plain tree is not self-balancing: inserting already sorted data produces a long chain. Real programs use Data.Map and Data.Set, which balance themselves (see Essential Libraries).

JS A binary search tree (stand-in)

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The in-order list comes out sorted, the duplicate 5 is ignored, and inserting sorted input gives depth 5, the degenerate chain mentioned above.

Expression trees and an evaluator

Recursive types shine when you model a small language. Arithmetic expressions are a classic:

HASKELL
data Expr
  = Num Double
  | Add Expr Expr
  | Mul Expr Expr
  | Neg Expr
  deriving (Show)

eval :: Expr -> Double
eval (Num n)   = n
eval (Add a b) = eval a + eval b
eval (Mul a b) = eval a * eval b
eval (Neg a)   = negate (eval a)

The expression 2 * (3 + 4) is data: Mul (Num 2) (Add (Num 3) (Num 4)). Because it is data, you can do more than evaluate it. You can print it, simplify it or check it:

HASKELL
render :: Expr -> String
render (Num n)   = show n
render (Add a b) = "(" ++ render a ++ " + " ++ render b ++ ")"
render (Mul a b) = "(" ++ render a ++ " * " ++ render b ++ ")"
render (Neg a)   = "-" ++ render a

Each new operation is one more function with one equation per constructor. If you later add a Sub constructor and compile with -Wall, GHC warns about every function that now misses a case. That safety net is a large part of why people model languages this way (the project in Expression Calculator builds on it).

JS Evaluate and print an expression tree (stand-in)

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Folding over a tree

Look at size, depth and toList again. Each one replaces Leaf with a fixed value and Node with a way to combine the three pieces. You can capture that once. This is a fold for trees:

HASKELL
foldTree :: b -> (b -> a -> b -> b) -> Tree a -> b
foldTree leaf _ Leaf         = leaf
foldTree leaf node (Node l x r) =
  node (foldTree leaf node l) x (foldTree leaf node r)

size', depth' :: Tree a -> Int
size'  = foldTree 0 (\l _ r -> l + 1 + r)
depth' = foldTree 0 (\l _ r -> 1 + max l r)

toList' :: Tree a -> [a]
toList' = foldTree [] (\l x r -> l ++ [x] ++ r)

This is the same idea as foldr on lists, where [] and (:) are replaced by your own pieces (see Higher-Order Functions). Standard classes make this automatic for many types; later you will meet Foldable, which lets sum, length and elem work on any container, including trees (see Foldable and Traversable).

Deep recursion on a very unbalanced tree can use a lot of stack, although GHC's stack grows on demand. For huge inputs prefer balanced structures from a library.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What makes a data type recursive?

    In Node (Tree a) a (Tree a), the fields of type Tree a refer back to the type being defined.
  2. 2. How many equations does a function over data Tree a = Leaf | Node (Tree a) a (Tree a) normally need?

    You write one equation per constructor; the Node equation calls the function on its subtrees.
  3. 3. What does insert x tree do to the original tree in Haskell?

    Values are immutable, so insert rebuilds only the path to the new element and reuses the rest.
  4. 4. Why is an expression tree useful compared with evaluating directly?

    Representing code as data lets you write many functions over it, such as eval and render.

Summary

  • A recursive type has constructors that contain the type itself, such as Cons a (MyList a) or Node (Tree a) a (Tree a).
  • Write one equation per constructor; recursive calls go on the smaller pieces.
  • Operations like insert build new values and share untouched parts; nothing is mutated.
  • Expression trees turn a small language into data, so you can evaluate, render and transform it.
  • A tree fold replaces each constructor by a function, and many functions are just folds.
  • A plain search tree is not balanced; use Data.Map and Data.Set in real code.

Next: Parametric Polymorphism and Type Variables.