# There are Only Functions! (Optional)

## 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

### Tuples

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

` tp = mkTup 1 "2" [3]`

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

` 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 : []

` 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

` ls = cons 1 (...)`

= \c -> c 1 (...)

`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`

`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)`

` lst = x:xs`

`(:)`

is` lst = (\x xs -> \c -> c x xs) x xs`

= \c -> c x xs

` 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)

` 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 []

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

`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`

`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

` 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

` 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

` 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

` mult n m = sum (replicate n m)`

### 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.#### Functional Programming in Haskell: Supercharge Your Coding

## Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.

You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education