cse130
https://ucsd-cse130.github.io/wi21/lectures/02-haskell.html
FixPOINT COMBINATOR Haskell Crash Course Part I
From the Lambda Calculus to Haskell
1 of 31
1/19/21, 8:51 AM
Recursion
What is Haskell?
A typed, lazy, purely functional programming language
Haskell = ¦Ë-calculus ++
better syntax i I types
Two
NE TWO
if x
f f x
ONE IfXsf
cse130
I
https://ucsd-cse130.github.io/wi21/lectures/02-haskell.html
2
2 of 31
1/19/21, 8:51 AM
built-in features
booleans, numbers, characters
DO
Ttype
records (tuples) lists
recursion
…
Programming in Haskell Xx D
Computation by Calculation
Substituting equals by equals
apple
apple
2351 11
11
20
5
4
5
51 11
ENRON
cse130 https://ucsd-cse130.github.io/wi21/lectures/02-haskell.html
Computation via Substituting Equals by Equals
(1+3)*(4+5) ==> 4*(4+5) ==> 4*9
==> 36
— subst 1 + 3 = 4
— subst 4 + 5 = 9
— subst 4 * 9 = 36
Computation via Substituting Equals by Equals
Equality-Substitution enables Abstraction via Pattern Recognition
3 of 31 1/19/21, 8:51 AM
cse130
https://ucsd-cse130.github.io/wi21/lectures/02-haskell.html
4 of 31
1/19/21, 8:51 AM
Abstraction via Pattern Recognition
Repeated Expressions
r 3
Recognize Pattern as ¦Ë-function
pat = \x y z -> x * ( y + z )
Equival1ent Haskell Definition
pat x y z = x * ( y + z )
Function Call is Pattern Instance
I
pat701295=*>70*(12+95)=*>70*107=*>7490 pat906812=*>90*(68+12)=*>90*80 =*>7200
Key Idea: Computation is substitute equals by equals. mm
Hyz
31*(42+56) 70*(12+95) 90*(68+12)
pat314256=*>31*(42+56)=*>31*98 =*>3038
CSEZON
Reg FRAMES
105 1312
pat x y pat K
pat
payt
2
y
x Cytz IZ
n
Lytle
a
y ten Htt ix yz.sn Cytc
cse130 https://ucsd-cse130.github.io/wi21/lectures/02-haskell.html
Programming in Haskell
Substitute Equals by Equals
Thats it! (Do not think of registers, stacks, frames etc.) S
Elements of Haskell
TR1NlTY
sYftwriFM.i.int
5 of 31 1/19/21, 8:51 AM
cse130
https://ucsd-cse130.github.io/wi21/lectures/02-haskell.html
6 of 31
1/19/21, 8:51 AM
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 … mypy
weirdo = 1 0 — rejected by GHC
Ig
Dropbox mypy google
statically
late8osleary90s
Java
CA
TSI 1 Flow
Helps with program design
Types are contracts (ignore ill-typed inputs!) Catches errors early
Allows compiler to generate code
Enables compiler optimOizations
reetfh.EE
2000g JsPythontruby
Why are types good?
Source
qqypEk oaptuG X86ASM
file
2010 2020 SORBET
Stripe
1
cse130 https://ucsd-cse130.github.io/wi21/lectures/02-haskell.html
haskell
The Haskell Eco-System
Batch compiler: ghc Compile and run large programs
Interactive Shell ghci Shell to interactively run small programs online
(https://repl.it/languages/haskell)
Build Tool stack Build tool to manage libraries etc.
01
Interactive Shell: ghci $ stack ghci
:load file.hs :type expression :info variable
7 of 31 1/19/21, 8:51 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/02-haskell.html
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
. . .
type
annot
8 of 31 1/19/21, 8:51 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/02-haskell.html
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’ es
ex4 :: Bool
ex4 = True
ex5 :: Bool
ex5 = False
— ‘a’, ‘b’, ‘c’, etc. built-in `Char` valu
— True, False are builtin Bool values
QUIZ: Basic Operations
9 of 31 1/19/21, 8:51 AM
cse130
QUIET https://ucsd-cse130.github.io/wi21/lectures/02-haskell.html
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!
10 of 31
1/19/21, 8:51 AM
QUIZ: Basic Operations
cse130 https://ucsd-cse130.github.io/wi21/lectures/02-haskell.html
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!
ez 8T
if e then ez else es 8T
OoBool ez8T
E
ill
Function Types
sensibletype
has
In Haskell, a function is a value that has a type A->B
no
typed
11 of 31
1/19/21, 8:51 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/02-haskell.html
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 -> … )
A Ix
B
e
Multiple Argument Functions
A function that
takes three inputs A1 , A2 and A3
returns one output B has the type A1->A2->A3->B
12 of 31 1/19/21, 8:51 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/02-haskell.html
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
13 of 31 1/19/21, 8:51 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/02-haskell.html
Function Calls
A function call is exactly like in the ¦Ë-calculus funcarg
e1 e2
where e1 is a function and e2 is the argument. For example
>>> isPos 12
True
>>> isPos (0 – 5)
False
Multiple Argument Calls
14 of 31 1/19/21, 8:51 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/02-haskell.html
With multiple arguments, just pass them in one by one, e.g.
(((e e1) e2) e3)
For example
>>>pat314256 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
15 of 31 1/19/21, 8:51 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/02-haskell.html
EXERCISE
Write a function sumTo such that sumTo n evaluates to 0 + 1 + 2 + … + n sumTo :: Int -> Int
sumTo n = ???
When you are done you should see the following behavior:
>>> sumTo 3
6
>>> sumTo 4
10
>>> sumTo 5 15
16 of 31 1/19/21, 8:51 AM