extra.md

Exercise 1

(a)

Write functions with the following type signatures:

fn : 'a -> 'a
fn : 'a*'b -> 'a
fn : 'a*'b -> 'b

Think about what the type signatures says and implement the functions.

There is only one implementation of these type signatures.

(b)

Provide a implementation for the following type signature:

const : fn : 'a -> 'b -> 'a

(c)

Create an example of how to use a partial application of const as an argument to map to replace every element in a list with the list [6,2,1].

Assuming ??? is your use of const, then map ??? [1,2,3] should result in [[6,2,1], [6,2,1], [6,2,1]].

When you partially apply const, you get a constant function, hence the name.

Exercise 2

A fold is a way to combine values into one value. foldr is one example of a fold. foldr is a function that takes one function that combines values, a default value and a list of values. (You can also look at link for a more thorough explanation of foldr.)

foldr : fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

definition:

fun foldr f v []       = v
|   foldr f v (x::xs)  = f(x, foldr f v xs);

Example of use:

fun p (x,y) = x+y;
foldr p 0 [1,2,3] = p(1, p(2, p(3,0)))  (* => 6 *)

So you can define

fun sum xs = foldr (fn (x,y) => x+y) 0 xs;

Implement these functions using foldr: (If that is too hard, implement them using explicit recursion)

product : fn : int list -> int

the product of the ints in a list
product [1,2,4] ====> 8

append : fn : 'a list -> 'a list -> 'a list

append to lists together
append [1,2,3] [4,5,6] ====> [1,2,3,4,5,6]

length : fn : 'a list -> int

length of a list
length [1,2,3]   ===> 3

flatten : fn : 'a list list -> a list

flatten a list of lists to a list. 
flatten [[1,2,3],[4,5,6]] = [1,2,3,4,5,6]
tips : append

map : fn : ('a -> 'b) -> 'a list -> 'b list

the normal map function for lists

null : fn : 'a list -> bool

a function that returns true if the list is empty, else return false

filter: fn : ('a -> bool) -> 'a list -> 'a list

the normal filter function for lists

all : fn : ('a -> bool) -> 'a list -> bool

a function that takes in a predicate and checks if every element in that list 

satisfies the predicate.

all (fn x => x = 5) [5,5,5] ====> true

all (fn x => x = 5) [6] ====> false

all (fn x => x = 5) [] ====> true

any :

same as all, except that it checks that ANY element satisfies the predicate, not every

---

Exercise 3

you can compose functions in sml using the o-operator which is defined like this: fun f o g = (fn x => f (g x));

(* example *)
fun add5 x = x + 5;
fun times2 = x * 2;

val f = times2 o add5;
(* here f is a function that adds 5 to its argument and then multiplies that by 2. *)
f 3
(times2 o add5) 3
(fn x => times2 (add5 x)) 3
times2 (add5 3)
times2 8
16

the type of compose (o) is fn : (b -> c) -> (a -> b) -> (a -> c)

use of compose:

fun any pred = not o null o List.filter (fn x => x) o map pred;

map (add5 o times2)
map add5 o map times2

create these functions (utilising compose):

all (as described earlier)

count : fn : ('a -> bool) -> 'a list -> int

count how many elements satisfy a given predicate

flatMap: fn : ('a -> b list) -> 'a list -> 'b list

tips: see flatten from earlier

find : fn : ('a -> bool) -> 'a list -> 'a

find the first element that satisfy the predicate

findValue : fn : ('k -> bool) -> ('k * 'v) list -> 'v

return the value of the first pair where the first value satisfy the predicate
fun first (a,b) = a;
fun second (a,b) = b;
first and second could make the composition nicer

combine : fn : ('a -> 'a) list -> 'a -> 'a

a function that composes all functions in a list into one function.
combine [f,g,h] should create the function f o g o h
- (combine [fn x => x+1, fn x => x*10, fn x => x+2]) 10;
val it = 121 : int

protip : use foldr

theoretical

a) what is the identity element for function composition, meaning :

which function e will make 
f o e = f
e o f = f
for any function f

b) prove that function composition is associative, meaning :

f o (g o h) = (f o g) o h 

use this definition of o:
fun f o g = (fn x => f (g x));

hard:

what is the result of the follow code and why does it work?

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

why does not this work?

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

why does this work?

- 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

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

Exercise 4 (a bit outside of the curriculum)

The standard map-function for lists is defined like this:

fun map f [] = []
|   map f (x::xs) = f x :: map f xs;

the type of map is

fn : ('a -> 'b) -> 'a list -> 'b list

With id is the identity function: fun id x = x; we can prove that the following property hold:

map id = id

, which means that when you map the identity function over a list, you should get the same list back. From this follows that the map-function can't change the structure of its argument, only the values

Proof, by induction: base case:

map id [] = [] = id []

inductive case:

map id (x::xs) = 
id x :: map id xs = 
x :: map id xs = (inductive theorem)
x :: xs = 
id (x :: xs)

Optional exercise : Prove that : map (f o g) = map f o map g (for all pure functions f,g)

Tree map

Is it possible to define a map function for other types than lists?

Yes!

Lets look at a binary tree datatype and its corresponding map-function:

datatype 'a tree = Empty | Node of 'a tree * 'a * 'a tree;

fun treemap f Empty = Empty
|   treemap f (Node(left,v, right)) = Node (treemap f left, f v, treemap f right);

treemap id = id holds for this definition (and its the only possible definition). The proof is left as an exercise to the reader :)

if we look at the type signature of map :

fn : ('a -> 'b) -> 'a list -> 'b list

and the type signature of treemap :

fn : ('a -> 'b) -> 'a tree -> 'b tree

we see some similarities

Implement map functions for each of these data types:

For all the new map functions, the newmap id = id needs to be valid. A "fun" way to check this is to prove it (in the same style as the proof above). You could also go the other way and use the rule to write the correct functions in the first place.

datatype 'a pair = Pair of ('a,'a);
pairmap : fn : ('a -> 'b) -> 'a pair -> 'b pair

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

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

type ('a,'b) func = 'a -> 'b
funcmap : fn : ('a -> 'b) -> ('c, 'a) func -> ('c, 'b) func

datatype ('s,'a) state = State of ('s -> ('s,'a))
statemap : fn : ('a -> 'b) -> ('s, 'a) state -> ('s, 'b) state

If you find this stuff interesting, you could check out these links (Haskell):

Functor

State (related to the state datatype)

Solutions

Solutions