Recursive types in Haskell

I was playing around today with attempting to re-define the definition of Haskell’s list. The list in Haskell is well defined using the symbols [ and ], and some additional operators such as : and ++

For example, if we have a list [1, 2, 3] we can easily append a number to the beginning (prefix) by doing 0:[1, 2, 3], or we can append a number to the end (postfix) by doing [1, 2, 3] ++ [4].

The difference between these two operations is that the former only takes constant time, since it is appending a value to the beginning of the list, while the latter takes O(n) time, because it first needs to traverse the list and then append another list ([value]) to the end of it.

So anyway, back to playing with recursive definitions. My definition of the list was:

data List a = Nil | Cons a (List a) deriving (Show)

What this says is that the type List can have 2 constructors, either Nil or Cons. If it’s Nil, then it’s Nil (end of list), however, if it’s Cons, then we can add a value to it (e.g. Cons 3), but after Cons we must also add another “List a” type (which can be either Nil or another recursive Cons).

So this recursive definition allows us to define a list. And this is how lists are basically implemented in LISP. For example, if we wanted to represent [1, 2, 3] using our Cons Nil representation, we would have something like:

Cons 1 (Cons 2 (Cons 3 Nil))

You can play around with it as much as you like; what I did was only implement the ++ operator:

add' :: List a -> List a -> List a
add' Nil ys = ys
add' (Cons x xs) ys = Cons x (add' xs ys)

Example usage:


*Main> add' (Cons 1 (Cons 2 (Cons 3 Nil))) (Cons 4 Nil)
Cons 1 (Cons 2 (Cons 3 (Cons 4 Nil)))
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s