Haskell/Overview

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 2011, the functional language on and in which the most research is being performed.

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 defines 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 Quicksort alogrithm can be expressed in Haskell concisely as:

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

(note that true quicksort sorts in-place but Haskell's lists are immutable so have to be copied around.)

Nonskipping stable mergesort is

  mgsort less [] = []
  mgsort less xs = head $ until (null.tail) pairs [[x] | x <- xs]
    where 
      pairs (x:y:xs)    = merge x y : pairs xs
      pairs xs          = xs
      merge (x:xs) (y:ys)
            | less y x  = y : merge (x:xs) ys 
            | True      = x : merge  xs (y:ys)
      merge  xs     ys  = xs ++ ys

where (.) is the function composition operator (h . g) x = h (g x) , (\x -> ...) is a lambda expression (a nameless function), and the predefined function  until cond fun  repeatedly applies a function fun  until a condition cond  is met; with where keyword introducing the local definitions showcasing the use of patterns (with (x:xs) matching a non-empty list with the head x and tail xs) and guards.

The Hamming numbers sequence is just

  hamm = 1 : map (2*) hamm `union` 
               (map (3*) hamm `union` map (5*) hamm)
  -- a union of two ordered lists:
  union (x:xs) (y:ys) = case (compare x y) of
          LT -> x : union  xs  (y:ys)
          EQ -> x : union  xs     ys 
          GT -> y : union (x:xs)  ys

using 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 back-quotes turns it into infix operator so that sub-expressions are automatically formed as if by placing parentheses appropriately, forming a nested expression, as in 2+3+5 --> ((2+3)+5) ; and a comment line is introduced by two dashes.

Finally, the infinite list of prime numbers, also using the above union function, is:

  primes = 2 : gaps 3 (join [[p*p,p*p+2*p..] | p <- primes'])
   where
    primes' = 3 : gaps 5 (join [[p*p,p*p+2*p..] | p <- primes'])
    join  ((x:xs):t)        = x : union xs (join (pairs t))
    pairs ((x:xs):ys:t)     = (x : union xs ys) : pairs t
    gaps k xs@(x:t) | k==x  = gaps (k+2) t 
                    | True  = k : gaps (k+2) xs

Here primes are defined corecursively as gaps between the composite numbers, i.e. the primes' multiples.

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, check out web frameworks in Haskell and Haskell in industry articles on the Haskell wiki, or darcs, an advanced revision control system written in Haskell.