(* cute uses of accumulators *)
(* here's the cross function from my solution of hw2 *)
(* accumulator helper function *)
fun one_cross(_,nil,accum) = accum
| one_cross(s,(t::ts),accum) = one_cross(s, ts, ((s,t)::accum))
(* my cross, using append (@) *)
infix cross;
fun nil cross ts = nil
| ss cross nil = nil
| (s::ss) cross ts = (one_cross(s, ts, nil))@(ss cross ts)
(*
But the accumulator function essential prepends its
output to the accumulator, making thing @ unnecessary
*)
fun nil cross ts = nil
| ss cross nil = nil
| (s::ss) cross ts = (one_cross(s, ts, (ss cross ts)))
(* cool, hunh? *)
(* more mapping *)
fun double x = x*x; (* we'll use this below *)
(*
if a list is like a one-dimensional array, than a list of
lists is like a two-dimensional array. But because map is
curried we can use it on 2d lists with very little
overhead
*)
map (map double) [[1,2],[3],[4,5,6]];
(* think of this as follows *)
val F = map double
map F [[1,2],[3],[4,5,6]];
(*
==> [ F[1,2], F[3], F[4,5,6] ];
==> [ (map double [1,2]), (map double [3]), (map double [4,5,6]) ]
*)
(* What does this do? *)
(* The local "loop" function is the functional idiom for a *)
(* "for" loop *)
map (fn x =>
let fun loop 0 = ""
| loop y = "ho " ^ (loop(y-1))
in loop x end)
[3,1,3,4]
(* If you're having trouble parsing the above, figure out *)
(* what this function does: *)
fun int2str x =
let fun loop 0 = ""
| loop y = "ho " ^ (loop(y-1))
in loop x end
int2str 3; int2str 4;
(* then consider the following *)
map int2str [3,1,3,4];
(* Again, as map is curried we can turn the previous example *)
(* into its own function *)
val hoizer = map (fn x =>
let fun loop 0 = ""
| loop y = "ho " ^ (loop(y-1))
in loop x end);
(* a definition of map: *)
fun map f nil = nil
| map f (x::xs) = (f x)::(map f xs)
(*
Folding
If we have a list
a1 a2 a3 ... a(n-1) a(n)
then we're going to think of each list item as being a function
F_a1 F_a2 F_a3 ... F_a(n-1) F_a(n)
foldl and foldr compose these functions & apply the
composition to a base:
foldr==>F_a1 (F_a2 (F_a3( ... (F_a(n-1) (F_a(n) (base))))))
fold1==>F_a(n) (F_a(n-1) (F_a(n-2)( ... (F_a2 (F_a1 (base))))))
The function is often thought of as an operation (see
foldleft and foldright from last week's notes).
If we're thinking of int lists, a natural operation is addtion:
fun F_a x = a+x (* = increment by a *)
F(a,x) = a+x
F_a(x)= a::x (* this is not real ML *)
*)
fun plus (x,y) = x+y;
foldl plus 0 [1,2,3,4,5]; (*=>15*)
val sum = foldl plus 0; (* sum is a function that sums a list *)
val sum = foldl (fn (a,x)=>a+x) 0 (* use an anonymous function
val sum = foldl (op +) 0; (* save us the trouble of writing a *)
(* "plus" function *)
(* op x turns an infix operator x into a function *)
(* fold can be used for a surprising variety of things: *)
foldl (fn (_,x) => 1+x) 0 [5,3,7,1,4,8];
(* ==> length of the list! *)
(* if we want to produce a list, the natural operation is :: *)
foldl (fn (a,lst) => a::lst) nil [1,2,3,4,5];
(* ==> reverse a list!! *)
(* So what's the difference between foldl and foldr anyway? Comparing *)
(* the previous example with the following is the one to remember:
foldr (fn (a,lst) => a::lst) nil [1,2,3,4,5];
(* ==> doesn't change the list! *)
(*
How to do the following?
["1","2","3","4"] ===> "1234"
In this case, the natural operation is ^ (concatenation)
*)
foldr (op ^) "" ["1","2","3","4"];
(* what would foldl do here? *)
(* Combining map and fold *)
(* if we have a set of numbers,
as =a1...an
their "variance" is the difference between the square of their mean
and the mean of their squares:
(sum a_i^2)/n - ((sum a_i)/n)^2
How to sum up some number? We did this already!
sum= foldl (op +)
How to turn a list into squares?
makesquares = map (fn x=>x*x)
Combine them all together:
(foldl (op +) 0 (map (fn x=>x*x) as)/n
- ((fn x => x*x) (foldl (op +) 0 as)/n)
Nice and short. We can make this more readable by doing the
following.
*)
val sum = foldl (op +) 0;
fun square x = x*x;
val n = length as;
val variance = (sum (map square as))/n - (square ((sum as)/n));
(* almost as easy as the math definition! *)