INF3110/4110
L�sningsforslag uke 38 (17.-19.9.2003)
Oppgave 2
---------
1. Siden vi skal l�se den rekursivt, s� lager vi f�lgende funksjon
(men det finnes alts� en formel for dette som fjerner behovet for
rekursjon):
fun sum(n:int):int = if n= 0 then 0
else n+sum(n-1);
2. let
val sum5 = sum(5)
in
sum5 * (sum5-1)
end;
Alternativ l�sning med en navnl�s funksjon:
Tenk deg at du har regnet ut sum(5), og at variabelen x er bundet
til denne verdien. Da f�r du opplagt samme svar ved � erstatte de
to forekomstene av sum(5) med x. Lag deretter en funksjon med x som
formell parameter, og send inn sum(5) som aktuell parameter:
(fn x => x * (x-1)) (sum(5));
Oppgave 3
---------
fun fib(n)= if n = 1 then (1,0)
else let val (a,b) = fib(n-1) in (a+b,a) end;
Oppgave 4
---------
1. structure Set_impl: Set_def =
struct
type ''Elem Set = ''Elem list;
val empty = [];
fun has(s,x) = case s of [] => false
| x'::r => if less(x,x') then false
else if less(x',x) then has(r,x)
else true;
fun add(s,x) = case s of [] => [x]
| x'::r => if less(x,x') then x::s
else if less(x',x) then x'::add(r,x)
else s;
fun del(s,x) = case s of [] => []
| x'::r => if less(x,x') then s
else if less(x',x) then x'::del(r,x)
else r;
fun union(s1,s2) = case s2 of [] => s1
| x::r2 => union(add(s1,x),r2);
(* Alternativt:
fun union(s1,s2) = case s1 of []�=> s2
| x::r1 => union(r1,add(s2,x));
*)
fun inter(s1,s2) = case s2 of [] => []
| x::r2 =>if has(s1,x) then x::inter(s1,r2)
else inter(s1,r2);
(*Alternativt:
fun inter(s1,s2) = case s1 of [] => []
| x::r1 => if has(s2,x) then x::inter(r1,s2)
else inter(r1,s2);
*)
end;
3. structure Set_impl2: Set_def =
struct
type ''Elem Set = ''Elem -> bool;
val empty = fn(x) => false;
fun has(s,x) = s x; (* has returnerer bool *)
fun add(s,x) = fn(y) => if x = y then true else s y;
fun del(s,x) = fn(y) => if x = y then false else s y;
fun union(s1,s2) = fn(x) => (s1 x) orelse (s2 x);
fun inter(s1,s2) = fn(x) => (s1 x) andalso (s2 x);
end;
En alternativ skrivem�te for noen av funksjonene:
fun empty x = false;
fun add(s,x) y = if x = y then true else s y;
fun del(s,x) y = if x = y then false else s y;
fun union(s1,s2) x = (s1 x) orelse (s2 x);
fun inter(s1,s2) x = (s1 x) andalso (s2 x);