inf3110 SML. solutions for the extra exercises

extra.sml

(* exercises : https://gist.github.com/morteako/2dadc9f9b4fff202431513f9475177d6 *)
(* if you find any mistakes, send a mail to morteako@ifi.uio.no *)

(* fn : 'a -> 'a *)
fun id a = a;

(* fn : 'a*'b -> 'a *)
fun first (a,b) = a;

(* fn : 'a*'b -> 'b *)
fun second (a,b) = b;




(* const : fn : 'a -> 'b -> 'a *)
fun const a b = a;

map (const [6,2,1]) [1,2,3];


(* Exercise 2 *)

(* The type annotations are added because the sml type inference algorithm does not *)
(* find the correct types without them *)

val product = foldr op* 1;


fun append (xs:'a list) (ys:'a list) = foldr op:: ys xs;

(* val length  = (foldr (fn (x,y) => 1 + y) 0) : 'a list -> int; *)
fun length (xs: 'a list) = (foldr (fn (x,y) => 1 + y) 0) xs;

fun flatten (xs: 'a list list) = foldr (fn (x,y) => append x y) [];
(* val flatten = foldr op@ []; *)

fun map f = foldr (fn (x,y) => f x :: y) [];

fun null (xs:'a list) = foldr (fn (x,y) => false) true xs;

fun filter p = foldr (fn (x,y) => if p x then x :: y else y) [];

fun all p = foldr (fn (x,y) => p x andalso y) true;

fun any p = foldr (fn (x,y) => p x orelse y) false;



(* Exercise 3 *)

fun all p = null o filter (not o p);

fun count p = length o filter p;

fun flatMap f = concat o map f;

fun find p = hd o filter p;


fun first (a,b) = a;
fun second (a,b) = b;
fun findValue p = second o hd o filter (p o first);

fun combine xs = foldr (op o) (fn x => x) xs;


(* theoretical *)
val identity = fn x => x;

(* proof: *)
(* f o (fn x => x)  *)
(* fn x => f ((fn x => x) x) *)
(* fn x => f x *)
(* f *)

(* (fn y => y) o f *)
(* fn x => (fn y => y) f x *)
(* fn x => f x *)
(* f *)

(* assoc proof: *)
(* f o (g o h) *)
(* fn x => f ((fn y => g (h y)) x) *)
(* fn x => f (g (h x)) *)
(* fn x => f (g (h x)) *)
(* fn x => (fn y => f (g y)) (h x) *)
(* (f o g) o h *)



(* (map o map) (fn x => x*2) [[1,2,3],[4,5,6]]  *)

(* from the definitation of o (compose), (map o map) gives the function *)
(* fn f => map (map f) *)
(* so *)
(* (map o map) (fn x => x*2) *)
(* gives  *)
(* map (map (fn x => x*2)) *)
(* So this function takes in a list of lists and applies (map (fn x => x*2)) to every element. *)
(* Then (map o map) (fn x => x*2) [[1,2,3],[4,5,6]]  will of course work. *)


(* fun add x y = x + y; *)
(* (add o add) 1 2 3; *)

(* from def of o(compose) *)
(* (add o add) *)
(* fn x => add (add x) *)
(* we see here that the outer add is given (add x) as the first argument.  *)
(* but add x is not fully applied, and will return a function. *)
(* and the outer add expects an int, not a function. So this will not type check *)



(* - fun compose f g = f o g; *) 
(* val compose = fn : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b *) 
(* - fun plus x y = x + y; *) 
(* val plus = fn : int -> int -> int *) 
(* - val plus3 = (compose compose compose) plus plus; *) 
(* val plus3 = fn : int -> int -> int -> int *) 
(* - plus3 1 2 3; *) 
(* val it = 6 : int *) 


(* This is a bit chaotic, but that is how it works. *)
(* Using simplified syntax for lambda-functions. *)
(* \f g y -> f (g y) means fn f => fn g => x => f (g x) *)

(* compose compose compose *)
(* compose o compose *)
(* (\y -> (\f g x -> f (g x)) ((\f g x -> f (g x)) y)) plus plus *)
(* (\f g x -> f (g x)) ((\f g x -> f (g x)) plus) plus *)
(* (\g x -> (((\f2 g2 x2 -> f2 (g2 x2)) plus)) (g x)) plus *)
(* (\x -> ((\f2 g2 x2 -> f2 (g2 x2)) plus) (plus x)) *)
(* (\x -> ((\g2 x2 -> plus (g2 x2)) (plus x))) *)

(* so *)

(* plus3 = (\x -> (((\g2 x2 -> plus (g2 x2))) (plus x))) *)
(* plus3 1 2 3 *)
(* (\x -> (((\g2 x2 -> plus (g2 x2))) (plus x))) 1 2 3 *)
(* (((\g2 x2 -> plus (g2 x2))) (plus 1)) 2 3 *)
(* (\x2 -> plus ((plus 1) x2)) 2 3 *)
(* (plus ((plus 1) 2)) 3 *)
(* (plus 3) 3 *)
(* 6 *)






(* so *) 
(* (compose compose compose) plus plus *) 
(* (fn gg => fn xx => (fn g => fn x => f (g x)) (gg xx)) plus plus *) 
(* fn xx => (fn g => fn x => f (g x)) (plus xx)) plus *) 

(* - val plus3 = compose (compose plus) plus; *) 
(* val plus3 = fn : int -> int -> int -> int *) 
(* - plus3 1 2 3; *) 
(* val it = 6 : int *) 


(* compose (compose plus) plus *)

(* fn x => compose plus (plus x) *)
(* fn x => (fn g => fn y => plus (g y)) (plus x) *)
(* fn x => fn y => plus (plus x y)) *)

(* so *)

(* val plus3 = fn x => fn y => plus (plus x y)); *)
(* plus3 1 2 3 *)
(* (plus3 1 2) 3 *)
(* (plus (plus 1 2)) 3 *)
(* (plus 3) 3 *)
(* 6 *)






(* Proof: *)
(* map (f o g) = map f o map g *)

(* base case: *)
(* map (f o g) [] = [] = map f [] = map f (map g []) = (map f o map g) [] *)
(* inductive case: *)
(* map (f o g) (x::xs) =  *)
(* (f o g) x :: map (f o g) xs =   *)
(* f (g x) :: map (f o g) xs =   Inductive hypothesis*)
(* f (g x) :: map f (map g xs) = *)
(* map f (g x :: map g xs) = *)
(* map f (map g (x::xs)) = *)
(* (map f o map g) (x::xs) *)



datatype 'a pair = Pair of 'a * 'a;
(* identitymap : fn : ('a -> 'b) -> 'a pair -> 'b pair *)
fun pairmap f (Pair (a,aa)) = Pair (f a, f aa);


datatype 'a identity = Identity of 'a;
(* identitymap : fn : ('a -> 'b) -> 'a identity -> 'b identity *)
fun identitymap f (Identity a) = Identity (f a);


datatype 'a option = NONE | SOME of 'a;
(* optionmap : fn : ('a -> 'b) -> 'a option -> 'b option *)
fun optionmap f NONE = NONE
|   optionmap f (SOME a) = SOME (f a);

type ('a,'b) func = 'a -> 'b;
fun funcmap f func = f o func;
(* so the map function for functions is just compose, funcmap = compose *)

(* proof :  *)
(* funcmap id func = id o func =  *)
(* (fn y => y) o func =  *)
(* fn x => (fn y => y) (func x) =  will be the same as *)
(* fn x => func x =    a function will work the same as the lambda that applies that function *)
(* func = *)
(* id func  *)



datatype ('s,'a) state = State of 's -> ('a * 's);
(* statemap : fn : ('a -> 'b) -> ('s, 'a) state -> ('s, 'b) state *)
fun statemap f (State stateFunc) = 
    State (fn s => 
        let 
            val (resA,resS) = stateFunc s
        in
            (f resA, resS)
        end);