Högre ordningens funktioner

Programmeringsparadigm > Funktionell programmering > Föreläsning 3/4

Strukturen för idag

1. Historisk tillbakablick: Lambdakalkylen från 1930-talet.
2. Immutability
3. Rena funktioner
4. Referenstransparens
5. Lambda i Haskell, Python och Java.
6. Tacit Programming, Point Free Style, underförstådda parametrar
7. Currying
8. Partiell Funktionsapplikation
9. Definiera en högre ordningens funktion.
10. Exemplifiera färdiga högre ordningens funktioner i Haskell: map, filter, foldl
11. Skriva egna högre ordningens funktioner i Haskell: twice.
12. Om vi hinner: Huttons klassiska impementation av The Countdown Problem

Historisk tillbakablick

Lambdakalkyl för er som kan Python eller (modern) Java

1. Det finns konstanter.
2. Det finns variabler, men de är immutable.
3. Det finns uttryck (variabler, konstanter, funktionsanrop och operatorer) med referenstransparens.
4. Funktioner kan definieras med lambdanotation i Haskell, Python och Java.
5. Funktioner är rena och de appliceras, istället för att anropas.
6. Variabler, parametrar och returvärden kan vara funktioner.

Typad lambdakalkyl (typed lambda calculus) är samma sak, men variabler, parametrar och returvärden förväntas hålla sig inom ramarna för en datatyp.

Grundtanken är att allt är (1) funktioner [ även data (abstraktion)] och (2) att tillämpa funktioner (applikation). Haskell kan användas så, men den stödjer även vissa praktiska förenklingar av detta synsätt.

Mutability och immutability

Mutability betyder förändringsbarhet. Immutability betyder oföränderlighet.

I Haskell är variabler i rena funktioner immutable och rena funktioner är default.

I Java och Python är variabler per default mutable, men det finns kommandon för att slå på immutability och det finns verktyg för att göra det.

När C++ var nytt så rådde mutabilty överallt på variabler och objekt, men senare tillkom nyckelordet const. Scott Meyers råder C++-programmerare att “använd const närhelst du kan” i boken Effective C++.

I Rust är immutabilty default och nyckelordet mut slår på mutability.

I kursen skiljer vi på konstanta referenser vilket innebär att en variabel är bundna till ett visst objekt och immutable objects/data structures (oföränderliga/beständiga objekt/datastrukturer)

Rena funktioner och orena funktioner

1. En ren funktion har inga bieffekter. Det betyder att globala variabler, inparametrar är oförändrade och att den inte utför några IO-operationer eller liknande. Bieffekter på tillståndet för cache:ing, CPU-flaggor och statistik för branchtabeller för spekulativ exekvering räknas inte in eftersom dessa följer av att köra någonting över huvud taget på en modern CPU.
2. En ren funktion returnerar alltid samma resultat för samma inparmetrar.

Klassificera dessa Python-funktioner som är inbyggda eller ligger i random eller math:�1. add, mul, sin, cos, abs

2. print, input, random.randint

Referenstransparens

Ett uttryck är referenstransparent om uttrycket helt och hållet kan ersättas med sitt värde.

Uttycket kommer från Russel och Whiteheads bok “Principia Mathematica” (1910, 1912, 1913)

Detta gäller normalt sett i algebraiska beräkningar, men är en ovanlig garanti i programmeringsspråk. Funktionella och deklarativa språk är på det här sättet mer lika matematiken än språk i den imperativa familjen.

​

​

Är uttrycken referenstransparenta?

(Ja, allihopa var referenstranparenta)

Är detta referenstransparent?

Nej, det är det inte

Print har bieffekten att skriva ut och uttrycket i while-satsen får förändrade variabler och värde under programmets körning.

Lambdanotation

Lambdanotation används för att skriva anonyma funktioner i Haskell. Syntaxen består av:

1. Tecknet lambda, men i ASCII är det närmaste backslash \
2. Parametrarna till funktionen, separerade med mellanslag
3. En pil ->
4. Uttrycket som en applikation ska representera.
5. (Kan skippas) En typsignatur. Skriv i så fall steg 1-4 inom parentes.

Exempel:

Enkelt exempel: addition

Prelude> let myadd = (\x y -> x+y):: Int->Int->Int

Prelude> myadd 11.0 1.0

​

<interactive>:7:7: error:

