• View
27

2

Embed Size (px)

DESCRIPTION

Paradigmer i Programmering 3. PIP. Hjere ordens funktioner. Idag: Hjere ordens funktioner Algebraiske datatyper Nste gang: I/O, Filer, interaktive programmer Lidt om Lex og Yacc - parsergeneratorer. Flere parametre. - fun add(x,y) = x+y; > val add = fn : int * int -> int - PowerPoint PPT Presentation

Transcript

• Hjere ordens funktionerIdag:

Hjere ordens funktionerAlgebraiske datatyper

Nste gang: I/O, Filer, interaktive programmerLidt om Lex og Yacc - parsergeneratorer

• Flere parametre- fun add(x,y) = x+y;> val add = fn : int * int -> int- add(2,3);> val it = 5 : int- fun add x y = x+y;> val add = fn : int -> int -> int- add 1;> val it = fn : int -> int- val inc = add 1;> val inc = fn : int -> int- inc 4;> val it = 5 : int

• mapAnvend funktion p hvert element i en liste:

- fun map f [] = [] | map f (x::xs) = (f x)::(map f xs);> val ('a, 'b) map = fn : ('a -> 'b) -> 'a list -> 'b list- map inc [1,2,3];> val it = [2, 3, 4] : int list

• Eksempel- fun upString x = implode (map Char.toUpper (explode x));> val upString = fn : string -> string- upString "hejsahj+986543";> val it = "HEJSAHJ+986543" : string

• all, exists- fun all p [] = true | all p (x::xs) = (p x) andalso (all p xs);> val 'a all = fn : ('a -> bool) -> 'a list -> bool- fun exists p [] = false | exists p (x::xs) = (p x) orelse (exists p xs);> val 'a exists = fn : ('a -> bool) -> 'a list -> bool

• Programmering med exists- fun eq x y = x=y;> val ''a eq = fn : ''a -> ''a -> bool- fun member elm lst = exists (eq elm) lst;> val ''a member = fn : ''a -> ''a list -> bool- member 3 [1,2,3,4];> val it = true : bool- member 3 [1,2,4,5];> val it = false : bool

• Foldning af liste- fun foldr f b [] = b | foldr f b (x::xs) = f(x,foldr f b xs);> val ('a, 'b) foldr = fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b- fun app xs ys = foldr op:: ys xs;> val 'a app = fn : 'a list -> 'a list -> 'a list- app [1,2,3] [4,5,6];> val it = [1, 2, 3, 4, 5, 6] : int list- fun sum xs = foldr op+ 0 xs;> val sum = fn : int list -> int- sum [1,2,3,4];> val it = 10 : int

• Anonyme funktioner: fn- fun len xs = foldr (fn (_,x) => x+1) 0 xs;> val 'a len = fn : 'a list -> int- len [1,2,3];> val it = 3 : int- len [];> val it = 0 : inteller..- fun snd (x,y) = y;> val ('a, 'b) snd = fn : 'a * 'b -> 'b- fun len xs = foldr (inc o snd) 0 xs;> val 'b len = fn : 'b list -> int- len [1,2];> val it = 2 : int

• Algebraiske datatyper

I mngdelren: N Mi SML: tupler Nm i SML: lister N + Mi SML: datatyper

N + M er stort set N M, men man kan se om envrdi kommer fra den ene eller anden.

• Eksempel- datatype Val = Chr of char | Str of string | Int of int;> New type names: =Val datatype Val = (Val,{con Chr: char -> Val, con Int: int -> Val, con Str: string -> Val}) con Chr = fn : char -> Val con Int = fn : int -> Val con Str = fn : string -> Val- Chr #"2";> val it = Chr #"2" : Val- Int 3;> val it = Int 3 : Val-

• Min liste- datatype Liste = Tom | Hoved of (int * Liste);> New type names: =Liste datatype Liste =(Liste,{con Hoved : (int * Liste) -> Liste, con Tom : Liste}) con Hoved = fn : (int * Liste) -> Liste con Tom = Tom : Liste- val x = Hoved(1,Hoved(2,Hoved(3,Tom)));> val x = Hoved(1,Hoved(2,Hoved(3,Tom))): Liste- fun len Tom = 0 | len (Hoved(x,xs)) = 1+ len xs;> val len = fn : Liste -> int- len x;> val it = 3 : int

- flad t;> val it = [1, 2, 3, 4] : int list

• Eksempel binrt sgetrdatatype 'a trae = blad | node of ('a * 'a trae * 'a trae );fun cmpr (a,b) = if a=b then EQUAL else if a node(x,lf,rt) | LESS => node(y,insert cmp x lf,rt) | GREATER => node(y,lf,insert cmp x rt) ;

