Creating Recursive Types

In this final lesson on creating data types, we will learn how to create recursive types that can contain potentially infinite values.

Recreating a list type

The canonical example of a recursive data type is the linked list. A nonempty list value contains a head element as well as a tail, which is a linked list itself. This is what makes the type recursive.

Thankfully, Haskell makes creating recursive types just as easy as any other type. We can define our own polymorphic list type as

data List a = Empty | NonEmpty a (List a) deriving (Show)

• The Empty constructor represents an empty list, just like [].
• The NonEmpty constructor takes two arguments: the head (of type a) and the tail (of type List a). It is our replacement for the : operator.

Note that we are using the type that we are defining (List a) recursively inside the definition of the constructor NonEmpty.

The equivalent representation of the list [3, 2, 6] :: [Int] in our data type is

Nonempty 3 (Nonempty 2 (Nonempty 6 Empty))) :: List Int

We can work with values of our custom lists as usual by writing recursive functions with pattern matching. For example, here is the elem function for our lists.