Map map f Ist:('a->'b)->('a list)->('b list) Creates a new list by applying f to each element of the input list;returns output in order. ●●●●● tt tt 3 12
12 Map map f lst: (’a->’b) -> (’a list) -> (’b list) Creates a new list by applying f to each element of the input list; returns output in order. f f f f f f
Fold fold f xo Ist:('a*'b->'b)->'b->('a list)->'b Moves across a list,applying fto each element plus an accumulator.f returns the next accumulator value,which is combined with the next element of the list returned initial 13
13 Fold fold f x0 lst: ('a*'b->'b)->'b->('a list)->'b Moves across a list, applying f to each element plus an accumulator. f returns the next accumulator value, which is combined with the next element of the list f f f f f returned initial
fold left vs.fold right Order of list elements can be significant Fold left moves left-to-right across the list Fold right moves from right-to-left SML Implementation: fun foldl f a [ a foldl f a (x::xs)= foldl f (f(x,a))xs fun foldr f a [ 三 a foldr f a (x:xs)=f(x,(foldr f a xs)) 14
14 fold left vs. fold right ◼ Order of list elements can be significant ◼ Fold left moves left-to-right across the list ◼ Fold right moves from right-to-left SML Implementation: fun foldl f a [] = a | foldl f a (x::xs) = foldl f (f(x, a)) xs fun foldr f a [] = a | foldr f a (x::xs) = f(x, (foldr f a xs))
Example fun foo(l:int list) sum(I)mul(I)length(I) How can we implement this by map and foldl? 15
15 Example fun foo(l: int list) = sum(l) + mul(l) + length(l) How can we implement this by map and foldl?
Example (Solved) fun foo(l:int list)= sum(I)mul(1)length(I) fun sum(Ist)=foldl (fn (a,x)=>a+x)0 Ist fun mul(lst)=foldl (fn (a,x)=>a*x)1 Ist fun length(Ist)=foldl (fn (a,x)=>a+1)0 Ist 16
16 Example (Solved) fun foo(l: int list) = sum(l) + mul(l) + length(l) fun sum(lst) = foldl (fn (a,x)=>a+x) 0 lst fun mul(lst) = foldl (fn (a,x)=>a*x) 1 lst fun length(lst) = foldl (fn (a,x)=>a+1) 0 lst