New type names: =traedatatype 'a trae =('a trae,{ con 'a blad : 'a trae, con 'a node : ('a * 'a trae * 'a trae) -> 'a trae})con 'a blad = blad : 'a traecon 'a node = fn : ('a * 'a trae * 'a trae) -> 'a traeval cmpr = fn : int * int -> orderval 'a insert = fn : ('a * 'a -> order) -> 'a -> 'a trae -> 'a trae

• Eksempel binrt sgetrMoscow ML version 2.00 (June 2000)Enter `quit();' to quit.

• Options datatype 'a option = NONE | SOME of 'a;

Bruges nr man mske ikke fr en vrdi

- fun last [] = NONE | last [x] = SOME x | last (x::xs) = last xs;> val 'a last = fn : 'a list -> 'a option

- last [1,2,3];> val it = SOME 3 : int option

• Undtagelser- exception TomListe;> exn TomListe = TomListe : exn- fun last [] = raise TomListe | last [x] = x | last (x::xs) = last xs;> val 'a last = fn : 'a list -> 'a- last [];! Uncaught exception:! TomListe

• Fange undtagelser- fun trylast ls = last ls handle TomListe => 0;> val trylast = fn : int list -> int- trylast [];> val it = 0 : int

• Fange undtagelser- fun f x = if x = 0 then x div 0 else if x = 1 then raise TomListe else x;> val f = fn : int -> int- fun g x = f x handle TomListe => 17 | x => 18;> val g = fn : int -> int- g 0;> val it = 18 : int- g 1;> val it = 17 : int- g 2;> val it = 2 : int

• Parametrisk polymorfi i C++#include template T max(T a,T b){ return ( a>b ? a : b );}template void swap(T &a,T &b){ T tmp = a; a=b; b=tmp; }int main(){ printf ("max =%6.3g\n",max(2.34,3.45)); printf ("max =%d\n",max(334,245)); char a = 'c', b='q'; swap(a,b); printf ("a=%c b=%c\n",a,b); int x=6,y=9; swap(x,y); printf ("x=%d y=%d\n",x,y); return(0);}

• Parametrisk polymorfi i SMLMoscow ML version 2.00 (June 2000)Enter `quit();' to quit.- fun swap (a,b) = (b,a);> val ('a, 'b) swap = fn : 'a * 'b -> 'b * 'a- swap (12,34);> val it = (34, 12) : int * int- swap ("hej","hallo");> val it = ("hallo", "hej") : string * string

I C++ laves en version af swap og max for hver type den bruges med. I ML checkes typen en gang og funktionen bruges uafhngig af typen.

• hjereordens kald i javainterface Visitor{ int call(int x); }class List{ int x; List next; List(int x1,List n1){x=x1;next=n1;} void visit(Visitor vv){ x=vv.call(x); if(next!=null) next.visit(vv);} public String toString(){return ""+x+" :: "+next;} }class incv implements Visitor{ public int call(int x){ return x+1; } }public class visit{ public static void main(String args[]){ List l = new List(3,new List(5,new List(2,null))); System.out.println(l); l.visit(new incv()); System.out.println(l); } }

3 :: 5 :: 2 :: null4 :: 6 :: 3 :: null

• Opgaver7.2: lav funktion min: int list -> int option der finder mindste tal i en liste

9.3 lav funktion rod: (int -> int) -> int s rod f finder mindste tal n (n>0) s f(n) = 0;

9.4, 9.5

• Flere opgaver1. Fakultetsfunktionen kan skrives fun fak(n) = if n = 1 then 1 else n * (fak n) Skriv den s den i stedet laver en liste af tal og derefter ganger dem sammen.

2. Skriv en funktion "flat" der tager en liste af lister og hfter dem sammen til en liste. F.eks. skal [[1,2],[3],[4,5]] laves om til [1,2,3,4,5]

3. Overvej at skrive den med brug af fold og append (op@)

4. (Opgave for dem der kan matrixregning..) Lad en matrix vre en liste af liste af heltal. Definer funktioner til multiplikation, sum, transponering og udregning af determinant.

5. lav funktion "subset" med to argumenter s1 og s2 og som undersger om alle elementer i listen s1 ogs findes i listen s2. F.eks er subset [1,2] [0,1,2,3] = truemens subset [0,1,2,3] [1,2] = false

6. Lav funktion "subsets" der danner en liste af alle delmngder af en liste. F.eks skal subsets [1,2] = [[],[1],[2],[1,2]]

7. lav funktion fun dropwhile p lst som fjerner elementer fra listen lst s lnge funktionen p anvendt p elementet returnerer sand F.eks. antag f.eks. en funktion odd : int -> bool der undersger om et tal er ulige da skal dropwhile odd [1,3,4,5,6] = [4,5,6]

• Flere opgaver8. lav funktion fun takewhile p lstsom tager indeledende del af liste hvor funktion p returnerer sand for elementerne. F.eks. skal

takewhile odd [1,3,4,5,6] = [1,3]

9. lav funktion repeat f n lst som anvender funktionen f antallet n gange p argumentet s f.eks "repeat f 2 lst" er det samme som "(f (f lst))"

10. typen "(string * string) list" kan vre nyttig som en slags "property list" a la maps fra javas collection frameworkskriv en funktion lookup nm alst : string -> (string * string) list -> string s f.eks lookup "y" [("x","1"),("y","hej"),("z","\$\$\$")] = "hej"Det kan antages at hvis der ikke findes et et par i listen hvor frste komponent passer s returnerer man blot en tom tekststreng

11. Skriv funktion "update" update nm vl alst : string -> string -> (string * string