## From the Lambda Calculus to Haskell

## Programming in Haskell

**Computation by Calculation**

*Substituting equals by equals*

## Computation via Substituting Equals by Equals

```
1 + 3) * (4 + 5)
(-- subst 1 + 3 = 4
==> 4 * (4 + 5)
-- subst 4 + 5 = 9
==> 4 * 9
-- subst 4 * 9 = 36
==> 36
```

## Computation via Substituting Equals by Equals

**Equality-Substitution** enables **Abstraction** via **Pattern Recognition**

## Abstraction via Pattern Recognition

**Repeated Expressions**

```
31 * (42 + 56)
70 * (12 + 95)
90 * (68 + 12)
```

**Recognize Pattern as λ-function**

`= \x y z -> x * ( y + z ) pat `

**Equivalent Haskell Definition**

`= x * ( y + z ) pat x y z `

**Function Call is Pattern Instance**

```
31 42 56 =*> 31 * (42 + 56) =*> 31 * 98 =*> 3038
pat 70 12 95 =*> 70 * (12 + 95) =*> 70 * 107 =*> 7490
pat 90 68 12 =*> 90 * (68 + 12) =*> 90 * 80 =*> 7200 pat
```

**Key Idea:** Computation is *substitute* equals by equals.

## Programming in Haskell

*Substitute Equals by Equals*

Thats it! (*Do not* think of registers, stacks, frames etc.)

## Elements of Haskell

- Core program element is an
**expression** - Every
*valid*expression has a**type**(determined at compile-time) - Every
*valid*expression reduces to a*value*(computed at run-time)

Ill-typed* expressions are rejected at *compile-time* before execution

*like*in Java*not like**λ*-calculus or Python …

## The Haskell Eco-System

**Batch compiler:**`ghc`

Compile and run large programs**Interactive Shell**`ghci`

Shell to interactively run small programs online**Build Tool**`stack`

Build tool to manage libraries etc.

## Interactive Shell: `ghci`

```
$ stack ghci
:load file.hs
:type expression
:info variable
```

## A Haskell Source File

A sequence of **top-level definitions** `x1`

, `x2`

, …

Each has

*type*`type_1`

,`type_2`

, …Each defined by

*expression*`expr_1`

,`expr_2`

, …

```
x_1 :: type_1
= expr_1
x_1
x_2 :: type_2
= expr_2
x_2
.
.
.
```

## Basic Types

```
ex1 :: Int
= 31 * (42 + 56) -- this is a comment
ex1
ex2 :: Double
= 3 * (4.2 + 5.6) -- arithmetic operators "overloaded"
ex2
ex3 :: Char
= 'a' -- 'a', 'b', 'c', etc. built-in `Char` values
ex3
ex4 :: Bool
= True -- True, False are builtin Bool values
ex4
ex5 :: Bool
= False ex5
```

## QUIZ: Basic Operations

```
ex6 :: Int
= 4 + 5
ex6
ex7 :: Int
= 4 * 5
ex7
ex8 :: Bool
= 5 > 4
ex8
quiz :: ???
= if ex8 then ex6 else ex7 quiz
```

What is the *type* of `quiz`

?

**A.** `Int`

**B.** `Bool`

**C.** Error!

## QUIZ: Basic Operations

```
ex6 :: Int
= 4 + 5
ex6
ex7 :: Int
= 4 * 5
ex7
ex8 :: Bool
= 5 > 4
ex8
quiz :: ???
= if ex8 then ex6 else ex7 quiz
```

What is the *value* of `quiz`

?

**A.** `9`

**B.** `20`

**C.** Other!

## Function Types

In Haskell, a **function is a value** that has a type

`A -> B`

A function that

- takes
*input*of type`A`

- returns
*output*of type`B`

For example

```
isPos :: Int -> Bool
= \n -> (x > 0) isPos
```

