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.
Provide a implementation for the following type signature:
const : fn : 'a -> 'b -> 'a
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.
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
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
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));
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
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)
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
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):