Search⌘ K
AI Features
Home
Courses
Learn Functional Programming in Haskell

Creating Recursive Types

Explore how to create recursive types in Haskell, including linked lists and binary trees. Learn to write recursive functions for these types, implement tree traversals, and use higher-order functions like map and fold to manipulate tree structures effectively.

We'll cover the following...

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