Haskell Language
Funkcje wyższego rzędu

Uwagi

Podstawy funkcji wyższego rzędu

Przed kontynuowaniem przejrzyj Częściowe zgłoszenie .

W Haskell funkcja, która może przyjmować inne funkcje jako argumenty lub funkcje zwracane, nazywana jest funkcją wyższego rzędu .

Oto wszystkie funkcje wyższego rzędu :

map       :: (a -> b) -> [a] -> [b]
filter    :: (a -> Bool) -> [a] -> [a]
takeWhile :: (a -> Bool) -> [a] -> [a]
dropWhile :: (a -> Bool) -> [a] -> [a]
iterate   :: (a -> a) -> a -> [a]
zipWith   :: (a -> b -> c) -> [a] -> [b] -> [c]
scanr     :: (a -> b -> b) -> b -> [a] -> [b]
scanl     :: (b -> a -> b) -> b -> [a] -> [b]

Są one szczególnie przydatne, ponieważ pozwalają nam tworzyć nowe funkcje oprócz tych, które już mamy, przekazując funkcje jako argumenty do innych funkcji. Stąd nazwa, funkcje wyższego rzędu .

Rozważać:

Prelude> :t (map (+3))
(map (+3)) :: Num b => [b] -> [b]

Prelude> :t (map (=='c'))
(map (=='c')) :: [Char] -> [Bool]

Prelude> :t (map zipWith)
(map zipWith) :: [a -> b -> c] -> [[a] -> [b] -> [c]]

Ta zdolność do łatwego tworzenia funkcji (jak np. Częściowa aplikacja, jak tutaj użyto) jest jedną z cech, która sprawia, że programowanie funkcjonalne jest szczególnie wydajne i pozwala nam uzyskać krótkie, eleganckie rozwiązania, które w innym przypadku zajęłyby dziesiątki linii w innych językach. Na przykład poniższa funkcja podaje liczbę wyrównanych elementów na dwóch listach.

aligned :: [a] ->  [a] -> Int
aligned xs ys = length (filter id (zipWith (==) xs ys))

Wyrażenia lambda

Wyrażenia lambda są podobne do funkcji anonimowych w innych językach.

Wyrażenia lambda to otwarte formuły, które określają również zmienne, które mają zostać powiązane. Ocena (znalezienie wartości wywołania funkcji) jest następnie osiągana przez podstawienie zmiennych powiązanych w ciele wyrażenia lambda argumentami podanymi przez użytkownika. Mówiąc wprost, wyrażenia lambda pozwalają nam wyrażać funkcje poprzez zmienne wiązanie i podstawianie .

Wyglądają wyrażenia lambda

\x -> let {y = ...x...} in y

W wyrażeniu lambda zmienne po lewej stronie strzałki są uważane za związane po prawej stronie, tj. W ciele funkcji.

Rozważ funkcję matematyczną

f(x) = x^2

Jest to definicja Haskella

f    x =  x^2

f = \x -> x^2

co oznacza, że funkcja f jest równoważna wyrażeniu lambda \x -> x^2 .

Rozważ parametr map funkcji wyższego rzędu, czyli funkcję typu a -> b . W przypadku użycia go tylko raz w wywołaniu map i nigdzie indziej w programie, wygodne jest określenie go jako wyrażenia lambda zamiast nazywania takiej funkcji odrzucania. Napisane jako wyrażenie lambda,

\x -> let {y = ...x...} in y

x przechowuje wartość typu a , ...x... jest wyrażeniem Haskella, które odnosi się do zmiennej x , zaś y zawiera wartość typu b . Na przykład moglibyśmy napisać następujące

map (\x -> x + 3)

map (\(x,y) -> x * y)

map (\xs -> 'c':xs) ["apples", "oranges", "mangos"]

map (\f -> zipWith f [1..5] [1..5]) [(+), (*), (-)]

Curry

W Haskell wszystkie funkcje są traktowane jako curry: to znaczy wszystkie funkcje w Haskell wymagają tylko jednego argumentu.

Weźmy funkcję div :

div :: Int -> Int -> Int

Jeśli wywołamy tę funkcję z 6 i 2, nie jest zaskoczeniem, że 3:

Prelude> div 6 2
3

Jednak to nie zachowuje się tak, jak moglibyśmy myśleć. Pierwszy div 6 jest oceniany i zwraca funkcję typu Int -> Int . Ta wynikowa funkcja jest następnie stosowana do wartości 2, która daje 3.

Kiedy patrzymy na podpis typu funkcji, możemy zmienić nasze myślenie z „bierze dwa argumenty typu Int ” na „bierze jeden Int i zwraca funkcję, która przyjmuje Int ”. Jest to potwierdzone, jeśli weźmiemy pod uwagę, że strzałki w notacji typu są powiązane z prawą div , więc div można w rzeczywistości odczytać w ten sposób:

div :: Int -> (Int -> Int)

Ogólnie rzecz biorąc, większość programistów może zignorować to zachowanie przynajmniej podczas nauki języka. Z teoretycznego punktu widzenia „formalne dowody są łatwiejsze, gdy wszystkie funkcje są traktowane jednakowo (jeden argument, jeden wynik)”.