Haskell 101

January 26, 2008

Our first function

Filed under: Haskell, Pattern matching, Recursion — Haskell 101 blogger @ 4:23 pm

Part of what we will be doing throughout these blog entries is to create Haskell functions. Our first function is a simple one. In fact, it already exists. But half of the fun (at least) is going to be creating functions to learn the language. Building up basic code (even if it replicates a higher-order existing function) is one of the ways I have found to best learn a new language.So, today’s function is one that will take two lists and concatenate them. In the Haskell 98 Report, this is known as ++. I’ll call the function “union.”Let’s set the type signature first. We want to take two lists and return a third. So:

(1) union::[a]->[a]->[a]

How do we define the function? Let’s do it using recursion. We’ll add each item in the first list to an empty list [], and then add each element of the first list after that, and then, once the first list is empty, we’ll add the second list. So, we know we want to stop recursing when the first list is empty:

(2) union [] y = y

How about adding each item to the initial list? We’ll cons the item on using the : operator.

(3) union (x:xs) y = x:(union xs y)

Note the splitting of the first list into x and xs. This is a handy way of getting access to the first element of the list x, and assigning the remainder, or tail, of the list to xs (with the “s” indicating a plural number of elements). You can also see that we grab the first element and then call our union function again. We then grab the second element, call the function again, and so on. The pattern in (3) will no longer match when the first list is empty, and then the pattern in (2) will match, ending the recursion.  So, in summary, here is our function:

union::[a]->[a]->[a]
union [] y = y
union (x:xs) y = x:(union xs y)

 If you want, you can take a look at the aforementioned Haskell 98 Report and see how our function compares to the official definition of ++. 

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

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

Create a free website or blog at WordPress.com.

%d bloggers like this: