Haskell/Overview

From Wikibooks, the open-content textbooks collection

Haskell is a standardized functional programming language with non-strict semantics. Interesting Haskell features include support for recursive functions and datatypes, pattern matching and list comprehensions. The combination of such features can make functions which would be difficult to write in a procedural programming language almost trivial to implement in Haskell. The language is, as of 2002, the functional language on and in which the most research is being performed.

[edit] Examples

The classic definition of the factorial function:

 fac 0 = 1 
 fac n = n * fac (n - 1)

The cute definition of the factorial function (using a built-in Haskell list notation and the standard product function):

 fac n = product [1..n]

Both are supposed to be compilable into same efficient code by a smart compiler, using equational reasoning.

A naive implementation of a function which returns the nth number in the Fibonacci sequence:

 fib 0 = 0 
 fib 1 = 1 
 fib n = fib (n - 2) + fib (n - 1)

A function which returns a list of the Fibonacci numbers in linear time:

 fibs = 0 : 1 : (zipWith (+) fibs (tail fibs))

The previous function creates an infinite list, which is possible because of lazy evaluation. One could implement fib as:

 fib n = fibs !! n

(!! is an operator which gets the nth element of a list).

The Hamming numbers sequence is just

 hamm = 1 : map (2*) hamm `merge` map (3*) hamm `merge` map (5*) hamm
   where
     merge (a:as) (b:bs)
         | a < b  = a:merge  as (b:bs)
         | a == b = a:merge  as    bs 
         | a > b  = b:merge (a:as) bs 

showcasing the use of local definitions, patterns (with (a:as) matching a non-empty list with the head a and tail as), guards, sections (partially applied operators) and the built-in function map working with lists, whether finite or not, due to lazy (i.e. by-need ) evaluation. Also, enclosing function's name into backquotes turns it into infix operator so that subexpressions are automatically formed as if by placing parentheses appropriately, forming a nested expression, as in 1+2+3 --> (1+(2+3)).

The Quicksort alogrithm can be elegantly expressed in Haskell with the help of list comprehensions:

 qsort []     = [] 
 qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x 
   where 
     elts_lt_x   = [y | y <- xs, y <  x] 
     elts_greq_x = [y | y <- xs, y >= x] 

(Note that because of excessive copying and concatenation of lists this code can be rather slow, depending on the implementation.)

Nonskipping stable mergesort can be expressed as

 mgsort f [] = []
 mgsort f xs = (head . until isSingleton (pairwise (merge f)) . map wrap) xs
   where 
     wrap         x      = [x]
     isSingleton [_]     = True
     isSingleton  _      = False
     pairwise g (x:y:r)  = g x y:pairwise g r
     pairwise g xs       = xs
     merge f (a:as) (b:bs)
           | f b a       = b:merge f (a:as) bs 
           | otherwise   = a:merge f  as (b:bs)
     merge f as     []   = as
     merge f []     bs   = bs

where (.) is the function composition operator, (h . g) x = h (g x) , f stands for "less", head is a built-in function that returns first element of a list, and the predefined function until repeatedly applies a function until a condition is met.

Finally, the infinite list of prime numbers is:

 primes   = 2: 3: sieve 0 primes' 5 
 primes'  = tail primes
 sieve k (p:ps) x          
          = [x | x<-[x,x+2..p*p-2], and [(x`rem`p)/=0 | p<-take k primes']]
            ++ sieve (k+1) ps (p*p+2)  

Here sieve explicitly uses successive prefixes of the primes list while it is being built, to test batches of odds for divisibility by them, between the successive squares of primes.

[edit] It's not just for quicksort!

Haskell is also used to build "real world" programs, including graphical or web user interfaces. To get a taste of Haskell in the real world example, check out Hope, the Haskell weblog/content-management system, or darcs, an advanced revision control system written in Haskell.