Funktionale Programmierung SS 2013 - Lösung 2

Prof. Dr. U. Kastens
Institut für Informatik, Fakultät für Elektrotechnik, Informatik und Mathematik, Universität Paderborn
29.04.2013

Lösung zu Aufgabe 1

a)

   val wuerfelA = fn x => 6*x*x;

b)

   fun wuerfelV x = x*x*x;

c)

   fun ggt(a,b) = if a=b
                  then a
                  else if a<b
                       then ggt(a, b-a)
                       else ggt(a-b, b);

d)

Ohne Pattern-Matching:

   fun reverse(l) = if null l
                    then nil
                    else reverse (tl l) @ [hd l];

Mit Pattern-Matching:

   fun reverse(nil) = nil
   |   reverse(h::t) = reverse t @ [h];

Lösung zu Aufgabe 2

a)

   fun wtab(f,s,t) = if s > t
                     then []
                     else f s :: wtab(f,s+1,t);
   fun pow(0) = 1
   | pow n = 2*pow(n-1);

   wtab(pow,0,10);

b)

   fun gerade(m,b,s,t) = wtab(fn x => m*x+b,s,t);

   gerade(2,~1,0,8);

Die Variablen m und b sind in dem Lambda-Ausdruck fn x => m*x+b frei und werden darum in der Closure gebunden.

Lösung zu Aufgabe 3

a)

Eine Funktion g mit Signatur

   ('a->'b) * ('b->'c) -> ('a->'c)

   fun x (f,g) = fn arg => g(f(arg));

Bemerkung: Die Signatur

   ('a->'b) * ('b->'c) -> 'a->'c

ist gleichbedeutend, da der Operator -> rechtsassoziativ ist.

b)

Bestimmung der Signaturen:

   fun x(li,m) = if null li
                 then 0
                 else x(tl li,m) + (if hd li = m then 1 else 0);

   fn : ''a list * ''a -> int

''a steht für einen polymorphen Typ, der die Vergleichsoperation '=' bietet.

   fun y(f,nil) = nil
   | y(f,x::xs) = f x :: y(f,xs);

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

y ist die map-Funktion.

   fun z(a,b,c) = if null c
                  then nil
                  else if b
                       then a
                       else 1.5 :: tl c;
  fn : real list * bool * real list -> real list

c)

Hausaufgabe: Geben Sie das Gleichungssystem für die Typinferenz der folgenden Funktion an. Welche Signatur hat die Funktion?

   fun f (a,b,g) = if g(a) then (b,a) else (a,b)

Das Gleichungssystem ergibt sich durch Gleichsetzen der unterern und oberen Typ-Terme in den Knoten.

   f: fn ('a * 'a * 'a -> bool) -> ('a * 'a)

Lösung zu Aufgabe 4

a)

Die drei Mengen-Funktionen:

   fun member(el, set) = if null set then false
                         else if hd set = el then true
                              else member(el, tl set);

   fun insert(el, set) = if member(el, set) then set
                         else el::set;

   fun delete(el, set) = if null set then nil
                         else if hd set = el then tl set
                              else hd set :: delete(el, tl set);

b)

Die einzige zentral-rekursiv Funktion ist delete.

Variante mit akkumulierendem Parameter:

   fun adelete(el, set, res) = if null set then res
                               else if el = hd set then res@tl set
                                    else adelete(el, tl set, hd set::res);
   fun delete(el, set) = adelete(el, set, []);

c)

(* unite *)
fun unite(set1, set2) = if null set2 then set1 
                        else if member(hd set2, set1) then unite(set1, tl set2) 
                             else unite(hd set2 :: set1, tl set2);


(* dissect *)
fun dissect(set1, set2) = if null set2 then nil 
                          else if member(hd set2, set1) then hd set2 :: dissect(set1, tl set2) 
                               else dissect(set1, tl set2);

Generiert mit Camelot | Probleme mit Camelot? | Geändert am: 14.05.2013

Weiter zum Anfang