colinrmitchell.com

Blog

The Beauty of Haskell

Posted Wednesday, March 19th 2014 in Programming - Permalink

Haskell has been quickly becoming my favourite programming language. It is a functional language, different from imperative languages such as C, Python, or Perl. The easiest way to describe the difference is that imperative languages focus on an ordering of statements and their execution, whereas functional languages focus on the definition and dependencies of functions, letting the compiler determine the best order of computation. In particular, Haskell is a lazy functional language. A language is said to be lazy if it does not compute something until it is actually needed. This is disimilar from imperative languages, which are usually eager. Eager languages compute expressions as they come across them.

To show some of the power and elegance of functional programming and lazy evaluation, I wanted to show two ways that we can compute the factorial of a number in Haskell. The definition of factorial is that the factorial of a number is equal to itself multiplied by the factorial of its predecessor, and that the factorial of zero is one. Factorials of negative numbers are not defined. For example, the factorial of 4, commonly written 4!, is calculated by

4! = 4 * (3!)
   = 4 * (3 * (2!))
   = 4 * (3 * (2 * (1!)))
   = 4 * (3 * (2 * (1 * (0!))))
   = 4 * (3 * (2 * (1 * (1))))
   = 4 * 3 * 2 * 1 * 1
   = 24

As you can see, the definition of the factorial is itself recursive, so we can expect to easily define it in Haskell recursively. Here is a function that can do that:

fact :: Integer -> Integer
fact 0 = 1
fact n = n * (fact $ n - 1)

The first line above defines the type signature of the function. The type signature here means that we are taking an Integer to an Integer. Haskell has two integer data types, Int and Integer. The difference is that Int is a bounded integer dependent on the architecture of the computer processor and Integer is an unbounded integer. That’s right, (mostly) unbounded!

The second line in the function simply states that the factorial of zero is one, our end case. The next line exactly follows the definition, that the factorial of n is n multiplied by the factorial of n - 1. Using this function, the first few factorials are

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5,040
8! = 40,320
9! = 362,880

Now, let’s look at what it means for Haskell to be lazy. That means that expressions are not evaluated until we actively call upon them. For example, we can use the take function, which allows us to take an arbitrary number of elements from the start of a list. And in Haskell, we can define simple arithmetic lists using a shorthand, such as [1,2..10], which is equivalent to the list [1,2,3,4,5,6,7,8,9,10]. In Haskell, we can even define infinite lists! But how can that be, a computer can’t calculate and store an infinite list in a finite amount of time? The reason is because, even though we define a list in a never-ending way, we never actually use an infinite number of elements from it. This is laziness at work: only so many elements from the list are calculated to satisfy our request. Here is a concrete example:

> take 10 [2,4..]
[2,4,6,8,10,12,14,16,18,20]

We are taking the first ten elements from a list of all even, positive integers. As you can see, the take function is only requesting the first ten elements of the list. No more elements from the list are needed, so no more are calculated.

So how could we use this as a way to compute factorials? Well, consider the list

[1,1,2,3,4,5,6,7,8,9..]

Also consider the way to calculate the first few factorials,

0! = 1
1! = 1
   = 1 * 1
2! = 2 * 1 
   = 1 * 1 * 2 
   = 2
3! = 3 * 2 * 1 
   = 1 * 1 * 2 * 3 
   = 6
...

It looks like we can compute n! by multiplying the first n + 1 elements of that list! But how would we express this in Haskell?

One way to do this is to use a folding function. A folding function somehow reduces a list, either to another list or to a single value. Haskell has several different folding functions built into it, one of which is foldr. The foldr function is defined as

foldr f z []     = z 
foldr f z (x:xs) = f x (foldr f z xs)

This function takes three arguments: a folding function, a starting value, and a list. The folding function lets us define how we want to combine two elements of the list. Consider using the folding function on a sublist of our list above,

foldr (*) 1 [1,2,3]
≡ (*) 1 (foldr (*) 1 [2,3])
≡ (*) 1 ((*) 2 (foldr (*) 1 [3]))
≡ (*) 1 ((*) 2 ((*) 3 (foldr (*) 1 [])))
≡ (*) 1 ((*) 2 ((*) 3 (1)))
≡ 1 * 2 * 3 * 1
≡ 3!

It turns out that folding a sublist of our list creates an expression equivalent to the factorial! Note that surrounding an infix operator such as * (multiplication) in parentheses causes it to become a prefix operator, that is, (*) 1 2 ≡ 1 * 2.

We can write a new factorial function, which is not itself defined recursively:

factFold :: Int -> Integer
factFold x = foldr (*) 1 $ take x [1,2..]

The first line is again a type signature. It states that we are taking a bounded integer to an unbounded integer. We must limit the argument to be a bounded integer since the take function that we are using only accepts a bounded integer. We can, however, return an unbounded integer, since the multiplication operation works with unbounded integers. This allows us to compute some very large factorials with only a single line of code!

This is just one example of a succinct way to solve a problem in Haskell. Another that I have found is a way to find prime numbers. You can view my function to find prime numbers in my code repository, here. You can look at the full program for this factorial exercise here.

Finally, I tested both of the above functions by calculating the first 500 factorials. Some of the results are below.

Using factFold
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5,040
8! = 40,320
9! = 362,880
10! = 3,628,800
11! = 39,916,800
12! = 479,001,600
13! = 6,227,020,800
14! = 87,178,291,200
...
Took 0.168925 seconds

Using factRecursive
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5,040
8! = 40,320
9! = 362,880
10! = 3,628,800
11! = 39,916,800
12! = 479,001,600
13! = 6,227,020,800
14! = 87,178,291,200
...
Took 0.164754 seconds

And, finally, here is 499!:

499! = 2,440,273,651,982,220,137,402,477,570,846,093,852,507,148,685,606,385,684,384,827,176,771,690,746,307,763,995,210,992,895,004,406,563,726,027,232,954,296,407,168,326,757,444,156,354,400,961,570,410,318,658,570,955,815,143,878,661,207,545,921,718,172,540,858,349,095,764,849,825,452,688,611,340,346,541,538,922,125,604,620,905,288,437,757,578,931,509,554,299,726,988,735,562,075,288,548,067,654,730,794,942,772,955,756,990,876,979,191,075,075,980,846,482,122,542,653,968,655,491,431,092,619,954,405,562,029,122,162,376,747,419,062,032,712,648,865,974,059,127,793,257,823,317,949,539,144,175,853,857,742,563,560,140,530,349,015,536,821,439,248,780,788,645,072,845,210,469,891,700,259,837,143,002,497,413,923,136,283,250,718,113,386,847,626,017,712,498,493,783,128,253,551,308,963,773,013,187,695,903,550,721,788,011,490,477,880,671,596,952,727,889,810,626,124,647,498,132,890,097,649,330,151,893,471,724,149,275,850,368,400,918,739,385,962,044,527,943,905,194,381,890,435,646,663,513,869,163,017,104,665,641,525,640,046,805,253,815,796,684,903,424,012,415,429,281,958,912,232,255,258,291,902,474,459,826,680,339,104,727,701,885,771,184,037,454,867,590,346,029,172,715,141,656,711,560,317,470,865,537,777,360,240,799,764,769,404,302,935,210,890,815,327,071,968,348,860,960,257,876,627,793,763,278,974,939,317,635,009,013,852,730,676,350,110,956,257,280,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000


List Posts Newest Posts Page 1Next Page