Temat för lektion 3 är högre ordningens funktioner. =================================================== (Jag har ännu (la före lunch fredag) inte hört något krav på en extratid för den inställda lektionen, därför här istället litet utförligare (än bara problemlösningar) om det jag tänkte säja) En högre ordningens funktion är en funktion som tar en funktion som argument eller returnerar en funktion. Observationer i tre steg ------------------------ Steg 1: - - - - (/ (+ 1 2 3 4 5) 5) => 3 (/ (+ 2 4 6 8 10 12 14) 7) => 8 ... Skall man göra många såna där medelvärdesberäkningar kanske man vill definiera en egen funktion för det. Det blir mer att skriva än en enskild medelvärdesberäkning, men det lönar sej i längden. (defun medel (värden) (labels ((add (värden) (if (endp värden) 0 (+ (first värden) (add (rest värden)))))) (/ (add värden) (length värden)))) (medel '(1 2 3 4 5)) => 3 Steg 2: - - - - Efter ett tag så observerar man att man har definierat ett flertal olika funktioner som liknar varandra väldigt mycket, ex: (defun sum-square (index n) ;summera kvadrater fr.o.m. index t.o.m. n. ;index kommer att vara loopvariabel, n är fixt. (if (> index n) 0 (+ (square index) (sum-square (+ 1 index) n)))) (defun sum-inv-square (index n) ... (+ (/ square index)) ... (defun sum-sin (index n) ... (+ (sin index) ... Steg 3: - - - - Förenkla situationen genom att ta den önskade elementfunktionen som argument: (defun sum (fn index n) (if (> index n) 0 (+ (?...fn...? index) ;Vad skall stå här??? (sum fn (+ 1 index) n)))) För att komma fram till vad "?...fn...?" skall vara - en liten utvikning: Hur beräknas uttrycket (x y z)? Jo, x är namnet på en funktion, medan x och y är uttryck som beräknas. I Commonlisp kan man ju samtidigt ha (setq x 17) och (defun x (arg) (+ arg 1)) och beräkna uttrycket (x x) => 18. I Commonlisp har en atom en funktionscell (som defun och labels förändrar) och en värdecell (som setq och let förändrar). I uttrycket (x y z) så hämtas alltså innehållet i x:s funktionscell och i y:s och z:s värdeceller. För att hantera denna situation finns konstruktionerna funcall och function. När funktionen sum ovan anropas så sker ju parameteröverföringen som vanligt - fn, index, och n har fått något i sina värdeceller. Men när vi använder fn vill vi egentligen hämta ur funktionscellen. Det rätta sättet att skriva (?...fn...? index) ovan är (funcall fn index). Ett korrekt anrop till sum kan vara (sum (function square) 1 100). funcall betyder: Tag ur en värdecell och använd som en funktion. function betyder: Tag ur en funktionscell (utvidgas strax) och använd som värde. function kan också skrivas #', t.ex. (sum #'square 1 100) Lambdauttryck ------------- Man kan låta en variabel få ett numeriskt värde: (setq x 17) Därefter kan man använda variabeln: (+ x x) => 34 Man kan defineira en funktion: (defun f(x) (+ x 1)) Därefter kan man använda funktionen: (f 4711) => 4712 Man kan, utan att gå via en variabel, ange ett numeriskt värde 'direkt': (+ 17 17) På samma sätt kan man använda en funktion 'direkt' utan att ge den ett namn: ((lambda (x) (+ x 1)) 4711) => 4712 Det där lambda-uttrycket är alltså ett sätt att skirva ett funktionsvärde (OBS! Ett värde som är en funktion, inte ett värde som är resultatet av en funktionsapplikation.). "Utvidgas strax" ovan innebär att man kan skriva så här: (sum #'(lambda (x) (* x x x)) 1 4) => 100 Man kan alltså ge ett lambdauttryck till function (eller #'). Map-funktioner -------------- Eftersom både listor och funktioner är så centrala i Lisp av alla smaker så har det sen dom språkens begynnelse funnits en uppsättning map-funktioner, funktioner som på något sätt går igenom en listor och applicerar en funktion steg för steg. (Det har något jargongigt utvidgats till att "mappa" i många situationer där man tillämpar nån metod på alla tillämpliga delar.) Den allra mest grundläggande map-funktionen i Commonlisp heter mapcar. Den tar en funktion och en lista och returnerar en ny lista enligt: (mapcar #'1+ '(1 2 3 4 5)) => (2 3 4 5 6), dvs en lista med värdena av funktionen applicerad på varje element i den givna listan. Om funktionen tar flera argument så tar också mapcar flera listargument: (mapcar #'cons '(1 2 3) '((4) (5 6)(7 8 9))) => => ((1 4) (2 5 6) (3 7 8 9)) Namnet mapcar kommer av att den för varje steg i avbetandet av listan applicerar den givna funktionen på listans första element. Om man istället vill applicera den på hela den kvarvarande listan används maplist: Jfr (mapcar #'length '((1) (1 2) (1 2 3))) => (1 2 3) med (maplist #'length '((1) (1 2) (1 2 3))) => (3 2 1) Hittills har alla program varit funktionella, dvs ingen setq eller andra s.k. sidoeffekter har förekommit. Om man vill gå igenom en lista utan att samla på sej några värden, man vill bara ha sidoeffekterna utförda, så finns mapc som motsvarighet till mapcar och mapl som motsvarighet till maplist. Utmatningen från (mapc #'print '(1 2 3)) blir: 1 2 3 Utmatningen från (mapl #'print '(1 2 3)) blir: (1 2 3) (2 3) (3) Det finns en rik flora av map- och närbesläktade funktioner. Ex: (some #'oddp '(2 4 5 8)) => t ;finns något udda element? (every #'oddp '(2 4 5 8)) => nil ;är varje element udda? Även funktionerna notevery och notany finns Funktionen reduce är väldigt användbar: (reduce #'+ '(1 2 3 4 5)) => 15 Den opererar ihop alla element på en lista mha funktionen, i detta fall alltså 1+2+3+4+5. (reduce #'cons '(1 2 3 4)) => (((1 . 2) .3) .4) Ajdå, det kanske inte riktigt var vad vi väntade oss. cons är inte associativ, dvs (cons a (cons b c)) är inte samma sak som (cons (cons a b) c). Man kan definiera Commonlispfunktiner så att dom kan ta ett antal optionella (frivilliga) argument. Det ser ut så här i reduce:s fall: (reduce #'cons '(1 2 3 4) :from-end t) => (1 2 3 . 4) Nästan framme. Problemet är att vi inte vill att den innersta cons:en skall vara (cons 3 4) utan (cons 4 nil). Lösning - ytterligare en optionell parameter: (reduce #'cons :from-end t :initial-value nil) => (1 2 3 4) Se vidare boken för en översikt av Commonlisps rika uppsättning av högre ordningens funktioner. Några problem att jobba med --------------------------- 1A: Definiera en funktion list-check som tar två funktioner och en lista som argument och fungerar enligt: (list-check #'(lambda (x y) (and x y)) #'oddp '(1 2 3)) => nil ;Är alla element på lista udda? (list-check #'(lambda (x y) (or x y)) #'oddp '(1 2 3)) => t :Är något element på listan udda? (Man kan alltså inte skicka #'and och #'or som argument. Detta p.g.a. att and och or inte är vanliga funktioner utan s.k. macron.) (list-check #'(lambda (x y) (and x y)) ...) motsvarar alltså every och (list-check #'(lambda (x y) (or x y)) ...) motsvarar any. 1B: Om man definierar (defun xor (x y) (or (and x (not y)) (and (not x) y))) Vad utför då (list-check #'xor ...) vad skulle den alltså kunna kallas för? 2: Definiera en funktion separate som delar upp en given lista i två dellistor efter hur listans element stämmer med ett predikat: (separate #'oddp '(1 2 3 4 5 6 7)) => ((1 3 5 7) (2 4 6)) 3: Definiera två funktioner map-all-1 och map-all-2 som tar en lista av funktioner och en lista av argument och som applicerar varje funktion på varje argument. map-all-1 returnerar en dellista för varje funktion: (map-all-1 (list #'oddp #'1- #'square) (list 1 2 3 4)) => => ((t nil t nil) (0 1 2 3) (1 4 9 16)) map-all-2 returnerar en dellista för varje argument: (map-all-2 (list #'oddp #'1- #'square) (list 1 2 3 4)) => => ((t 0 1) (nil 1 4) (t 2 9) (nil 3 16)) Lab 2 ----- Nu är det ju ganska nära redovisningstillfället, men ni kan ju ändå ha nytta av litet kommentarer: 2A - logikuttryck - - - - - - - - - Tänk på strukturen - inte godtyckliga sekvenser/träd! Kan ett logikuttryck vara · tomt? · en konstant/symbol/atom? 2B o. C - listsökning - - - - - - - - - - - Gör inte samma sökning 2 ggr! B och C är väldigt lika - fast tvärtom ... :-) 2D - traversera binära träd - - - - - - - - - - - - - - Se till att svara på alla frågor! 2E - Pascals triangel - - - - - - - - - - - Ni skall alltså dels skriva generate-list, dels en funktion som generera en ny triangelrad. Lösningar --------- ***STOPP!!!*** ***STANNA!!!*** Fundera litet själv på problemen innan du läser vidare bland lösningarna 1A: Första varianten är ganska rakt på: (defun list-check (ihop-fn element-fn lista) (if (endp lista) '() (funcall ihop-fn (funcall element-fn (first lista)) (list-check ihop-fn element-fn (rest lista))))) ihop-fn och element-fn är ju samma sak i varje rekursivt anrop, så följande variant är också tänkbar: (defun list-check (ihop-fn element-fn lista) (labels ((check-do (lista) (if (endp lista) '() (funcall ihop-fn (funcall element-fn (first lista)) (check-do (rest lista)))))) (check-do lista))) Just i detta fall kanske man inte vinner så mycket på att införa en hjälpfunktion, men det visar i alla fall på konstruktionen med att använda omgivande funktioners variabler. 1B: Varför inte kalla funktionen sant-för-udda-antal ? 2: (defun separate (test-fn lista) (labels ((separate-do (lista t-lista nil-lista) (cond ((endp lista) (list (reverse t-lista) (reverse nil-lista))) ;enklare än att i ;varje steg lägga till nya element sist ((funcall test-fn (first lista)) (separate-do (rest lista) (cons (first lista) t-lista) nil-lista)) (t (separate-do (rest lista) t-lista (cons (first lista) nil-lista)))))) (separate-do lista '() '()))) 3: En första lösning som är ganska rakt på med en rekursiv funktion för att beta av den ena lista, och inuti den en rekursiv funktion för den andra: (defun map-all-1 (fns args) (labels ((map-do (fn args) (if (endp args) '() (cons (funcall fn (first args)) (map-do fn (rest args)))))) (if (endp fns) '() (cons (map-do (first fns) args) (map-all-1 (rest fns) args))))) (defun map-all-2 (fns args) (labels ((map-do (fns arg) (if (endp fns) '() (cons (funcall (first fns) arg) (map-do (rest fns) arg))))) (if (endp args) '() (cons (map-do fns (first args)) (map-all-2 fns (rest args)))))) Ett tema den här lektionen är ju map-funktioner, och här har vi ju en typsituation: att gå igenom varje element på en lista och returnera en lista av resultaten. Båda inre funktionerna kan ersättas med map-anrop: (defun map-all-1 (fns args) (if (endp fns) '() (cons (mapcar (first fns) args) (map-all-1 (rest fns) args)))) (defun map-all-2 (fns args) (if (endp args) '() (cons (mapcar #'(lambda (fn) (funcall fn (first args))) fns) (map-all-2 fns (rest args))))) Självklart kan ju även dom yttre funktionerna ersättas med map-anrop: (defun map-all-1 (fns args) (mapcar #'(lambda (fn) (mapcar fn args)) fns)) (defun map-all-2 (fns args) (mapcar #'(lambda (arg) (mapcar #'(lambda (fn) (funcall fn arg)) fns)) args)) Ta-da! Självklart, eller ...