Define **function-expressions** using `\`

like in *λ*-calculus!

But Haskell also allows us to put the parameter on the *left*

```
isPos :: Int -> Bool
= (x > 0) isPos n
```

(Meaning is **identical** to above definition with `\n -> ...`

)

## Multiple Argument Functions

A function that

- takes three
*inputs*`A1`

,`A2`

and`A3`

- returns one
*output*`B`

has the type

`A1 -> A2 -> A3 -> B`

For example

```
pat :: Int -> Int -> Int -> Int
= \x y z -> x * (y + z) pat
```

which we can write with the params on the *left* as

```
pat :: Int -> Int -> Int -> Int
= x * (y + z) pat x y z
```

## QUIZ

What is the type of `quiz`

?

```
quiz :: ???
= (x + y) > 0 quiz x y
```

**A.** `Int -> Int`

**B.** `Int -> Bool`

**C.** `Int -> Int -> Int`

**D.** `Int -> Int -> Bool`

**E.** `(Int, Int) -> Bool`

## Function Calls

A function call is *exactly* like in the *λ*-calculus

` e1 e2`

where `e1`

is a function and `e2`

is the argument. For example

```
>>> isPos 12
True
>>> isPos (0 - 5)
False
```

## Multiple Argument Calls

With multiple arguments, just pass them in one by one, e.g.

` (((e e1) e2) e3)`

For example

```
>>> pat 31 42 56
3038
```

## EXERCISE

Write a function `myMax`

that returns the *maximum* of two inputs

```
myMax :: Int -> Int -> Int
= ??? myMax
```

When you are done you should see the following behavior:

```
>>> myMax 10 20
20
>>> myMax 100 5
100
```

## How to Return Multiple Outputs?

## Tuples

A type for packing `n`

different kinds of values into a single “struct”

`T1,..., Tn) (`

For example

```
tup1 :: ???
= ('a', 5)
tup1
tup2 :: (Char, Double, Int)
= ('a', 5.2, 7) tup2
```

## QUIZ

What is the type `???`

of `tup3`

?

```
tup3 :: ???
= ((7, 5.2), True) tup3
```

**A.** `(Int, Bool)`

**B.** `(Int, Double, Bool)`

**C.** `(Int, (Double, Bool))`

**D.** `((Int, Double), Bool)`

**E.** `(Tuple, Bool)`

## Extracting Values from Tuples

We can **create** a tuple of three values `e1`

, `e2`

, and `e3`

…

`= (e1, e2, e3) tup `

… but how to **extract** the values from this tuple?

**Pattern Matching**

```
fst3 :: (t1, t2, t3) -> t1
= x1
fst3 (x1, x2, x3)
snd3 :: (t1, t2, t3) -> t2
= x2
snd3 (x1, x2, x3)
thd3 :: (t1, t2, t3) -> t3
= x3 thd3 (x1, x2, x3)
```

## QUIZ

What is the value of `quiz`

defined as

```
tup2 :: (Char, Double, Int)
= ('a', 5.2, 7)
tup2
snd3 :: (t1, t2, t3) -> t2
= x2
snd3 (x1, x2, x3)
= snd3 tup2 quiz
```

**A.** `'a'`

**B.** `5.2`

**C.** `7`

**D.** `('a', 5.2)`

**E.** `(5.2, 7)`

## Lists

Unbounded Sequence of values of type `T`

`T] [`

For example

```
chars :: [Char]
= ['a','b','c']
chars
ints :: [Int]
= [1,3,5,7]
ints
pairs :: [(Int, Bool)]
= [(1,True),(2,False)] pairs
```

## QUIZ

What is the type of `things`

defined as

```
things :: ???
= [ [1], [2, 3], [4, 5, 6] ] things
```

**A.** `[Int]`

**B.** `([Int], [Int], [Int])`

**C.** `[(Int, Int, Int)]`

**D.** `[[Int]]`

**E.** `List`

## List’s Values Must Have The SAME Type!

The type `[T]`

denotes an unbounded sequence of values of type `T`

Suppose you have a list

`= [1, 2, 'c'] oops `

There is no `T`

that we can use

- As last element is not
`Int`

- First two elements are not
`Char`

!

**Result: Mysterious Type Error!**

## Constructing Lists

There are two ways to construct lists

```
-- creates an empty list
[] :t -- creates a list with "head" 'h' and "tail" t h
```

For example

```
>>> 3 : []
3]
[
>>> 2 : (3 : [])
2, 3]
[
>>> 1 : (2 : (3 : []))
1, 2, 3] [
```

**Cons Operator** `:`

**is Right Associative**

`x1 : x2 : x3 : x4 : t`

means `x1 : (x2 : (x3 : (x4 : t)))`

So we can just avoid the parentheses.

**Syntactic Sugar**

Haskell lets you write `[x1, x2, x3, x4]`

instead of `x1 : x2 : x3 : x4 : []`

## Functions Producing Lists

Lets write a function `copy3`

that

- takes an input
`x`

and - returns a list with
*three*copies of`x`

```
copy3 :: ???
= ??? copy3 x
```

When you are done, you should see the following

```
>>> copy3 5
5, 5, 5]
[
>>> copy3 "cat"
"cat", "cat", "cat"] [
```

## PRACTICE: Clone

Write a function `clone`

such that `clone n x`

returns a list with `n`

copies of `x`

.

```
clone :: ???
= ??? clone n x
```

When you are done you should see the following behavior

```
>>> clone 0 "cat"
[]
>>> clone 1 "cat"
"cat"]
[
>>> clone 2 "cat"
"cat", "cat"]
[
>>> clone 3 "cat"
"cat", "cat", "cat"]
[
>>> clone 3 100
100, 100, 100] [
```

## How does `clone`

execute?

(Substituting equals-by-equals!)

```
3 100
clone =*> ???
```

## EXERCISE: Range

Write a function `range`

such that `range i j`

returns the list of values `[i, i+1, ..., j]`

```
range :: ???
range i j = ???
```

When we are done you should get the behavior

```
>>> range 4 3
[]
>>> range 3 3
3]
[
>>> range 2 3
2, 3]
[
>>> range 1 3
1, 2, 3]
[
>>> range 0 3
0, 1, 2, 3] [
```

## Functions Consuming Lists

So far: how to *produce* lists.

**Next** how to *consume* lists!

## Example

Lets write a function `firstElem`

such that `firstElem xs`

returns the *first* element `xs`

if it is a non-empty list, and `0`

otherwise.

```
firstElem :: [Int] -> Int
= ??? firstElem xs
```

When you are done you should see the following behavior:

```
>>> firstElem []
0
>>> firstElem [10, 20, 30]
10
>>> firstElem [5, 6, 7, 8]
5
```

## QUIZ

Suppose we have the following `mystery`

function

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

What does `mystery [10, 20, 30]`

evaluate to?

**A.** `10`

**B.** `20`

**C.** `30`

**D.** `3`

**E.** `0`

## EXERCISE: Summing a List

Write a function `sumList`

such that `sumList [x1, ..., xn]`

returns `x1 + ... + xn`

```
sumList :: [Int] -> Int
= ??? sumList
```

When you are done you should get the following behavior:

```
>>> sumList []
0
>>> sumlist [3]
3
>>> sumlist [2, 3]
5
>>> sumlist [1, 2, 3]
6
```

## Recap

- Core program element is an
**expression** - Every
*valid*expression has a**type**(determined at compile-time) - Every
*valid*expression reduces to a*value*(computed at run-time)

**Execution**

Basic values & operators

Execution / Function Calls just

*substitute equals by equals*Pack data into

*tuples*&*lists*Unpack data via

*pattern-matching*