• No instance for (Fractional Int) arising from the literal ‘11.0’

• In the first argument of ‘myadd’, namely ‘11.0’

In the expression: myadd 11.0 1.0

In an equation for ‘it’: it = myadd 11.0 1.0

Prelude> myadd 1 2

3

Prelude> let liberal_add = \x y -> x + y

Prelude> li

liberal_add lines

Prelude> liberal_add 10 12

22

Prelude> :t liberal_add

liberal_add :: Num a => a -> a -> a

Prelude>

​

​

En multiplikationsfunktion med lambda i Haskel, Java och Python

Haskell: \x y -> x*y

Java: (x, y) -> x*y

Python: lambda x,y:x*y

Lambda används ofta i Python för callback

Underförstådda parametrar

Kallas på engelska Tacit Programming eller förvirrande Point Free Style.

Tacit betyder tyst/underförstådd.

Point Free Style betyder inte att funktionskomposition eller punktnotation för att komma åt en medlem är förbjuden. De “punkter” som är bortplockade är parametrarna! Ordet punkt kommer från topologi.

Haskellexempel: (+ 3), (+), (*), och (^2)

​

Currying

Currying är ett sätt att packa upp tupler och skapa en funktion som tar parametrarna i ordning.

Prelude> f = \(a,b)->"stuvning"

Prelude> :t f

f :: (a, b) -> [Char]

Prelude> g = curry f

Prelude> f "pasta" "pesto"

​

<interactive>:9:1: error:

• Couldn't match expected type ‘[Char] -> t’

with actual type ‘[Char]’

• The function ‘f’ is applied to two arguments,

but its type ‘(a0, b0) -> [Char]’ has only one

In the expression: f "pasta" "pesto"

In an equation for ‘it’: it = f "pasta" "pesto"

• Relevant bindings include it :: t (bound at <interactive>:9:1)

​

<interactive>:9:3: error:

• Couldn't match expected type ‘(a0, b0)’ with actual type ‘[Char]’

• In the first argument of ‘f’, namely ‘"pasta"’

In the expression: f "pasta" "pesto"

In an equation for ‘it’: it = f "pasta" "pesto"

Prelude> g "pasta" "pesto"

"stuvning"

Prelude> :t g

g :: a -> b -> [Char]

Prelude>

​

​

Uncurrying - ett sätt att lägga in en tupel i en funktion som är curried (curried function är default i Haskell)

Prelude> :info subtract

subtract :: Num a => a -> a -> a -- Defined in ‘GHC.Num’

Prelude> tuplesub = uncurry subtract

Prelude> tuplesub (3, 10)

7

Prelude> :t tuplesub

tuplesub :: Num c => (c, c) -> c

Prelude> :info subtract

subtract :: Num a => a -> a -> a -- Defined in ‘GHC.Num’

Prelude> :info tuplesub

tuplesub :: Num c => (c, c) -> c -- Defined at <interactive>:27:1

Prelude>

​

Partiell funktionsapplikation

De flesta språk tillåter inte att du anropar en funktion med för få parametrar.

Haskell returnerar i de lägena en funktion där de första argumenten är låsta till de värdena du angav:

Prelude> subthree = subtract 3

Prelude> subthree 45

42

Prelude>

Funktionen subtract i Haskell utläses subtrahera första argumentet från det andra.�En funktion som stödjer partiell applikation är inte automatiskt en Högre Ordningens Funktion. Den är däremot Curry:ad, (curried på engelska).

Vi definierar en högre ordningens funktion

En funktion är en högre ordningens funktion om den uppfyller minst en av dessa:

1. En funktion som tar in en funktion som parameter.
2. En funktion som returnerar en funktion.

Exempel på högre ordningens funktion: Twice

twice :: (a -> a) -> (a -> a) �twice f = f . f �

Matematisk notation:

​

kvadrat x = x*x �Prelude > twice kvadrat 2 �16

map

Tillämpa en funktion på varje element i en lista eller mängd.��Funktionen kan implementeras på 3 rader, inklusive typsignatur!�map1 :: (a -> b) -> [a] -> [b]�map1 _ [] = [] �map1 f (x:xs) = f x : (map1 f xs)� �prelude> map1 (^2) [1,2,3]�[1,4,9] �convertChars :: [Char] -> [Int] �convertChars = map1 fromEnum�*Main> convertChars "Ann"

