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) ...