Haskell Language
Функции более высокого порядка

замечания

Основы функций более высокого порядка

Просмотрите частичное приложение перед продолжением.

В Haskell функция, которая может принимать другие функции в качестве аргументов или возвращаемых функций, называется функцией более высокого порядка .

Ниже перечислены все функции более высокого порядка :

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]

Они особенно полезны в том, что они позволяют нам создавать новые функции поверх тех, которые у нас уже есть, передавая функции в качестве аргументов другим функциям. Отсюда и название, функции более высокого порядка .

Рассматривать:

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

Эта способность легко создавать функции (например, частичное приложение, как используется здесь) является одной из функций, которая делает функциональное программирование особенно мощным и позволяет нам выводить короткие, элегантные решения, которые в противном случае занимали бы десятки строк на других языках. Например, следующая функция дает нам количество выровненных элементов в двух списках.

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

Лямбда-выражения

Лямбда-выражения аналогичны анонимным функциям на других языках.

Лямбда-выражения - это открытые формулы, которые также определяют переменные, которые должны быть связаны. Затем оценка (поиск значения вызова функции) достигается путем подстановки связанных переменных в тело лямбда-выражения с предоставленными пользователем аргументами. Проще говоря, лямбда-выражения позволяют нам выражать функции посредством привязки переменных и их замены .

Лямбда-выражения выглядят

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

В пределах лямбда-выражения переменные в левой части стрелки считаются связанными в правой части, т. Е. Телом функции.

Рассмотрим математическую функцию

f(x) = x^2

В качестве определения Haskell это

f    x =  x^2

f = \x -> x^2

что означает, что функция f эквивалентна лямбда-выражению \x -> x^2 .

Рассмотрим параметр map функции высшего порядка, являющийся функцией типа a -> b . Если он используется только один раз в вызове для map и нигде в программе, его удобно указывать как выражение лямбда вместо того, чтобы называть такую ​​функцию throwaway. Написанное в виде лямбда-выражения,

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

x имеет значение типа a , ...x... является выражением Haskell, которое ссылается на переменную x , а y имеет значение типа b . Так, например, мы могли бы написать следующее

map (\x -> x + 3)

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

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

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

Карринг

В Haskell все функции считаются curried: то есть все функции в Haskell принимают только один аргумент.

Возьмем функцию div :

div :: Int -> Int -> Int

Если мы будем называть эту функцию 6 и 2, то неудивительно получим 3:

Prelude> div 6 2
3

Однако это не совсем так, как мы думаем. Первый div 6 оценивается и возвращает функцию типа Int -> Int . Затем эта полученная функция применяется к значению 2, которое дает 3.

Когда мы смотрим на подпись типа функции, мы можем перенести наше мышление с «принимает два аргумента типа Int » на «принимает один Int и возвращает функцию, которая принимает Int ». Это подтверждается, если учесть, что стрелки в обозначении типа связаны справа , поэтому div фактически можно читать следующим образом:

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

В общем, большинство программистов могут игнорировать это поведение, по крайней мере, пока они изучают язык. С теоретической точки зрения , «формальные доказательства легче, когда все функции обрабатываются равномерно (один аргумент в, один результат)».