Functional Programming (FP)

A programming style based on the application of functions (more information).

Arity

The (maximal) number of arguments expected by a function.

Expressions

• conditional ones: if/then/else (ex: if n >= 0 then n else -n)
• guarded: | can be read as "when (some condition is true)"; knowing that otherwise = True allows to define default clauses
• lambda expressions are just anonymous functions; ex: \x -> 4 + 2*x

Operators

Prelude> :info +
type Num :: * -> Constraint
class Num a where
  (+) :: a -> a -> a
  ...
    -- Defined in ‘GHC.Num’
infixl 6 +

x:y:z:l  ≡  x:(y:(z:l))

[4,5,3] = 4:5:3:[]

A -> B -> C ->  ≡  A -> (B -> (C -> D))

-- mult :: Int -> (Int -> (Int -> Int))
mult :: Int -> Int -> Int -> Int

-- mult x y z = ((mult x) y) z
mult x y z = x*y*z

a $ b op c  ≡  a (b op c)

($) :: (a -> b) -> a -> b
f $ x = f x

Function

An association from a set of arguments to a set of corresponding results.

double x = 2*x

sum :: Num a => [a] -> a
sum []     = 0
sum (n:ns) = n + sum ns

A function may not be defined for all (well-typed) combinations of its arguments.

For example head [] is to throw an exception.

A function is a value like the other datatypes (first-class citizen).

Thanks to the algebraic datatypes such as lists and tuples, a function may take and return an arbitrary number of values (thus including functions).

A function may be only partially applied: its last argument(s) may not specified in a given call. Then the value of the overall expression is a function of these remaining, unspecified arguments.

For example, if f :: (Int,Float) -> Bool then f 3 :: Float -> Bool.

By default functions are polymorphic, insofar as they will accept all types determined as compatible. For example zip :: [a] -> [b] -> [(a,b)] can handle any types for a and b.

Functions are defined from expressions and based on pattern matching, which operates on few possible patterns that are examined in turn, from top to bottom:

• function application, like in:

(&&) :: Bool -> Bool -> Bool
True && b = b
False && _ = False

• tuple patterns, like in:

fst :: (a,b) -> a
fst (x,_) = x

• list patterns, like in:

tail :: [a] -> [a]
tail (_:xs) = xs

The ‘_’ character acts as a "wildcard" (it matches any value).

Note that a non-empty list is (a bit surprisingly) to be pattern-matched with (x:xs) and not [x:xs]. For example:

product :: Num a => [a] -> a
product [] = 1
product (n:ns) = n * product ns

The same name cannot be specified for two arguments to match when they are equal; a guard must be used for that. Finally pattern matching can operate on few possible patterns: function application, tuple and list ones, that's it.

Guards

Functions can be defined using guarded equations, to select which clause applies based on the first one from the top to evaluate to True. As Haskell can guarantee that these functions are pure, guards can be user-defined (rather than be taken in a limited selection of built-in guards).

For example:

abs | n >= 0    = n
    | otherwise = -n

Currying

A function taking its arguments one by one (one at a time, from left to right), each time returning a function of a decremented arity, is said to be curried.

Such 1-arity functions are those directly modelled by the lambda calculus, an essential base of the functional languages.

As the function arrow operator (->) is right associative, the type of functions is preferably written as:

f :: TArg1 -> TArg2 -> ... -> TArgn -> TResult

This corresponds to the following actual type:

f :: TArg1 -> ( TArg2 -> (... -> (TArgn -> TResult))...)

Consequently, as their arguments are to be applied one by one from left to right, the `` `` operator (function application is represented by the space character) is right-associative:

f a1 a2 ... an  ≡  (((f a1) a2) ... an)

Functions can thus all be seen as curried ones, and can also be directly transposed as lambda ones; for example the following definitions define the same function:

add :: Int -> Int -> Int
add x y = x + y

add :: Int -> (Int -> Int)
add = \x -> (\y -> x + y)

In this latter form:

• the type specification and the definition of the function respect the same structure: XXX -> (XXX -> XXX)
• the function is designated (on the left of the = sign) without listing its arguments (we have add =, not add x y =) [3]
• if the purpose of the function is to return another one, its intent is clearer once expressed as a lamdba function

Side Effects

They correspond to all the consequences that the evaluation of a code (program, function) incurs besides its returned value.

Example:

