List comprehension in Haskell

Introduction

Generating and operating on lists of data in languages is an essential tool when doing even the most basic of processing. List comprehension is just this process. It’s prevalent in most of today’s languages and today I want to post about this process in Haskell.

A numeric example

Working with numeric data is probably the easiest of examples to help you grasp this concept. Let’s start by using a list comprehension to generate a list of numbers 1-through-5.

[x | x <- [1..5]]

This will return a list looking like [1, 2, 3, 4, 5]. Analysing what we’ve just written here, we can see that what we want to return is on the left hand side of the pipe | symbol, how we want to generate each value sits on the right hand side of the pipe symbol. This expression is wrapped in square braces because we want a list! We can change this ever so slightly to only give us back odd numbers like so:

[[x | x <- [1..5], odd x]

You can see that we’ve just concatenated another piece of criteria to the right hand side of the expression specifying that we only want odd numbers. We then end up with a list looking like [1, 3, 5]. These are still very simple examples, but we can do some very powerful things with these expressions. Take the following for example.

[[x * y | x <- [1..5], y <- [1..5]]

Looking at the left-hand side you can see that we want the multiple of x and y. On the right-hand side you can see that both x and y iterate 1-through-5, so we end up with the following:

[1,2,3,4,5,2,4,6,8,10,3,6,9,12,15,4,8,12,16,20,5,10,15,20,25]

Now we’re getting somewhere.

Folding in Haskell

Introduction

In this post I would like to present some basic concepts in folding. This really will be over in a flash, so don’t blink - it’s easy.

tl;dr

The Haskell functions foldl and foldr allow you to “fold” functions between values.

Diagram it for me!

If you read up on these functions in the documentation, you’ll see mention of “reducing values in a list” and such. All this really means, is that you’re going to iterate through a list apply a function at every stop and finish up with a “reduced” answer. Here, take a look at this. I have an array spanning 1 through 5.

[1, 2, 3, 4, 5]

I want to add all of the values together, so I use foldl to move through the list applying the + operator.

foldl (+) 0 [1,2,3,4,5]

This command in english says, apply the + operator between each element in the list (moving left to right) with an initial value of 0. Or:

0 + 1 + 2 + 3 + 4 + 5 = 15

Bring it back the other way!

Folding right is interesting. No so much for the example that we have above, as addition moving left or right is at identity with each other. I’ve prepared a more interesting example for moving to the right. Take a look at the following and the results:

foldl (-) 10 [10, 20, 30]
-50

foldr (-) 10 [10, 20, 30]
10

Wow, that’s quite the difference. When folding right, the reduction occurs in reverse (values right to left) and then it’s applied to the initial value.

(foldl)
10 - 10 - 20 - 30     = -50 

(foldr)
10 - (20 - (30 - 10)) = 10

So, there we are folding to the right! That’s (very basic) folding for you anyway. An interesting follow-up to this article is the function foldl'. By nature foldl that we’ve just discussed is lazy, meaning it will build the list of computations to execute using the source array and only execute those computations once the array is depleted (internally). It’s been shown that this model of execution can cause stack overflow errors for larger lists because of this deferred execution model. foldl' solves this by not deferring execution. So, the overall result will be the same it’s just that foldl' won’t be lazy in getting the answer back to you.

Function currying in Haskell

I think it’s important to follow up my previous post on anonymous functions with a post on currying. One of the more difficult concepts to think about (only because Haskell does a great job of separating you from this) is that every function only has 1 argument.

Take this basic greeting example which expects the name of someone who is doing the greeting and the name of someone who is being greeted:

let sayHello toWho fromWho = fromWho ++ " says Hello to " ++ toWho

This is a pretty trivial example. Give it two names and the computer will appear to play nice between these two people:

*Main> sayHello "John" "Peter"
"Peter says Hello to John"

We like John so much, that we’re going to make a new function using this existing one.

let sayHelloToJohn = sayHello "John"

So now, we can get anyone to play nice with John:

*Main> sayHelloToJohn "Peter"
"Peter says Hello to John"
*Main> sayHelloToJohn "Joe"
"Joe says Hello to John"
*Main> sayHelloToJohn "Jane"
"Jane says Hello to John"

Great! We’ve just made a partially applied function. When you don’t specify enough parameters to a function, you’re actually returned a function (or, partially applied function) that you can continue to use. Breaking down how this works, when Jane is saying hello to John she is actually doing so by doing this:

(sayHello "John") "Jane"

This should at least explain my outlandish claims above of functions only having one argument, anyway. You’ve just witnessed function currying in motion. These principles are also directly applicable on infix functions as well, they just need a little extra help to be told so. Take this for example:

double :: (Floating a) => a -> a
double = (*2)

Ignoring the function definition, you can see that all you need to do for infix functions is to surround then with parenthesis. You need to supply the value that makes it a partial application of course!

Function composition in Haskell

Function composition is a no-brainer concept for Haskell that makes a lot of sense. It’s truly aligned with its mathematical equivelant where you have two given functions:

f(x) = x * x
g(x) = x + 2

The composition part comes in when you nest these functions, so that you end up with:

f(g(x)) = f(x + 2)
f(g(x)) = (x + 2) * (x + 2)
f(g(x)) = x^2 + 4x + 4

Mathematically, this is cake. We just nest the second function inside the first. If we look at it with respect to Haskell we end up with this:

-- | g(x) = x + 2
let g x = x + 2

-- | f(x) = x * x
let f x = x * x

-- | f(g(x))
let fg = f . g

So, the . operator is doing the composition here for us. Below I’ve got the mathematical representation on the left, Haskell on the right.

f(g(x)) = (f . g) x

The real power here is that you can use function composition with any two functions, just as long as the return type of the second function is the same as the argument taken by the first function.

Slick.

Anonymous Functions in Haskell

Introduction

It’s no doubt that when you’re first entering the wild world of Haskell, that it’s syntax is a little alien to look at, at first glance. Once of the major building blocks or keys to unlocking power in Haskell are anonymous functions. The idea of higher-order functions in languages these days is becoming more of a standard rather than a feature and Haskell is no exception. There’s plenty around on the web to read about anonymous functions, higher-order functions and of course [functional programming](http://en.wikipedia.org/wiki/Functional_programming.

An example

A fairly unintuitive example, but shows how you can assign an anonymous function to a handleable variable is shown:

let y = (\x -> x)

Breaking this down, the key part is (\x -> x). Immediately, you can see that anonymous functions take the form of (\param1 .. paramn -> body). The real power here is unlocked when you use an anonymous function in conjunction with other functions. The best example I think is the use of the map function. The map function is defined as follows:

map :: (a -> b) -> [a] -> [b]
map f xs = [f x | x <- xs]

This definition says, give me a function f and I’ll take all of the a’s and turn them into b’s. Obviously, the anonymous function comes in for the f component. For simplicity, a can be an array of integers.

map (\x -> x * x) [1,2..100]

So the above example maps the function (x*x) across an array from 1 to 100. Easy!