# Creating Recursive Types

Learn how to create recursive types and implement a binary tree data structure.

## 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`

.

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.

Get hands-on with 1200+ tech skills courses.