Haskell Language
Högre ordningsfunktioner

Anmärkningar

Grunderna i funktioner för högre ordning

Granska delvis ansökan innan du fortsätter.

I Haskell kallas en funktion som kan ta andra funktioner som argument eller returnera funktioner en funktion av högre ordning .

Följande är alla högre ordningsfunktioner :

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]

Dessa är särskilt användbara eftersom de tillåter oss att skapa nya funktioner ovanpå de som vi redan har, genom att överföra funktioner som argument till andra funktioner. Därför namnet, högre ordning funktioner .

Överväga:

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]]

Denna förmåga att enkelt skapa funktioner (som t.ex. genom delvis applikation som används här) är en av funktionerna som gör funktionell programmering särskilt kraftfull och gör att vi kan härleda korta, eleganta lösningar som annars skulle ta dussintals rader på andra språk. Följande funktion ger exempelvis antalet justerade element i två listor.

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

Lambda-uttryck

Lambda-uttryck liknar anonyma funktioner på andra språk.

Lambda-uttryck är öppna formler som också specificerar variabler som ska bindas. Utvärdering (att hitta värdet på ett funktionssamtal) uppnås sedan genom att de bundna variablerna i lambda-uttryckets kropp ersätts med de användartillhandahållna argumenten. Enkelt uttryckt, lambda-uttryck tillåter oss att uttrycka funktioner genom variabel bindning och substitution .

Lambda-uttryck ser ut

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

Inom ett lambda-uttryck anses variablerna på pilens vänstra sida vara bundna i höger sida, dvs. funktionens kropp.

Tänk på den matematiska funktionen

f(x) = x^2

Som en Haskell-definition är det

f    x =  x^2

f = \x -> x^2

vilket betyder att funktionen f är ekvivalent med lambda-uttrycket \x -> x^2 .

Tänk på parametern för högre ordningens funktion map , som är en funktion av typ a -> b . Om det bara används en gång i ett samtal för att map och ingen annanstans i programmet är det bekvämt att specificera det som ett lambda-uttryck istället för att namnge en sådan kast-funktion. Skrivet som ett lambda-uttryck,

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

x har ett värde av typ a , ...x... är ett Haskell-uttryck som hänvisar till variabeln x , och y har ett värde av typ b . Så vi kan till exempel skriva följande

map (\x -> x + 3)

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

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

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

Currying

I Haskell betraktas alla funktioner som curried: det vill säga att alla funktioner i Haskell tar bara ett argument.

Låt oss ta funktionen div :

div :: Int -> Int -> Int

Om vi kallar den här funktionen med 6 och 2 får vi förvånansvärt 3:

Prelude> div 6 2
3

Men detta fungerar inte riktigt på det sätt vi kanske tror. Första div 6 utvärderas och returnerar en funktion av typen Int -> Int . Denna resulterande funktion appliceras sedan på värdet 2 som ger 3.

När vi tittar på typsignaturen för en funktion kan vi flytta vårt tänkande från "tar två argument av typ Int " till "tar en Int och returnerar en funktion som tar en Int ". Detta bekräftas om vi betraktar att pilar i typnotationen associerar till höger , så div kan faktiskt läsas så:

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

I allmänhet kan de flesta programmerare ignorera detta beteende åtminstone medan de lär sig språket. Ur teoretisk synvinkel är "formella bevis lättare när alla funktioner behandlas enhetligt (ett argument in, ett resultat ut)."