Haskell features


This article describes the features in []Haskell.

Examples

Factorial

A simple example that is often used to demonstrate the syntax of functional languages is the factorial function for non-negative integers, shown in Haskell:

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial

Or in one line:

factorial n = if n > 1 then n * factorial else 1

This describes the factorial as a recursive function, with one terminating base case. It is similar to the descriptions of factorials found in mathematics textbooks. Much of Haskell code is similar to standard mathematical notation in facility and syntax.
The first line of the factorial function describes the type of this function; while it is optional, it is considered to be good style to include it. It can be read as the function factorial has type from integer to integer. That is, it takes an integer as an argument, and returns another integer. The type of a definition is inferred automatically if the programmer didn't supply a type annotation.
The second line relies on pattern matching, an important feature of Haskell. Note that parameters of a function are not in parentheses but separated by spaces. When the function's argument is 0 it will return the integer 1. For all other cases the third line is tried. This is the recursion, and executes the function again until the base case is reached.
Using the product function from the Prelude, a number of small functions analogous to C's standard library, and using the Haskell syntax for arithmetic sequences, the factorial function can be expressed in Haskell as follows:

factorial n = product

Here denotes the arithmetic sequence in list form. Using the Prelude function enumFromTo, the expression can be written as enumFromTo 1 n, allowing the factorial function to be expressed as

factorial n = product

which, using the function composition operator to compose the product function with the curried enumeration function can be rewritten in point-free style:

factorial = product. enumFromTo 1

In the Hugs interpreter, one often needs to define the function and use it on the same line separated by a where or let..in. For example, to test the above examples and see the output 120:

let in factorial 5

or

factorial 5 where factorial = product. enumFromTo 1

The GHCi interpreter doesn't have this restriction and function definitions can be entered on one line, and referenced later.

More complex examples

Calculator

In the Haskell source immediately below, "::" can be read as "has type"; "a —> b" can be read as "is a function from a to b".
In the second line "calc =... " the equals sign can be read as "can be"; thus multiple lines with "calc =... " can be read as multiple possible values for calc, depending on the circumstance detailed in each line.
A simple Reverse Polish notation calculator expressed with the higher-order function foldl whose argument f is defined in a where clause using pattern matching and the type class Read:

calc :: String ->
calc = foldl f . words
where
f "+" = :zs
f "-" = :zs
f "*" = :zs
f "/" = :zs
f "FLIP" = y:x:zs
f xs y = read y : xs

The empty list is the initial state, and f interprets one word at a time, either as a function name, taking two numbers from the head of the list and pushing the result back in, or parsing the word as a floating-point number and prepending it to the list.

Fibonacci sequence

The following definition produces the list of Fibonacci numbers in linear time:

fibs = 0 : 1 : zipWith fibs

The infinite list is produced by corecursion — the latter values of the list are computed on demand starting from the initial two items 0 and 1. This kind of a definition relies on lazy evaluation, an important feature of Haskell programming. For an example of how the evaluation evolves, the following illustrates the values of fibs and tail fibs after the computation of six items and shows how zipWith has produced four items and proceeds to produce the next item:
fibs = 0 : 1 : 1 : 2 : 3 : 5 :...
+ + + + + +
tail fibs = 1 : 1 : 2 : 3 : 5 :...
= = = = = =
zipWith... = 1 : 2 : 3 : 5 : 8 :...
fibs = 0 : 1 : 1 : 2 : 3 : 5 : 8 :...
The same function, written using GHC's parallel list comprehension syntax :

fibs = 0 : 1 :

or with regular list comprehensions:

fibs = 0 : 1 :

or directly self-referencing:

fibs = 0 : 1 : next fibs where next = : next t

With stateful generating function:

fibs = next where next = a : next

or with unfoldr:

fibs = unfoldr

or scanl:

fibs = 0 : scanl 1 fibs

Using data recursion with Haskell's predefined fixpoint combinator:

fibs = fix xs ) -- zipWith version
= fix . -- same as above, pointfree
= fix . scanl -- scanl version

Factorial

The factorial we saw previously can be written as a sequence of functions:

factorial n = foldr . ) id $ 1
-- factorial 5 id )))) 1
-- . . . . . id $ 1

More examples

Hamming numbers

A remarkably concise function that returns the list of Hamming numbers in order:

hamming = 1 : map hamming `union` map hamming
`union` map hamming

Like the various fibs solutions displayed above, this uses corecursion to produce a list of numbers on demand, starting from the base case of 1 and building new items based on the preceding part of the list.
Here the function union is used as an operator by enclosing it in back-quotes. Its case clauses define how it merges two ascending lists into one ascending list without duplicate items, representing sets as ordered lists. Its companion function minus implements set difference:
It is possible to generate only the unique multiples, for more efficient operation. Since there are no duplicates, there's no need to remove them:

