Главная » Haskell » Функции  высшего порядка

0

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

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

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

Можно привести в качестве примера наиболее интересные функции из стандартного модуля Prelude, которые являются функциями высшего порядка:

map  :: (a  ->  b)  ->  [a]  ->  [b] map  _ []          =  []

map  f (x:xs) = (f x):(map   f xs)

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

Другие известные функции высшего порядка — различные виды свёрток списка значений в одно. Например, левоассоциативная свёртка определяется следующим образом (подробно описывается на стр. 253):

foldl :: (a  ->  b ->  a)  ->  a ->  [b] ->  a foldl _ z  []     = z

foldl f z  (x:xs) = foldl f (f z  x) xs

Эта функция «сворачивает» заданный список при помощи заданной функции, используя в качестве  начального значения второй аргумент.  При помощи этой функции, а также  функции для правоассоциативной  свёртки (foldr,  описана на стр. 254) определяются многие частные виды свёртки, в том числе и функции для суммирования элементов списка, получения их произведения и т. д.

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

ки также важна. Пояснить ассоциативность свёртки можно следующими рассуждениями:

Для левоассоциативной свёртки вызов функции foldl

foldl f z  [x1, x2 .. xn]

тождественнен последовательному  применению (эта запись не  имеет смысла на языке Haskell, троеточия используются в качестве замещающего символа):

(…((z ‘f‘ x1)  ‘f‘ x2)  … ‘f‘ xn)

Правоассоциативная свёртка работает иначе. Вызов функции foldr

foldr f z  [x1, x2 .. xn]

опять-таки тождественнен последовательному применению:

(x1  ‘f‘ (x2  ‘f‘ … (xn  ‘f‘ z) … ))

Наконец, осталось привести в качестве примера ещё одну очень интересную функцию из стандартного модуля Prelude. Это функция zipWith, которая принимает на вход функцию и два списка, а возвращает список, состоящий из значений функции, полученных при помощи её применения  к значениям исходных списков. Её определение выглядит следующим образом (а более детально описывается на стр. 269):

zipWith :: (a  ->  b ->  c) ->  [a] ->  [b]  -> [c]  zipWith f (x:xs) (y:ys) = (f x  y):(zipWith f xs  ys)

zipWith _ _

_           = []

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

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

Источник: Душкин Р. В., Справочник по языку Haskell. М.: ДМК Пресс, 2008. 544 с., ил.

По теме:

  • Комментарии