• writing content on file, or on the screen
• reading from file or from the input devices (keyboard, mouse)
• changing the state of a value accessible from outside of the function
• sending a message to another process or through the network
• drawing a random value

These impure events are difficult to manage yet are generally necessary, as the purpose of a program is to trigger "interesting side-effects"; a strictly pure program would most probably have no actual use (except using time, processing resources and adding the possibility of failure).

Typing

data MyFirstType = FirstValue | SecondValue | FirstConstructor T

data MySecondType a = ThirdValue | SecondConstructor a Int

("I am a tuple", 2, True)

l1 = [1.0, 7.0, 2.0]
l2 = []
l3 = [100..]
l4 = 1 : 2 : 3 : []

u s = [toUpper c | c <- s]

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v []    = v
foldr f v (x:xs)  = f x (foldr f v xs)

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v []    = v
foldl f v (x:xs)  = foldl f (f v x) xs

s = "This is a unique \
\line."

(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool

(+) :: Num a => a -> a -> a

Monad

return :: t -> Maybe t
return undefined = Nothing
return O -> Just O

(>>=) :: Maybe t -> ( t -> Maybe u ) -> Maybe u
Nothing   ```>>=``` f = Nothing
(Maybe a) ```>>=``` f = Just( f a )

seqn :: Monad m => [m a] -> m [a]
seqn []         = return []
seqn (act:acts) = do x <- act    -- *performs* this 'act' action
                          xn <- seqn acts
                          return (x:xs)

Lazy Evaluation

Most languages perform strict, eager evaluation: to evaluate a function call, first each of the supplied argument is fully evaluated, then the function itself is evaluated, based on the values jst computed for its arguments.

On the contrary, lazy evaluation strives to defer as much as possibly evaluations - possibly delaying up to the point of having never to perform them.

Lazy evaluation is convenient to express higher-level programs (ex: handling infinite lists such as [1,...]), yet makes it harder to predict the behaviour of programs at least in terms of resource consumption (time, memory, etc.).

For an increased control, strict evaluation can nevertheless be forced.

Arrows

An arrow (a.k.a. "bolt") is a type class representing computations in a pure way; this monad generalisation allows to express the relationships between the logical steps of a processing.

Refer to this article for more information.

Lambda Calculus

The lambda calculus is a simple yet powerful theory of functions. Its basis is to consider that all program elements are functions. An expression may include functions that are not yet defined and that are then considered as variables.

This is a formal system designed by Alonzo Church in the 1930s to define the concepts of function and (function) application. It relies on λ-expressions, where λ denotes the binding of a variable. For example, if M is a λ-expression, then λx.M is also one, and represents the function that to the x variable associates M (i.e. \x -> M x here).

The λ-calculus has been the first formalism defining and characterising the recursive functions, and as such is essential to the theory of computing.

It is used as theoretical programming language and also as metalanguage for formal proof.

λ-calculus may or may not be typed.

Refer to this article for more information.

Reserved Words

They cannot be used to name functions or variables:

case, class, data, deriving, do, else, if, import,
in, infix, infixl, infixr, instance, let, of, module,
newtype, then, type, where

Comments

A single-line comment starts with -- and extends to the end of the line.

Multi-line comments start with {- and extend to -}.

Example:

size = 3  -- This is a constant here.

{- Comments are essential for understanding.

   Consider writing them.


 -}

Comments can be nested.

See also the comment conventions for the Haddock documentation generator.

Literate programming (where text is by default a comment, unless being specifically designated as code) is possible in an Haskell script, whose extension shall then be .lhs (for Literate Haskell).

Glasgow Haskell Tools

They include a compiler (GHC) and an interpreter (GHCi).

Haddock: a Haskell Documentation Tool

Haddock generates documentation from annotated Haskell source code (typically libraries).

So that they are taken into account by Haddock, comments above function definitions should start with {- |, and those next to parameter types with -- ^.

Example of use:

-- |The 'square' function squares an integer.
-- It takes one argument, of type 'Int'. square :: Int -> Int
square x = x * x

{-|
 The 'cube' function cubes an integer.
 It takes one argument, of type 'Int'.
 -}
cube x = x * square x

data T a b
  = C1 a b  -- ^ This is the documentation for the 'C1' constructor
  | C2 a b  -- ^ This is the documentation for the 'C2' constructor

See this page for more information regarding markup.

Index

They start at zero:

[1,2,3,4] !! 1 = 2

Whitespaces

One should avoid tabulations (i.e. prefer spaces).

Generally the least number of spaces is preferred; like in: sum $ map sqrt [1..10].

Naming

The names of functions and arguments start with a lowercase character and are followed by any number of: numbers, letters (of any case), underscores and single quotes.

The names of types and constructors start with an uppercase letter.

Shortness

Most Haskell developers seem to strongly dislike typing, often resulting in cryptic names for functions (ex: fst) and variable names (often reduced to a single character whose meaning is never disclosed).

A lot of efforts went especially to save keystrokes and more precisely to remove as much as possible the need for parentheses (function application being denoted as a space, the . and $ operators being introduced, etc.). This allows very compact definitions of functions out of functions (ellipsing values as such), and an increased expressivity, sometimes at the expense of clarity. Extra documentation may alleviate this problem.

Single-letter variable names often denote their type (ex: c for a Char variable), and are suffixed by s to indicate this is a list thereof (ex: bs for a variable of type [Bool], css for a [[Char]] one).

Layout & Indentation

Indentation matters, as spaces denote scopes:

a = b + c
 where
  b = 1
  c = 2

d = a * 2

An alternative layout based on curly braces and semi-colons exists, yet its use is discouraged.

A function body shall be indented of at least one space compared to the function name (if indented at all).

As any where or let use must be, indentation-wise, between the name and the body of a function, we prefer, compared to the function name:

• a 2-space indentation for the body
• a 1-space indentation for where / let body

For example:

square x =
  sq
 where sq = x * x

Installing Haskell

On Arch Linux (see this page for more information): pacman -Sy ghc cabal-install stack.

See also our corresponding script for continuous integration.

Running Haskell

Except for performances, programs can be tested directly with ghci, like in:

$ ghci Foobar.hs

The very essential GHCi commands are:

• :? or :help: lists available commands
• :load FILENAME: loads specified script
• :reload or :r: reloads the current module, file, or project
• :: repeats the previous command
• :type or :t: returns the type of specified expression (value or function); ex: :t not False
• set editor NAME: sets the code editor to NAME
• edit FILENAME: edits specified script
• edit: edits current script
• :quit or CTRL-D: quits the interpreter

For example:

$ ghci
GHCi, version 8.10.5: https://www.haskell.org/ghc/  :? for help

Prelude> :type not
not :: Bool -> Bool

Functions can be directly redefined:

Prelude> fac n = product [1..n]
Prelude> fac 5
120

Prelude> fac _ = 0
Prelude> fac 5
0

Haskell-related Filenames

ELF 64-bit LSB relocatable, x86-64, version 1 (SYSV), not stripped

ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 4.4.0, BuildID[sha1]=[...], not stripped

linux-vdso.so.1
libHSbase-4.14.2.0-ghc8.10.5.so => /usr/lib/ghc-8.10.5/base-4.14.2.0/libHSbase-4.14.2.0-ghc8.10.5.so
libHSinteger-gmp-1.0.3.0-ghc8.10.5.so => /usr/lib/ghc-8.10.5/integer-gmp-1.0.3.0/libHSinteger-gmp-1.0.3.0-ghc8.10.5.so
libHSghc-prim-0.6.1-ghc8.10.5.so => /usr/lib/ghc-8.10.5/ghc-prim-0.6.1/libHSghc-prim-0.6.1-ghc8.10.5.so
libHSrts-ghc8.10.5.so => /usr/lib/ghc-8.10.5/rts/libHSrts-ghc8.10.5.so
libgmp.so.10 => /usr/lib/libgmp.so.10
libc.so.6 => /usr/lib/libc.so.6
libm.so.6 => /usr/lib/libm.so.6
librt.so.1 => /usr/lib/librt.so.1
libdl.so.2 => /usr/lib/libdl.so.2
libffi.so.7 => /usr/lib/libffi.so.7
libpthread.so.0 => /usr/lib/libpthread.so.0
/lib64/ld-linux-x86-64.so.2 => /usr/lib64/ld-linux-x86-64.so.2

Build System

One may rely on the Haskell transposition of our simple, usual make-based build system (refer to the GNUmake* files; see this section of our Erlang-based Myriad counterpart for more details).

To Learn

We would certainly recommend browsing the pleasant Learn You a Haskell for Great Good! website or, even better, buying their book; another worthwhile book is Programming in Haskell, whose author is Graham Hutton, that we found interesting and well-written as well.

Of course the official Haskell website is also of interest.

Cheat Sheets

See Justin Bailey's one.