\
lambda x : x+1
function (x) { return x+1; }
x => x+1
\x -> x+1
(\y -> 2*x – 3*y)
\x y -> 2*x – 3*y
diffSq x y = (x – y) * (x + y)
diffSq = \x y -> (x – y) * (x + y)
diffSq x = \y -> (x – y) * (x + y)
diffSq 10 5
(diffSq 10) 5
diffSq 10
(\x y -> (x – y) * (x + y)) 10
\y -> (10 – y) * (10 + y)
X -> Y -> A
diffSq 10
\x ->
Table of Contents
tahw si ereh ,detaulave si ti nehW .)”noitacilppa laitrap“( enola ”
:sneppah “ esu elbissop si tI
:sretemarap 2 ot noitcnuf a gniylppa tuoba tahW
reilrae morf llaceR :dnahtrohS .”gniyrruc“ dellac si siht gnioD .retemarap dn2 eht sekat taht noitcnuf a ot
retemarap ts1 eht spam taht noitcnuf a — )dettimo eb nac sesehtnerap esoht(
:noitcnuf detsen a sa ti ledom ot si erutluc lleksaH eht ,sretemarap 2 dnetni uoy fi ,txeN
.λ :adbmal rettel keerG eht ekil skool ti esuaceb nesohc saw
eman a ti gnivig tuohtiw noitcnuf a etirw ot woh = noitcnuf suomynona = adbmal
snoitacilppanoitcnufdetsendna)”gniyrruc“(sadbmaldetseN 1 traP sepyT lleksaH
:esiw-epyT
rof dnahtrohs si
sa nettirw eb nac sihT
neve ro
:lleksaH :tpircsavaJ :nohtyP
→ →
X -> (Y -> A)
(X->Y)->A
atFourPlusAtSeven :: (Integer -> Integer) -> Integer
atFourPlusAtSeven f = f 4 + f 7
atFourPlusAtSeven
atFourPlusAtSeven (\x -> x*2)
atFourPlusAtSeven (diffSq 10) — “diffSq 10” example of partial application
atFourPlusAtSeven (\x -> diffSq x 2)
rep2Integer :: Integer -> [Integer]
rep2Integer x = [x, x]
rep2Integer False
rep2 :: a -> [a]
rep2 x = [x, x]
Integer -> [Integer] rep2Integer 4
a -> [a] a myElementType
a element
rep2 4 rep2 False rep2 “hello”
template
SLL
Table of Contents
.
, ,.g.e ,esac rewol htiw trats ot evah seod tub ,” “ eb ot evah t’nseod ,uoy ot pu era selbairav epyt fo semaN .”retemarap epyt“ ro ”elbairav epyt“ a si ereht ” “ eht ,” “ nI
,dewolla si
?retteb od nac ew ylerus tuB .t’nsi
. ot epyt eht dennip ylirassecennu evah I
).stsil deknil-ylgnis cireneg rof ++C dna avaJ ni dellac epyt a evah I dneterP( :epytotorp ++C :erutangis avaJ
:setalpmet ++C emos ,scireneg }…,tsuR ,alacS ,avaJ{ ot ralimiS .cte , , , :dewolla llA
.]x ,x[ tsil eht sdliub ,x tnemugra regetni na sekat noitcnuf sihT
:noitcnuf redro-rehgih a si noitcnuf gniwollof ehT :elpmaxe yoT .”snoitcnuf redro-rehgih“ yas ew dna ,taht od nac uoy seY .noitcnuf a si retemarap a fi tahw ,.e.i , tuoba ksa larutan s’ti neht dnA
.”retemarap dn2 eht sekat taht noitcnuf ot retemarap ts1 eht spam taht noitcnuf“ llaceR
msihpromylop cirtemaraP
sh.1sepyTlleksaH ni
sh.1sepyTlleksaH ni
:eseht ekil ti gnisu yrT sh.1sepyTlleksaH ni
snoitcnuf redro-rehgiH
rof dnahtrohs si
Bool String
rep2 :: a -> [a]
rep2 :: forall a. a -> [a]
rep2 False
rep2 “hello”
rep2
[Bool] String->[String]
rep2wrong :: a -> [a]
rep2wrong x = [False, True]
a
xyx :: a -> a -> [a]
xyx x y = [x, y, x]
xyx 4 False
facetious x =
if x :: Integer, then
a=Bool
a=String
rep2Integer
Integer->[Integer] Bool->
Bool a
rep2wrong
a
a
if x>5, the answer is [x-1, x+1, x^2, x*x]
else the answer is [x, x+3]
else if x :: Bool, then
the answer is [x, not x]
else
the answer is [x, x]
Table Ionf Cteogneternts
:)nwohs edocoduesp( ,.g.e ,epyt yb ruoivaheb yrav tonnaC :elbixeflnI
:secneuqesnoC .sesoohc resu eht tahw dlot ton si redivorp eht :snaem trap ”cirtemarap“ eht—”msihpromylop cirtemaraP“
.noitanalpxe eht si ”redivorp eht ot pu ton ,resu eht ot pu“ ;)noisserpmi etisoppo eht evig nac tcaf ni( gnorw si yhw nialpxe ot sliaf ”ynA“ .ti slortnoc ohw si noitseuq laer eht ;eb nac tahw stbuod reve eno oN .tniop eht sessim yletelpmoc sihT .semit ynam ,ynam ”epyt yna eb nac “ gnitaeper yb nialpxe ot yrt )sgniht gninialpxe fo( seikooR :tnaR
.” “ rof esoohc ot redivorp eht ot pu ton si ti esuaceb
:etirw tonnac redivorp ehT .redivorp eht ot pu ton erofereht ,resu eht ot pu si eciohc ehT :tnatropmI
.epyt elgnis eno gnieb htiw kcuts — ”cihpromonom“ si .cte , ,
,
). , ,.g.e ,esac reppu htiw trats )sepyt denfied dna sepyt ni-tliub fo seman( stnatsnoc epyT(
,
:sepytynamfoenoemocebnac—”cihpromylop“si tahtyaseW
,.g.e ,” “ rof esu ot epyt hcihw sesoohc )reviecer( resu eht snaem sihT
gnisoohc m’I : gnisoohc m’I :
?lagel ” “ sI sh.1sepyTlleksaH ni
sa dootsrednu retteb si
:ziuq hsalF
erutangis epyt ehT
foo :: a -> [a]
map
map :: (a -> b) -> [a] -> [b]
— or
map :: (a -> b) -> ([a] -> [b])
map ord [‘a’, ‘b’, ‘c’]
= [ord ‘a’, ord ‘b’, ord ‘c’]
= [97, 98, 99]
ord :: Char -> Int a=Char b=Int
import Data.Char
foo 48 foo “hello”
map (map ord) [[‘a’, ‘b’, ‘c’], [‘x’, ‘y’, ‘z’]] :: [[Int]]
map :: (Char -> Int) -> ([Char] -> [Int]) a=Char b=Int
map ord :: [Char] -> [Int]
map :: ([Char] -> [Int]) -> [[Char]] -> [[Int]]
a=[Char] b=[Int]
map (map ord) :: [[Char]] -> [[Int]]
foo False
map
Table of Contents
oS .retcarahc a fo edoc IICSA eht sevig ,)
:syaw owt ni nettirw ,epyt stI !evoba eht fo lla sesu taht noitcnuf yrarbil a si
) ,
gnisoohc m’I( retuo
:elpmaxe cihpromylop ,redro-rehgih ,deirruC
).retnemelpmi eht dna resu eht neewteb elggurts ssalc citcelaid a si gnimmargorP .resu eht rof ytilibatciderp htiw tciflnoc tcerid ni si retnemelpmi eht rof ytilibixefl ,yllareneG .nioc emas eht fo sedis owT(
.)snoitcnuf cihpromylop rof( rewef hcum deen seirarbil lleksaH ,sesac tset erom hcum deen seirarbil nohtyP taht eciton lliw uoY .yltaerg gnitset sefiilpmis sihT
.cte , , ot neppah lliw tahw wonk I nehT ? tset I fi teg I od tahW :noitseuq eno rewsna ot uoy deen tsuj I tuB
.edoc ruoy sseug t’nac I os )edoc lagel llits tub( yzarc eb ot yrT
…sdrow rehto nI .gniht mrofinu a od ot decrof si retnemelpmi eht esuaceB .seulav lla dna sepyt lla rof edulcnoc nac uoy dna ,eulav eno dna epyt eno tsuj ta tseT :tset ot ysaE
)
,
gnisoohc m’I( renni
:nwodkaerb epyt deliateD
:epyt siht fo gnihtemos pu edoc ot yrT
?scireneg avaJ ni siht od uoy naC :esicrexE
!emag eht pu s’tel tuB
, gnisoohc m’I ( rahC.ataD morf si
.s’tnI fo tsil a teg I .
:elpmaxe yb seod ti tahW
map (map ord) [[‘a’, ‘b’, ‘c’], [‘x’, ‘y’, ‘z’]]
= [map ord [‘a’, ‘b’, ‘c’], map ord [‘x’, ‘y’, ‘z’]]
= [[ord ‘a’, ord ‘b’, ord ‘c’], [ord ‘x’, ord ‘y’, ord ‘z’]]
= [[97, 98, 99], [120, 121, 122]]
insertionSort :: [Integer] -> [Integer]
insertionSort :: [a] -> [a]
<=
insertionSort2 :: (a -> a -> Bool) -> [a] -> [a]
insertionSort2 _ [] = []
insertionSort2 leq (x:xt) = insert x (insertionSort2 leq xt)
where
insert e [] = [e]
insert e xs@(x:xt)
| leq e x = e : xs
| otherwise = x : insert e xt
exampleInsertionSort2 = insertionSort2 (<=) [3,1,4]
<=
insertionSort3 :: Ord a => [a] -> [a]
Ord a =>
<= a
Table of Contents
. epyt fo seulav no ekil snosirapmoc esu nac noitcnuf eht snaem ” “ won roF
?yltnetsisnoc rotarapmoc emas eht esu eteled dna ,pukool ,tresni taht erusne dna ,snoitarepo eert hcraes yranib cihpromylop fo etius a ,elpmaxe rof ,od ot woH .gnirtS dna regetnI htob rof skrow ,.g.E ?gnidaolrevo rotarepo troppus lleksaH seod woH
:snoitseuq owt srewsna ti dna ,”sessalc epyt“ dellac s'tI :weiverp resaeT .erutcel retal a ni noitulos hcet-ih a si erehT
).dohtem nosirapmoc eht sniatnoc taht tcejbo na eriuqer ,segaugnal POO nI( .ti edivorp ot resu eht eriuqer dna ,rotarapmoc eht rof retemarap artxe na dda ot si noitulos hcet-wol elpmis a ,gnitros ekil noitcnuf elgnis a roF
.dnik suoitecaf eht ton ,dnik ngineb eht tub ,ruoivaheb cfiiceps-epyt a si nosirapmoc taht etoN .erapmoc ot woh tsuj neve ro epyt nesohc-resu eht wonk ton dluoc noitcnuf siht esuaceb
.sregetni era yeht taht erac yllaer t'ndid I ,)rotarepo eht ,.g.e( stnemele gnirapmoc ylno saw I ?sepyt tnemele rehto rof esnes sekam gnitros yleruS
:siht ekil sepyt ot sdael yaw hcet-ih ehT
:siht toN ?epyt cihpromylop sti etirw ot woH
:nwod dennip epyt sti dah tros noitresni ym taht llaceR
weiverp ruoivaheb cfiiceps-epyT
sh.1sepyTlleksaH ni
:seod ti tahW
"Duke" "Earl" "Sussex"
data Tetrastratan
= Monarch
| Lord String String Integer
| Knight String
| Peasant String
deriving (Eq, Show)
Tetrastratan Monarch Lord Knight Peasant
Monarch
Lord d t i
Knight n
Peasant n
d::String t::String i::Integer n::String
n::String
Monarch
⊎⊎⊎
Table of Contents
.”ciarbegla“ — laimonylop — stcudorp fo mus a ot suogolana gnirtS gnirtS regetnI×gnirtS×gnirtS )tes notelgnis( :noinu tniojsid deggat a si natartsarteT ,yllacitamehtaM
.eulav dna mret a s'ti ,epytbus a ton si .rehtie sepytbus/sessalcbus POO toN :gninraW .edoc noitazilaitini yrartibra ton ,gnillebal ylno s'tI .srotcurtsnoc POO toN :gninraW
, , fi,
:sesac 4 otni llaf epyt siht fo seulaV .dezilatipac :tnemeriuqer ylnO .eciohc ruoy era seman 5 llA .oot taht kniht
I ,thgir er'uoy ,”sgat“ kniht uoy fI .”srotcurtsnoc atad“ dellac era , , ,
. si eman epyt ehT
)gnirts a( eman :dlefi 1 yb defiiceps hcaE .stnasaeP )gnirts a( eman :dlefi 1 yb defiiceps hcaE .sthginK
ereh 9 sah xessuS fo ekuD ht9 eht ,.g.e ,)regetni( rebmun noisseccus ,.g.e ,)gnirts( yrotirret , ,.g.e ,)gnirts( eltit
:sdlefi 3 yb defiiceps hcaE .sdroL .)dlefi on sah( dias fuN' .hcranom ehT
:snosrep fo sdnik ruof htiw atartsarteT yrtnuoc laduef a enigamI .sdlefi erom ro 0 esac hcae ,sesac erom ro 1 :tuc tsriF
stcudorp naisetrac fo noinu tniojsiD sepyt atad ciarbeglA :sepyt denfied-resU
fi , fi ,
sh.1sepyTlleksaH ni
:sa detneserper eb nac yehT
Lord :: String -> String -> Integer -> Tetrastratan
Knight :: String -> Tetrastratan
Peasant :: String -> Tetrastratan
Monarch
Monarch :: Tetrastratan
theOneAndOnly, edmondDantès :: Tetrastratan
theOneAndOnly = Monarch
edmondDantès = Lord “Count” “Monte Cristo” 1
mkDuke :: String -> Integer -> Tetrastratan
mkDuke terr n = Lord “Duke” terr n
— Can also be cute, partial application:
— mkDuke = Lord “Duke”
— Pattern-matching example: How to address a Tetrastratan:
addressTetra :: Tetrastratan -> String
addressTetra Monarch = “H.M. The Monarch”
addressTetra (Lord d t i) = “The ” ++ show i ++ “th ” ++ d ++ ” of ” ++ t
addressTetra (Knight n) = “Sir ” ++ n
addressTetra (Peasant n) = n
— Pattern-matching example: Social order:
superior :: Tetrastratan -> Tetrastratan -> Bool
superior Monarch (Lord _ _ _) = True
superior Monarch (Knight _) = True
superior Monarch (Peasant _) = True
superior (Lord _ _ _) (Knight _) = True
superior (Lord _ _ _) (Peasant _) = True
superior (Knight _) (Peasant _) = True
superior _ _ = False
String
Bool
Table of Contents
: ,.g.e ,flesruoy meht denfied evah dluoc uoy ;sepyt atad ciarbegla era sepyt yrarbil dradnats emoS
.srenoititcarp alacS morf elcitra siht daeR .elihwhtrow ton si ti yhw yfitsuj nac uoy sselnu atad dilavni wollasiD .ot evirts uoy tub ,elihwhtrow syawla ton elbissop nehw dna ,elbissop syawla toN .sgub secuder sihT .ecalp tsrfi eht ni atad dilavni diova ot epyt atad ruoy ngiseD :ediug ngiseD
.gnirts a ton si gnihtyrevE .epyt noitaremune na yb ecalpeR .daorb oot si seltit drol rof :esicrexE
:siht gniod snoitcnuf fo selpmaxE ).]nosaer[ ”eltit teg“ sretteg dna ”?droL ti si“ setaciderp fo tol a revo derreferP( .epyt atad ciarbegla na fo seulav gnitcessid fo yaw derreferp dna latnemadnuf eht si gnihctam nrettaP .snrettap ni desu eb nac srotcurtsnoc ataD
:seulav ekam ot meht gnisu fo selpmaxE
:si epyt sti dna ,tnatsnoc a si ti tub ,noitcnuf a deredisnoc ton si
:era sepyt noitcnuf rieht ,ti od uoy nehW .snoitcnuf sa desu eb nac sdlefi erom ro 1 fo srotcurtsnoc ataD
sh.1sepyTlleksaH ni
sh.1sepyTlleksaH ni
data Bool = False | True
MyIntegerList
INil
ICons x xs x::Integer xs::MyIntegerList
data MyIntegerList = INil | ICons Integer MyIntegerList
deriving (Show, Eq)
exampleMyIntegerList = ICons 4 (ICons (-10) INil)
— `from0to n` builds a MyIntegerList from 0 to n-1
from0to :: Integer -> MyIntegerList
from0to n = make 0
where
make i | i >= n = INil
| otherwise = ICons i (make (i+1))
myISum :: MyIntegerList -> Integer
myISum INil = 0
myISum (ICons x xs) = x + myISum xs
IntegerBST
IEmpty
INode lt x rt lt::IntegerBST x::Integer rt::IntegerBST
data IntegerBST = IEmpty | INode IntegerBST Integer IntegerBST
deriving Show
exampleIntegerBST = INode (INode IEmpty 3 IEmpty) 7 (INode IEmpty 10 IEmpty)
ibstInsert :: Integer -> IntegerBST -> IntegerBST
ibstInsert k IEmpty =
— Base case: empty tree plus k = singleton tree with k
INode IEmpty k IEmpty
ibstInsert k inp@(INode left key right)
— Induction step: The input tree has the form INode left key right.
— Induction hypothesis (strong induction):
— If t is a smaller tree than the input tree, e.g., t=left or t=right,
— then ibstInsert k t computes t plus k.
— Can you use this to help compute inp plus k?
Table of Contents
.”k sulp eert eht“ yas ot retteb eb yaM .yek wen eht htiw tub eert tupni eht ekil si taht eert wen a ecudorp snaem ”tresni“ ,seert elbatummi htiw gnimmargorp lanoitcnuf si siht ecniS .tresni TSB
, , fi,
:fo eno si
epyt fo eulav A :noitinfied evisrucer elyts-63B .sregetni fo eert ]hcraes[ yranib :elpmaxE
:fo eno si
epyt fo eulav A :noitinfied evisrucer elyts-63B .sregetni fo tsil ]deknil ylgnis[ :elpmaxE
dna fi ,
.detroppus si )lautum ,fles( noisruceR :tuc dnoceS
sh.1sepyTlleksaH ni
sh.1sepyTlleksaH ni
sepyt evisruceR
— If k
| k > key = INode left key (ibstInsert k right)
— If k==key, nothing new to compute, the correct answer is the input tree.
| otherwise = inp — INode left key right
data BST a = Empty | Node (BST a) a (BST a)
deriving Show
exampleBSTChar :: BST Char
exampleBSTChar = Node (Node Empty ‘c’ Empty) ‘g’ (Node Empty ‘j’ Empty)
bstInsert :: Ord a => a -> BST a -> BST a
— “Ord a =>” to be explained later under Type Classes. For now it means I can
— do “<", "<=" comparisons.
bstInsert k Empty = Node Empty k Empty
bstInsert k inp@(Node left key right)
| k < key = Node (bstInsert k left) key right
| k > key = Node left key (bstInsert k right)
| otherwise = inp
BST bstInsert
data BST k v = Empty | Node …
data MyList a = Nil | Cons a (MyList a) deriving (Eq, Show)
exampleMyListI :: MyList Integer
exampleMyListI = Cons 4 (Cons (-10) Nil)
exampleMyListS :: MyList String
exampleMyListS = Cons “albert” (Cons “bart” Nil)
Table of Contents
,.g.e ,tsil emas eht ni sepyt meti tnereffid evah t’nac—tsil suoenegomoH sh.1sepyTlleksaH ni
).epyt tsil ni-tliub eht tuoba wonk ydaerla uoY .esoprup gnihcaet rof tsuJ( .epyt tnemele yrartibra fo epyt tsil yM
:siht ekil tratS .eulav osla tub ,yek tsuj ton ,.e.I .tes tsuj ton ,yranoitcid rof dna etirweR :esicrexE
.epyt yek yrartibra fo eert ]hcraes[ yranib :elpmaxE .detroppus si ).cte ,tsuR ,avaJ ni ”scireneg“( msihpromylop cirtemaraP :tuc drihT
sh.1sepyTlleksaH ni
sepyt cihpromyloP
sh.1sepyTlleksaH ni
Cons “albert” (Cons True Nil)
BST
data Maybe a = Nothing | Just a
— Great for: Sometimes there is no answer.
data Either a b = Left a | Right b
— Great for: Having two possible types.
— Example: Want a list with some String elements and some Bool elements:
— [Left “albert”, Right True, Left “trebla”] :: [Either String Bool]
MyList String MyList Bool
Table of Contents
:selpmaxe rehtruf sa yrarbil dradnats eht morf sepyt atad ciarbegla cihpromylop emoS .epyt tsil ni-tliub eht rof ylralimiS .evoba epyt eht rof ylralimiS ? ? ,epyt sti eb dluow tahw esuaceB .lagelli si