Är inte map en datastruktur? Nej, det är Map.

I c++ och många andra språk kallas en hashtabell för map, vilket är förvirrande. En datastruktur är inte en högre ordningens funktion. Det är däremot mer likt en funktion än det som kallas funktion i Python...

Python kallar datastrukturen för dictionary.

Java kallar datastrukturen för HashMap.

Haskell kallar datastrukturen för Data.Map (notera stort M)

​

map i Java och Python

Java:�jshell> IntStream.range(1,11).map((x)->{return x*x;}).forEachOrdered(System.out::println)

1

4

9

16

25

36

49

64

81

100

​

jshell> �Python:�>>> list(map(lambda x:x*x, range(1,11)))

[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

>>>

​

​

filter

Välj ut element som uppfyller ett predikat. Ett predikat är en funktion som returnerar bool.

*Main> :t filter

filter :: (a -> Bool) -> [a] -> [a]

*Main>

​

Om vi har en funktion som heter is_prime:

*Main> filter is_prime [1..100]

[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

*Main>

​

P: Den första Parametern är ett Predikat som berättar vad som Passerar filtret.

​

filter kan implementeras på 5 rader

filter1 :: (a -> Bool) -> [a] -> [a]�filter1 _ [] = [] �filter1 predikat (x:xs) � | predikat x = x : filter1 predikat xs � | otherwise = filter1 predikat xs

filter, exempel i Java

IntStream.range(2,100).filter((n)->{for(int i=2; i<n; ++i){if(n%i==0)return false;}return true;}).forEachOrdered(System.out::println)

​

​

filter, exempel i Python

filter är en inbyggd funktion i Python3�>>> list(filter(lambda n:0 not in [n%d for d in range(2,n)], range(2,100)))

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

​

grep i terminalen (bash/zshell) är ett filter

Saol % egrep -e "(n.*){6,}" finalsaol

anrikningsanläggning

fastspänningsanordning

förbränningsanläggning

hornhinnetransplantation

penninginrättning

undanvindsvändning

upphängningsanordning

uppspänningsanordning

utlänningsnämnden

återvinningsanläggning

Saol %

​

foldl, foldr

En fold påminner om map, men ackumulerar värdet.

Sista bokstaven i foldl betyder var ligger det flest parenteser i rad:

Förenklat:�foldl (((((( * ) * ) * ) * ) * ) * )�foldr ( * ( * ( * ( * ( * ( * ))))))

foldr på lista kan implementeras på 4 rader

foldr2 :: (a -> b -> b) -> b -> [a] -> b

foldr2 _ start [] = start

foldr2 f start (x:xs) =

f x (foldr2 f start xs)��Uppgift: implementera foldl?

foldl är ännu enklare

foldl2 :: (b -> a -> b) -> b -> [a] -> b

foldl2 _ start [] = start

foldl2 f start (x:xs) =

foldl2 f (f start x) xs

​

​

​

Användning av foldr

Summera alla tal i en lista

summa = foldr (+) 0

​

Listlängd:

length lst = foldr (\el acc -> acc + 1) 0 lst

�Kortare:

length = foldr (\el acc -> acc + 1) 0�

map kan implementeras mha foldr:

map2 f = foldr (\el rest -> (f el : rest)) []��Kan du implementera den med hjälp av foldl?

​

Implementation av map med foldl

Naiv implementation:�map3 f = foldl (\acc x -> acc ++ [f x]) []

Bättre implementation:�map4 f = reverse . foldl (\acc x -> f x : acc) []

En funktion som returnerar en funktion

Beräkna fakultet med högre ordningens funktioner

Haskell:�Prelude> factorial n = foldl (*) 1 [1..n]�Prelude> factorial 10�3628800

Java:�jshell> IntStream.range(1,11).reduce(1, (x,y)->(x*y))�$4 ==> 3628800

Python:�>>> from operator import mul�>>> from functools import reduce�>>> def factorial(n): return 1 if n==0 else reduce(mul, range(1,n+1))�... �>>> factorial(10)�3628800

The Countdown Problem

Givet en lista med positiva heltal…

1. Välj ut några av dem, utan att upprepa dem
2. Lägg in de fyra räknesätten (du får upprepa räknesätten)
3. …så att resultatet av uttrycket blir ett visst tal som är målet?