foo bar
f (3+4, div(4, 2))
f (7, div(4, 2))
f (7, 2)
7
f (3+4, div(1, 0))
f (7, div(1, 0))
☹
take 3 [a,b,c,d,e] = [a,b,c]
take 3 [a,b] = [a,b]
take 0 _ = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs
doITerminate = take 2 (from 0)
where
from n = n : from (n + 1)
doIEvenMakeSense = take 2 zs
where
f (foo, bar) f
eval a parameter, arithmetic
eval the other parameter, arithmetic
ready to plug in at last
eval a parameter, arithmetic
eval the other parameter, arithmetic
take
zs = 0 : zs
— At low level this is one node pointing back to itself. O(1)-space.
Table of Contents
:siht ekil seog noitatnemelpmi ehT .elbaliava sa ynam sa ro ,tsil tupni eht fo smeti n tsrfi eht lareneg nI
eht etaulave ,ydob s’ etaulave ,”
.ydob otni gulp neht ,)egaugnal eht no sdneped tsrfi eno hcihw( tsrfi dna
:siht ekil sevaheb taht ” “ noitcnuf tsil a sah yrarbil dradnats ehT .tsrfi uoy htiw ssem em teL
)deen yb llac .a.k.a( noitaulave yzaL
:desunu eb dluow ti fi neve noitpecxe/rorre na esuac nac retemarap citamelborp A
😡 = )y ,x(f sa denfied noitcnuf a si ereht fI :elpmaxE
“ etaulave oT :redro noitaulave rof ”eulav yb llac“ esu segaugnal tsoM
eulav yb llaC redrO noitaulavE
sh.lavElleksaH ni
?etanimret gniwollof eht oD
→ →
→ → →
f foo bar
f
foo + bar
const x y = x
const (3+4) (div 1 0)
const (3+4) (div 1 0)
3+4
7
doITerminate
plug in
arithmetic
take 2 (from 0)
take 2 (0 : from (0 + 1))
0 : take (2-1) (from (0 + 1))
0 : take 1 (from (0 + 1))
0 : take 1 (n : from (n + 1))
with n = 0 + 1
0 : n : take (1-1) (from (n + 1))
with n = 0 + 1
0 : n : take (1-1) (from (n + 1))
with n = 1
0 : 1 : take (1-1) (from (1 + 1))
0 : n : take 0 (from (n + 1))
with n = 1
0 : 1 : []
eval “from 0” for pattern matching
match, plug in
eval “2-1” for pattern matching
eval “from (0 + 1)” for pattern matching
match, plug in
eval 2nd element n for printing
eval “1-1” for pattern matching
match, plug in
(may as well inline n if it appears only once)
Table of Contents
.ypoc emas eht ot gnitniop sretniop owt :hparg a ward osla dluoc uoY .eciwt ot derrefer ”1 + 0“ fo ypoc derahs eno snaem ”1 + 0 = n htiw“ yM :etoN
tnirp ot sdeen LPER eht nehw ,g.e—detnirp ylluf si rewsna eht litnu(
).orez yb gnidivid tuoba rorre oN(
.eulav-yb-llac :”
sah yrarbil dradnats ehT :elpmaxe citsard yreV “ .g.e snoitarepo citemhtira etaulave oT
).”rorre“ aka ”denfiednu“ eralced ,snrettap fo tuo nur fI( .nrettap txen eht yrt ,hctam-non fI .etaulave dna SHR otni gulp ,hctam fI .hctam-non ro hctam a s’ti rehtehw ediced ot hguone tsuj )s(retemarap etaulave :gnihctam nrettap otni uoy snur taht fI
.noitacilpud on ,ypoc derahs emas :semit elpitlum retemarap emas eht ot srefer SHR fI .taht etaulave neht ,tsrfi SHR s’ otni gulp :” “ etaulave oT
noitaulavE yzaL gnisU
.uoy ot pu s’tI etirw ylpmis dna ti fo dir teg ot KO s’ti ,elpmis os si ”1 = n“ :etoN
: fo noitaulavE
:)hcteks( lleksaH ni noitaulave yzaL
:)tluser lluf eht fo noitaulavE
→ →
→
→
→ → → →
→ →
x1 = x – f(x)/f'(x)
= x – (x^3 – b)/(3x^2)
= x – (x – b/x^2)/3
= (2x + b/x^2)/3
cubeRoot b = within 0.001 (iterate next b)
— From the standard library:
— iterate f z = z : iterate f (f z)
— = [z, f z, f (f z), f (f (f z)), …]
where
next x = (2*x + b/x^2) / 3
within eps (x : x1 : rest)
| abs (x – x1) <= eps = x1
| otherwise = within eps (x1 : rest)
cubeRoot = within 0.001 . iterate next
(.)
Table of Contents
.esruocfo,nworuoyekam-motsucotevahuoysemitemoS yna ,ro ,lla ,dna ,muminim ,mumixam ,tcudorp ,mus ,htgnel ,'ldlof ,ldlof ,rdlof :sremusnoC
piznu ,htiWpiz ,piz ,noititrap ,kaerb ,naps ,elihWpord ,elihWekat ,tAtilps ,pord ,ekat )semitemos ,oot rdlof( ,rnacs ,lnacs ,retlfi ,pam :srecudsnarT
)oTmorFmune ,morFmune yb dekcab( noitaton ]y..x[ ,]..x[ eht ,rdlofnu ,etareti ,etacilper ,elcyc ,taeper :srecudorP
:segats enilepip fo smret ni kniht uoy nehw ro ,spool-rof sa ylizal stsil esu uoy nehw snoitcnuf tsil elbaton yrev emoS
.segaugnal thgir eht htiw—tneicffie erom dna enas erom htob si segats enilepip level-hgih ni gniknihT
.daehrevo CG dna noitacolla edon tuohtiw sretsiger ni yleritne tfi neve nac ti ,)edoc ruoy ezimitpo nac relipmoc eht fi( ykcul er'uoy eromrehtruf fI .ecaps-)1(O neve si ti ,ylluferac ti od uoy fI .segats enilepip emoceb snoitcnuf gnissecorp-tsil nehT .spool-rof naht pool-rof retteb a—erutcurts lortnoc tnellecxe na si ti ,lleksaH ni ylizal tsil esu uoy fi ,revewoH
.gnorw ti gniod er'uoy ”meti hti eht“ rof ksa uoy fi dnA .)segaugnal lla( erutcurts atad gnimusnoc-ecaps yrev a si tsil deknil-ylgniS
.senilepip xinU ekil enilepip a evah yllaer uoy ,siht htiW
rotarepo noitisopmoc noitcnuf eht gnisu ,yltnelaviuqE sh.lavElleksaH ni
.x morf 1x gnitupmoc rof elbisnopser si woleb ”txen“ noitcnuf lacol ehT
.b fo toor ebuc ,.e.i ,0 = b - 3x evlos yletamixorppA .»srettam PF yhw« s'sehguH ni ekiL .stsil yzal htiw dohtem s'notweN
2x3 = )x('f ,b - 3x = )x(f oS
mySumV2
mySumV2 xs = g 0 xs
where
g accum [] = accum
g accum (x:xs) = g (accum + x) xs
mySumV2 [1,2,3]
mySumV2 (1 : 2 : 3 : [])
g 0 (1 : 2 : 3 : [])
g (0 + 1) (2 : 3 : [])
g ((0 + 1) + 2) (3 : [])
g (((0 + 1) + 2) + 3) []
((0 + 1) + 2) + 3
(1 + 2) + 3 3 + 3
6
foldl (+) 0 [1,2,3]
plug in
match, plug in
match, plug in
match, plug in
match, plug in
arithmetic at last
ditto
ditto
mySumV1 [1,2,3]
mySumV1 [] = 0
mySumV1 (x:xs) = x + mySumV1 xs
seq x y x
seq x y
seq
foldr (+) 0 [1,2,3]
y
seq
x
y
Table of Contents
ot
ro )woleb denfied(
fo noitaulave eht hguorht oG :esicrexE .citemhtira denoptsop eht rof ecaps )n(Ω sekat sihT →
yzal gnillik rof ”
.elbatiusnu ti meed uoy erehw noitaulave “ si erehT .rotalumucca eht rof noitaulave yzal deen ton seod tsil a gnimmuS
.deen lliw
:ssenizal rotalumucca llik ot gnisu mhtirogla gnimmus a si ereH taht gnihtemos si nehw lufgninaem tsom si ” “ ,yllarutaN
adbmal a evah uoy litnu :snoitcnuf rof rotcurtsnoc atad a evah uoy litnu :sepyt atad ciarbegla rof rebmun eht evah uoy litnu :sepyt rebmun ni-tliub rof
:snaem )FNHW( mrof lamron daeh kaeW . htiw eunitnoc neht ,”mrof lamron daeh kaew“ ot etaulave :” “ etaulave oT
.yenruoj tnereffid a hguorht hguoht ,ecaps )n(Ω sekat osla ti woh ees
🙂
ylralimis(
fo noitaulavE sh.lavElleksaH ni
rotalumucca na dna pool-elihw a sa noitcnuf repleh a gnisu tsil a mus ot
:retemarap enfieD
struh noitaulave yzal nehW
.oot tol a spleh noisneherpmoc tsil taht tegrof t'nod dnA
sh.lavElleksaH ni
→ → → → → → →
mySumV3 xs = g 0 xs
where
g accum [] = accum
g accum (x:xs) = seq accum (g (accum + x) xs)
-- Note: accum is something that "g (accum + x) xs" will need.
g 0 (1 : 2 : 3 : [])
seq 0 (g (0 + 1) (2 : 3 : []))
g (0 + 1) (2 : 3 : [])
seq a (g (a + 2) (3 : []))
with a = 0 + 1
seq a (g (a + 2) (3 : []))
with a = 1
g (1 + 2) (3 : [])
seq b (g (b + 3) [])
with b = 1 + 2
seq b (g (b + 3) [])
with b = 3 g (3 + 3) [] 3+ 3
6
Data.List foldl'
foldl' f z [] = z
foldl' f z (x:xs) = seq z (foldl' f (f z x) xs)
mySumV4 xs = g 0 xs
where
g accum (x:xs) = let a1 = accum + x
in seq a1 (g a1 xs)
-- Note: a1=accum+x is something that "g a1 xs" will need.
g 0 (1 : 2 : 3 : [])
seq b (g b (2 : 3 : []))
with b = 0 + 1
seq b (g b (2 : 3 : []))
with b = 1
g 1 (2 : 3 : [])
seq c (g c (3 : []))
with c = 1 + 2
seq c (g c (3 : []))
with c = 3
g 3 (3 : [])
seq d (g d [])
with d = 3 + 3
seq d (g d [])
with d = 6
assum + x
Table of Contents
.yltpmorp detaulave steg ”
“ taht gniwohs noitaulave elpmaS sh.lavElleksaH ni
:denetsah rehtruf eb nac dna noitareti eno yb citemhtira senoptsop llits evoba eht taht eurt si tI
:llew sa siht rof sah
:pu-dliub decuder hcum gniwohs noitaulave elpmaS sh.lavElleksaH ni
→
→ →
→
→ →
→ →
→ → →
→
→ →
→
→ → →
g 6 [] 6
Table of Contents
→ →