# Haskell/Overview

Haskell is a standardized functional programming language with non-strict semantics. Haskell features include support for recursive functions, datatypes, pattern matching, and list comprehensions. By combining these features, functions that would be difficult to write in a procedural programming language are 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.^{[1]}

The examples below give a taste of Haskell, oriented toward those familiar with other programming languages.

## Examples[edit]

The classic definition of the factorial function:

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

A cute definition using Haskell's built-in list notation and the standard `product`

function:

```
fac n = product [1..n]
```

Both definitions above should compile into the *same* efficient code via 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 algorithm 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.)

Non-skipping stable merge sort 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

repeatedly applies a function **until** *cond* *fun**fun* until a condition *cond* is met; with `where`

keyword introducing the local definitions showcasing the use of patterns (with `(`

matching a non-empty list with the head **x:xs**)

and tail **x**

) and guards.
**xs**

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

working with lists, whether finite or not, due to lazy (i.e. **map***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 by trial division is

```
primes = 2 : sieve [3..] primes -- 2 : _Y ((3:) . sieve [5,7..])
where
sieve xs (p:ps) | (h,t) <- span (< p*p) xs =
h ++ sieve [n | n <- t, rem n p > 0] ps
```

or as unbounded incremental Sieve of Eratosthenes with ordered lists,

```
import Data.List.Ordered
primes = 2 : _Y ((3:) . minus [5,7..] -- ps = [2..] \\ [[p*p, p*p+p..] | p <- ps]
. unionAll
. map (\p -> [p*p, p*p+2*p..]))
_Y g = g (_Y g) -- = g (g (g (g (g ... ))))
```

defining primes corecursively as natural numbers which are not multiples of primes. Or with arrays,

```
import Data.Array
import Data.List (tails, inits)
ps = 2 : [n | (r:q:_, px) <- (zip . tails . (2:) . map (^2)) ps (inits ps),
(n,True) <- assocs (
accumArray (\_ _ -> False) True (r+1,q-1)
[(m,()) | p <- px,
let s = div (r+p) p * p, m <- [s,s+p..q-1]] )]
```

## It's not just for quicksort![edit]

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.

## Notes[edit]

- ↑ Based on crude Google Scholar "since 2010" queries – Haskell "functional programming": 2220, Scheme "functional programming": 1400, ML "functional programming": 1020, Lisp "functional programming": 779, OCaml "functional programming": 316, Scala "functional programming": 290, XSLT "functional programming":93, Clojure "functional programming": 76