cse230

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

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

Equivalent Haskell Definition

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

Function Call is Pattern Instance

pat 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

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
x_1 = expr_1

x_2 :: type_2
x_2 = expr_2

.
.
.

Basic Types

ex1 :: Int
ex1 = 31 * (42 + 56)   -- this is a comment

ex2 :: Double
ex2 = 3 * (4.2 + 5.6)  -- arithmetic operators "overloaded"

ex3 :: Char
ex3 = 'a'              -- 'a', 'b', 'c', etc. built-in `Char` values

ex4 :: Bool
ex4 = True             -- True, False are builtin Bool values

ex5 :: Bool
ex5 = False

QUIZ: Basic Operations

ex6 :: Int
ex6 = 4 + 5

ex7 :: Int
ex7 = 4 * 5

ex8 :: Bool
ex8 = 5 > 4

quiz :: ???
quiz = if ex8 then ex6 else ex7

What is the type of quiz?

A. Int

B. Bool

C. Error!

QUIZ: Basic Operations

ex6 :: Int
ex6 = 4 + 5

ex7 :: Int
ex7 = 4 * 5

ex8 :: Bool
ex8 = 5 > 4

quiz :: ???
quiz = if ex8 then ex6 else ex7

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
isPos = \n -> (x > 0)

Define function-expressions using \ like in λ-calculus!

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

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

(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
pat = \x y z -> x * (y + z)

which we can write with the params on the left as

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

QUIZ

What is the type of quiz ?

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

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 :: ???
tup1 = ('a', 5)

tup2 :: (Char, Double, Int)
tup2 = ('a', 5.2, 7)

QUIZ

What is the type ??? of tup3?

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

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 …

tup = (e1, e2, e3)

… but how to extract the values from this tuple?

Pattern Matching

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

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

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

QUIZ

What is the value of quiz defined as

tup2 :: (Char, Double, Int)
tup2 = ('a', 5.2, 7)

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

quiz = snd3 tup2

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]
chars = ['a','b','c']

ints :: [Int]
ints = [1,3,5,7]

pairs :: [(Int, Bool)]
pairs = [(1,True),(2,False)]

QUIZ

What is the type of things defined as

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

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

oops = [1, 2, 'c']

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
    h:t    -- creates a list with "head" 'h' and "tail" t

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

clone 3 100
  =*> ???

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
mystery []     = 0
mystery (x:xs) = 1 + mystery xs

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

From the Lambda Calculus to Haskell

Programming in Haskell

Computation via Substituting Equals by Equals

Computation via Substituting Equals by Equals

Abstraction via Pattern Recognition

Programming in Haskell

Elements of Haskell

The Haskell Eco-System

Interactive Shell: ghci

A Haskell Source File

Basic Types

QUIZ: Basic Operations

QUIZ: Basic Operations

Function Types

Multiple Argument Functions

QUIZ

Function Calls

Multiple Argument Calls

EXERCISE

How to Return Multiple Outputs?

Tuples

QUIZ

Extracting Values from Tuples

QUIZ

Lists

QUIZ

List’s Values Must Have The SAME Type!

Constructing Lists

Functions Producing Lists

PRACTICE: Clone

How does clone execute?

EXERCISE: Range

Functions Consuming Lists

Example

QUIZ

EXERCISE: Summing a List

Recap

Interactive Shell: `ghci`

How does `clone` execute?