smooth235 = 1 : foldr s. map . )
where
fix f = x where x = f x -- fixpoint combinator, with sharing

This uses the more efficient function merge which doesn't concern itself with the duplicates :

mergeBy less xs ys = merge xs ys where
merge xs = xs
merge ys = ys
merge | less y x = y : merge ys
| otherwise = x : merge xs

Each vertical bar starts a guard clause with a guard expression before the = sign and the corresponding definition after it, that is evaluated if the guard is true.

Mergesort

Here is a bottom-up merge sort, defined using the higher-order function until:

mergesortBy less =
mergesortBy less xs = head $
until x] | x <- xs]
pairwise f = f a b : pairwise f t
pairwise f t = t

Prime numbers

The mathematical definition of primes can be translated pretty much word for word into Haskell:

-- "Integers above 1 that cannot be divided by a smaller integer above 1"
primes = , all ]

This finds primes by trial division. Note that it is not optimized for efficiency and has very poor performance. Slightly faster is this code by David Turner:

primes = sieve where sieve = p : sieve

Much faster is the optimal trial division algorithm

primes = 2 : , all $ takeWhile . ) primes]

or an unbounded sieve of Eratosthenes with postponed sieving in stages,

primes = 2 : sieve primes where
sieve -> ) = h ++ sieve ps

or the combined sieve implementation by Richard Bird,

-- "Integers above 1 without any composite numbers, whereas the
-- composite numbers are found by enumeration of each prime's multiples"
primes = 2 : minus

or an even faster tree-like folding variant with nearly optimal time complexity and very low space complexity achieved through telescoping multistage recursive production of primes:

primes = 2 : _Y . minus . _U. map )
where
_Y g = g -- )) -- non-sharing Y combinator
_U = x : t -- ~= nub.sort.concat

Working on arrays by segments between consecutive squares of primes, it's

import Data.Array
import Data.List
ps = 2 :

The shortest possible code is probably nubBy.gcd) . It is quite slow.

Syntax

Layout

Haskell allows indentation to be used to indicate the beginning of a new declaration. For example, in a where clause:

product xs = prod xs 1
where
prod a = a
prod a = prod xs

The two equations for the nested function prod are aligned
vertically, which allows the semi-colon separator to be omitted. In
Haskell, indentation can be used in several syntactic constructs,
including do, let, case, class,
and instance.
The use of indentation to indicate program structure
originates in Landin's ISWIM language, where it was called the
off-side rule. This was later adopted by Miranda, and Haskell
adopted a similar version of Miranda's
off-side rule, which is called "layout". Other languages to adopt whitespace-sensitive syntax
include Python and F#.
The use of layout in Haskell is optional. For example, the function product above can also be written:

product xs = prod xs 1
where

The explicit open brace after the where keyword indicates
that the programmer has opted to use explicit semi-colons to separate
declarations, and that the declaration-list will be terminated by an
explicit closing brace. One reason for wanting support for explicit
delimiters is that it makes automatic generation of Haskell source
code easier.
Haskell's layout rule has been criticised for its complexity. In
particular, the definition states that if the parser encounters a
parse error during processing of a layout section, then it should try
inserting a close brace. Implementing this
rule in a traditional parsing/lexical-analysis combination requires
two-way cooperation between the parser and lexical analyser, whereas
in most languages these two phases can be considered independently.

Function calls

Applying a function f to a value x is expressed as simply f x.
Haskell distinguishes function calls from infix operators syntactically, but not semantically. Function names which are composed of punctuation characters can be used as operators, as can other function names if surrounded with backticks; and operators can be used in prefix notation if surrounded with parentheses.
This example shows the ways that functions can be called:

add a b = a + b
ten1 = 5 + 5
ten2 = 5 5
ten3 = add 5 5
ten4 = 5 `add` 5

Functions which are defined as taking several parameters can always be partially applied. Binary operators can be partially applied using section notation:

ten5 = 5
ten6 = 5

addfive =
ten7 = addfive 5

List comprehensions

See List comprehension#Overview for the Haskell example.

Pattern matching

is used to match on the different constructors of algebraic data types. Here are some functions, each using pattern matching on each of the types below:

-- This type signature says that empty takes a list containing any type, and returns a Bool
empty :: -> Bool
empty = False
empty = True
-- Will return a value from a Maybe a, given a default value in case a Nothing is encountered
fromMaybe :: a -> Maybe a -> a
fromMaybe x = y
fromMaybe x Nothing = x
isRight :: Either a b -> Bool
isRight = True
isRight = False
getName :: Person -> String
getName = name
getSex :: Person -> Sex
getSex = sex
getAge :: Person -> Int
getAge = age

Using the above functions, along with the map function, we can apply them to each element of a list, to see their results:

map empty 1,2,3,,,1..
-- returns
map
-- returns
map isRight
-- returns
map getName
-- returns , using the definition for tom above

Tuples in haskell can be used to hold a fixed number of elements. They are used to group pieces of data of differing types:

account :: -- The type of a three-tuple, representing
-- a name, balance, and interest rate
account =

Tuples are commonly used in the zip* functions to place adjacent elements in separate lists together in tuples :

-- The definition of the zip function. Other zip* functions are defined similarly
zip :: -> ->
zip = : zip xs ys
zip _ _ =
zip "hello"
-- returns
-- and has type
zip3 "hello"
-- returns
-- and has type

In the GHC compiler, tuples are defined with sizes from 2 elements up to 62 elements.
In the #More_complex_examples section above, calc is used in two senses, showing that there is a Haskell type class namespace and also a namespace for values:
  1. a Haskell type class for calc. The domain and range can be explicitly denoted in a Haskell type class.
  2. a Haskell value, formula, or expression for calc.

    Typeclasses and polymorphism

Algebraic data types

are used extensively in Haskell. Some examples of these are the built in list, Maybe and Either types:

-- A list of a's is either an a consed onto another list of a's, or an empty list
data = a : |
-- Something of type Maybe a is either Just something, or Nothing
data Maybe a = Just a | Nothing
-- Something of type Either atype btype is either a Left atype, or a Right btype
data Either a b = Left a | Right b

Users of the language can also define their own abstract data types. An example of an ADT used to represent a person's name, sex and age might look like:

data Sex = Male | Female
data Person = Person String Sex Int -- Notice that Person is both a constructor and a type
-- An example of creating something of type Person
tom :: Person
tom = Person "Tom" Male 27

Type system

The ST monad allows programmers to write imperative algorithms in Haskell, using mutable variables and mutable arrays. The advantage of the ST monad is that it allows programmers to write code that has internal side effects, such as destructively updating mutable variables and arrays, while containing these effects inside the monad. The result of this is that functions written using the ST monad appear completely pure to the rest of the program. This allows programmers to produce imperative code where it may be impractical to write functional code, while still keeping all the safety that pure code provides.
Here is an example program that takes a list of numbers, and sums them, using a mutable variable:

import Control.Monad.ST
import Data.STRef
import Control.Monad
sumST :: Num a => -> a
sumST xs = runST $ do -- runST takes stateful ST code and makes it pure.
summed <- newSTRef 0 -- Create an STRef
forM_ xs $ \x -> do -- For each element of the argument list xs..
modifySTRef summed -- add it to what we have in n.
readSTRef summed -- read the value of n, which will be returned by the runST above.

STM monad

The STM monad is an implementation of Software Transactional Memory in Haskell. It is implemented in the GHC compiler, and allows for mutable variables to be modified in transactions.

Arrows

As Haskell is a pure functional language, functions cannot have side effects. Being non-strict, it also does not have a well-defined evaluation order. This is a challenge for real programs, which among other things need to interact with an environment. Haskell solves this with monadic types that leverage the type system to ensure the proper sequencing of imperative constructs. The typical example is I/O, but monads are useful for many other purposes, including mutable state, concurrency and transactional memory, exception handling, and error propagation.
Haskell provides a special syntax for monadic expressions, so that side-effecting programs can be written in a style similar to current imperative programming languages; no knowledge of the mathematics behind monadic I/O is required for this. The following program reads a name from the command line and outputs a greeting message:

main = do putStrLn "What's your name?"
name <- getLine
putStr

The do-notation eases working with monads. This do-expression is equivalent to, but easier to write and understand than, the de-sugared version employing the monadic operators directly:

main = putStrLn "What's your name?" >> getLine >>= \ name -> putStr

Concurrency

The Haskell language definition itself does not include either
concurrency or parallelism, although GHC supports both.
Concurrent Haskell is an extension to Haskell that provides
support for threads and synchronization. GHC's
implementation of Concurrent Haskell is based on multiplexing
lightweight Haskell threads onto a few heavyweight OS
threads, so that Concurrent Haskell programs run in
parallel on a multiprocessor. The runtime can support millions of simultaneous threads.
The GHC implementation employs a dynamic pool of OS threads, allowing
a Haskell thread to make a blocking system call without
blocking other running Haskell threads. Hence the
lightweight Haskell threads have the characteristics of heavyweight OS
threads, and the programmer is unaware of the implementation details.
Recently, Concurrent Haskell has been extended with support for Software Transactional Memory, which is a concurrency abstraction in which compound operations on shared data are performed atomically, as transactions. GHC's STM implementation is the only STM implementation to date to provide a static compile-time guarantee preventing non-transactional operations from being performed within a transaction. The Haskell STM library also provides two operations not found in other STMs: retry and orElse, which together allow blocking operations to be defined in a modular and composable fashion.