Haskell a la carte

New to Haskell? This menu will give you a first impression. Don't read all the explanations, or you'll be starved before the meal.

Apéritifs

Foretaste of an excellent meal.

  qsort :: Ord a => [a] -> [a]
  qsort []     = []
  qsort (x:xs) = qsort (filter (<x) xs) ++ [x] ++ qsort (filter (>=x) xs))

Quicksort in three lines (!). Sorts not only integers but anything that can be compared.

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

The infinite list of fibonacci numbers. Just don't try to print all of it.

  linecount = interact $ show . length . lines
  wordcount = interact $ show . length . words

Count the number of lines or words from standard input.

Entrées

How to read the dishes.

  square x = x*x

is the function $f(x)=x\cdot x$ which maps a number to its square. While we commonly write parenthesis around function arguments in mathematics and most programming languages, a simple space is enough in Haskell. We're going to apply functions to arguments all around, so why clutter the notation with unnecessary ballast?

  square :: Int -> Int
  square x = x*x

Squaring again, this time with a type signature which says that squaring maps integers to integers. In mathematics, we'd write $f:\mathbb {Z} \to \mathbb {Z} ,\ f(x)=x\cdot x$. Every expression in Haskell has a type and the compiler will automatically infer (= figure out) one for you if you're too lazy to write down a type signature yourself. Of course, parenthesis are allowed for grouping, like in square (4+2) which is 36 compared to square 4 + 2 which is 16+2=18.

  square :: Num a => a -> a
  square x = x*x

Squaring yet again, this time with a more general type signature. After all, we can square anything (a) that looks like a number (Num a). By the way, this general type is the one that the compiler will infer for square if you omit an explicit signature.

  average x y = (x+y)/2

The average of two numbers. Multiple arguments are separated by spaces.

  average :: Double -> Double -> Double
  average x y = (x+y)/2

Average again, this time with a type signature. Looks a bit strange, but that's the spicey currying. In fact, average is a function that takes only one argument (Double) but returns a function with one argument (Double -> Double).

  power a n = if n == 0 then 1 else a * power a (n-1)

$a^{n}$, defined with recursion. Assumes that the exponent n is not negative, that is n >= 0.

Recursion is the basic building block for iteration in Haskell, there are no for or while-loops. Well, there are functions like map or foldr that provide something similar. There is no need for special built-in control structures, you can define them yourself as ordinary functions (later).

  power a 0 = 1
  power a n = a * power a (n-1)

Exponentiation again, this time with pattern matching. The first equation that matches will be chosen.

  length []     = 0
  length (x:xs) = 1 + length xs

Calculate the length of a list. What's a list? Well, a list may either be empty ([]) or be an element (x) prepended (:) to another list (xs). Read "xs" as the plural of "x", that is as "ex-es". It's a list of other such elements x, after all.

  length :: [a] -> Int
  length []     = 0
  length (x:xs) = 1 + length xs

Length of a list again, this time with type signature. [a] is the type of lists with elements of type a. length can be used for any such element type.

  head :: [a] -> a
  head (x:xs) = x

First element of a list. Undefined for empty lists.

  sum []     = 0
  sum (x:xs) = x + sum xs

Sum all elements of a list.

  average xs = sum xs / (fromIntegral (length xs))

Arithmetic mean. fromIntegral converts the integer result of length into a decimal number for the division /.

Soupes

The best soup is made by combining the available ingredients.

  (.) :: (b -> c) -> (a -> b) -> (a -> c)
  (.) f g x = f (g x)

  fourthPower = square . square

The dot f . g is good old function composition $f\circ g$. First apply g, then apply f. Simple example: squaring something twice.

  minimum = head . qsort

To find the least element of a list, first sort and then take the first element. You think that takes too much time ($O(n\cdot \log n)$ instead of $O(n)$)? Well, thanks to lazy evaluation, it doesn't! In Haskell, expressions are evaluated only as much as needed. Therefore, the sorting won't proceed further than producing the first element of the sorted list. Ok, the sorting function has to play along and produce that one quickly, but many like quicksort (in the average case) or mergesort do so.

Plats principaux

Desserts

Sugar-sweet and en passant.

Vins