Skip main navigation

Hurry, only 5 days left to get one year of Unlimited learning for £249.99 £174.99. New subscribers only. T&Cs apply

Find out more

Key Constructs and Functions in Haskell

In this video, Wim Vanderbauwhede explains how key constructs in a functional language are really just syntactic sugar over lambda functions.

In a Functional Language, There are Only Functions

Although it might seems that a language like Haskell has a lot of different objects and constructs, we can express all of them in terms of functions. Watch the video to get a little insight, then read on to find out more …

Variables and let

 

 let
 n = 10
 f x = x+1
 in
 f n

-- One variable per let => 

 let
 n = 10
 in
 let 
 f x = x+1
 in
 f n

-- Rewrite f as lambda =>
 
 let
 n = 10
 in
 let 
 f = x -> x+1
 in
 f n


-- Rewrite inner let as lambda =>

 let
 n = 10
 in
 (f -> f n) (x -> x+1) 

-- Rewrite outer let as lambda =>

 ( n -> ((f -> f n) ( x -> x+1 )) ) 10 

 

So variables and let expressions are just syntactic sugar for lambda expressions.

 

Tuples

 

 tp = (1,"2",[3])

 

The tuple notation is syntactic sugar for a function application:

 

 tp = mkTup 1 "2" [3]

 

The tuple construction function can again be defined purely using lambdas:

 

 mkTup = x y z -> t -> t x y z

 

The same goes for the tuple accessor functions:

 

 fst tp = tp (x y z -> x)
 snd tp = tp (x y z -> y)

 

Lists

 

Lists can be defined in terms of the empty lists [] and the cons operation (:).

 

 ls = [1,2,3]

Rewrite using : and [] =>

 ls = 1 : 2 : 3 : []

 

Or using cons =>

 

 ls = cons 1 (cons 2 (cons 3 []))

 

Defining cons

 

We can define cons using only lambda functions as

 

 cons = x xs ->
 c -> c x xs

 

Thus

 

 ls = cons 1 (...)
 = c -> c 1 (...)

 

We can also define head and tail using only lambdas:

 

 head ls = ls (x y -> x)
 tail ls = ls (x y -> y)

 

The empty list

 

We can define the empty list as follows:

 

 [] = f -> true

 

The definitions for true and false are given below under Booleans.

 

Then we can check if a list is empty or not:

 

 isEmpty lst = lst (x xs -> false)

 

A non-emptylist is always defined as:

 

 lst = x:xs

 

which with our defintion of (:) is

 

 lst = (x xs -> c -> c x xs) x xs
 = c -> c x xs

 

Thus,

 

 isEmpty lst
 = isEmpty (c -> c x xs)
 = (c -> c x xs) (x xs -> false)
 = false

 isEmpty []
 = isEmpty (f -> true)
 = (f->true) (x xs -> false)
 = true

 

Recursion on lists

 

Now that we can test for the empty list we can define recursions on lists such as foldl, map etc.:

 

 foldl f acc lst =
 if isEmpty lst
 then acc
 else foldl f (f (head lst) acc) (tail lst)

 

and

 

 map f lst =
 let
 map' f lst lst' = if isEmpty lst then (reverse lst') else map' f (tail lst) (head lst: lst')
 in
 map' f lst []

 

with

 

 reverse lst = (foldl (acc elt -> (elt:acc)) [] lst

 

The definitions of foldl and map use an if-then-else expression which is defined below under Conditionals.

 

 List concatenation

 

 (++) lst1 lst2 = foldl (acc elt -> (elt:acc)) lst2 (reverse lst1)

 

 The length of a list

 

To compute the length of a list we need integers, they are defined below.

 

 length lst = foldl calc_length 0 lst
 where
 calc_length _ len = inc len

 

Conditionals

 

We have used conditionals in the above expressions:

 

 if cond then if_true_exp else if_false_exp

 

Here cond is an expression returning either true or false, these are defined below.

 

We can write the if-then-else clause as a pure function:

 

 ifthenelse cond if_true_exp if_false_exp

 

Booleans

 

To evaluate the condition we need to define booleans:

 

 true = x y -> x
 false = x y -> y

 

With this definition, the if-then-else becomes simply

 

 ifthenelse cond if_true_exp if_false_exp = cond if_true_exp if_false_exp

 

Basic Boolean operations: and, or and not

 

Using ifthenelse we can define and, or and not:

 

 and x y = ifthenelse x (ifthenelse y true) false
 or x y = ifthenelse x true (ifthenelse y true false)
 not x = ifthenelse x false true

 

Boolean equality: xnor

 

We note that to test equality of Booleans we can use xnor, and we can of course define xor in terms of and, or and not:

 

 xor x y = (x or y) and (not x or not y)

 

 xnor x y = not (xor x y)

 

Signed Integers

 

We define an integer as a list of booleans, in thermometer encoding, and with the following definitions:

 

We define usigned 0 as a 1-element list containing false. To get signed integers we simply define the first bit of the list as the sign bit. We define unsigned and signed versions of 0:

 

 u0 = false:[]
 0 = +0 = true:u0
 -0 = false:u0

 

For convenience we define also:

 

 isPos n = head n
 isNeg n = not (head n)
 isZero n = not (head (tail n))
 sign n = head n

 

Integer equality

 

The definition of 0 makes the integer equality (==) easier:

 

 (==) n1 n2 = let
 s1 = head n1
 s2 = head n2
 b1 = head (tail n1)
 b2 = head (tail n2)
 if (xnor s1 s2) then
 if (and (not b1) (not b2))
 then true
 else
 if (and b1 b2)
 then (==) (s1:(tail n1)) (s2:(tail n2))
 else false
 else false

 

Negation

 

We can also easily define negation:

 

 neg n = (not (head n)):(tail n)

 

Increment and Decrement

 

For convenience we define also define increment and decrement operations:

 

 inc n = if isPos n then true:true:(tail n) else if isZero n then 1 else false:(tail (tail n))
 dec n = if isZero n then -1 else if isNeg n then false:true:(tail n) n else true:(tail (tail n))

 

Addition and Subtraction

 

General addition is quite easy:

 

 add n1 n2 = foldl add_if_true n1 n2
 where
 add_if_true elt n1 = if elt then true:n1 else n1

 

In the same way, subtraction is also straightforward:

 

 sub n1 n2 = foldl sub_if_true n1 n2
 where
 sub_if_true elt n1 = of elt then (tail n1) else n1

 

Multiplication

 

An easy way to define multiplication is by defining the replicate and sum operations:

 

 replicate n m =
 let
 repl n m lst = if n==0 then lst else repl (dec n) m (m:lst)
 in
 repl n m []

 sum lst = foldl add 0 lst

 

Then multiplication simply becomes

 

 mult n m = sum (replicate n m)

In a similar way integer division and modulo can be defined.

Floats, Characters and Strings

We note that floats and chars use an integer representation, and strings are simply lists of chars. So we now have a language that can manipulate lists and tuples of integers, floats, chars and strings.

This article is from the free online

Functional Programming in Haskell: Supercharge Your Coding

Created by
FutureLearn - Learning For Life

Reach your personal and professional goals

Unlock access to hundreds of expert online courses and degrees from top universities and educators to gain accredited qualifications and professional CV-building certificates.

Join over 18 million learners to launch, switch or build upon your career, all at your own pace, across a wide range of topic areas.

Start Learning now