Какие есть интересные применения функций высшего порядка?

Вы заметили, что в Haskell нет синтаксиса для циклов? Нет while или do или for. Потому что это всего лишь функции высшего порядка:

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

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

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

 unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

 iterate :: (a -> a) -> a -> [a]

Функции высшего порядка заменяют необходимость встроенного синтаксиса языка для управляющих структур, а это означает, что почти каждая программа на Haskell использует эти функции, что делает их весьма полезными!

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

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

Дело в том, что жизнь довольно скучна, когда она первоклассна. Программирование становится интересным только тогда, когда у вас есть более высокий порядок.

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

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

Шаблон стратегия — это еще один пример схемы, которая часто передает объекты в качестве аргументов вместо того, что на самом деле предназначено, т. е. функций.

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

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

Я действительно почувствовал силу, когда узнал, что функция может быть частью структуры данных. Вот "потребительская монада" (техноболтовня: бесплатная монада над (i ->)).

data Coro i a
    = Return a
    | Consume (i -> Coro i a)

Таким образом, Coro может либо мгновенно дать значение, либо быть другим Coro в зависимости от некоторого ввода. Например, это Coro Int Int:

Consume $ \x -> Consume $ \y -> Consume $ \z -> Return (x+y+z)

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

sumStream :: Coro Int Int
sumStream = Consume (go 0)
    where
    go accum 0 = Return accum
    go accum n = Consume (\x -> go (accum+x) (n-1))

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

Функции в структурах данных — очень мощный инструмент, который не был частью моего лексикона до того, как я начал работать с Haskell.

Ознакомьтесь с документом 'Даже функции высшего порядка для синтаксического анализа или почему Кто-нибудь когда-нибудь хотел использовать функцию шестого порядка?» Криса Окасаки. Он написан с использованием ML, но идеи в равной степени применимы и к Haskell.

Джоэл Спольски написал известное эссе, демонстрирующее, как Map-Reduce работает с использованием функций высшего порядка JavaScript. Обязательна к прочтению всем, кто задается этим вопросом.

Функции более высокого порядка также требуются для каррирования, которое Haskell использует повсеместно. По сути, функция, принимающая два аргумента, эквивалентна функции, принимающей один аргумент и возвращающей другую функцию, принимающую один аргумент. Когда вы видите такую ​​сигнатуру типа в Haskell:

f :: A -> B -> C

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

f :: A -> (B -> C)

Некаррированная функция с двумя аргументами вместо этого имела бы такой тип:

f' :: (A, B) -> C

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

Мартин Эскардо приводит интересный пример функции высшего порядка:

equal :: ((Integer -> Bool) -> Int) -> ((Integer -> Bool) -> Int) -> Bool

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

Мой Haskell довольно ржавый, поэтому я не могу легко привести вам пример Haskell, но вот упрощенный пример Clojure, который, надеюсь, передает концепцию:

(defn make-object [initial-value]
  (let [data (atom {:value initial-value})]
      (fn [op & args]
        (case op 
          :set (swap! data assoc :value (first args))
          :get (:value @data)))))

Использование:

(def a (make-object 10))

(a :get)
=> 10

(a :set 40)

(a :get)
=> 40

Тот же принцип будет работать в Haskell (за исключением того, что вам, вероятно, потребуется изменить операцию set, чтобы вернуть новую функцию, поскольку Haskell является чисто функциональным)

Я особый поклонник мемоизации более высокого порядка:

memo :: HasTrie t => (t -> a) -> (t -> a)

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

Это из http://hackage.haskell.org/package/MemoTrie.

Здесь есть несколько примеров: http://www.haskell.org/haskellwiki/Higher_order_function

Я также рекомендую эту книгу: http://www.cs.nott.ac.uk/~gmh/book.html, который является отличным введением во все аспекты Haskell и охватывает функции более высокого порядка.

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

Вот небольшой перефразированный фрагмент кода:

rays :: ChessPieceType -> [[(Int, Int)]]
rays Bishop = do
  dx <- [1, -1]
  dy <- [1, -1]
  return $ iterate (addPos (dx, dy)) (dx, dy)
...  -- Other piece types

-- takeUntilIncluding is an inclusive version of takeUntil
takeUntilIncluding :: (a -> Bool) -> [a] -> [a]

possibleMoves board piece = do
  relRay <- rays (pieceType piece)
  let ray = map (addPos src) relRay
  takeUntilIncluding (not . isNothing . pieceAt board)
    (takeWhile notBlocked ray)
  where
    notBlocked pos =
      inBoard pos &&
      all isOtherSide (pieceAt board pos)
    isOtherSide = (/= pieceSide piece) . pieceSide

При этом используются несколько функций «высшего порядка»:

iterate :: (a -> a) -> a -> [a]
takeUntilIncluding  -- not a standard function
takeWhile :: (a -> Bool) -> [a] -> [a]
all :: (a -> Bool) -> [a] -> Bool
map :: (a -> b) -> [a] -> [b]
(.) :: (b -> c) -> (a -> b) -> a -> c
(>>=) :: Monad m => m a -> (a -> m b) -> m b

(.) — это оператор ., а (>>=) — это do-нотация «оператор разрыва строки».

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

Вот шаблон, о котором я еще не видел, чтобы кто-то еще упоминал, который действительно удивил меня, когда я впервые узнал о нем. Рассмотрим пакет статистики, в котором у вас есть список выборок в качестве входных данных, и вы хотите рассчитать по ним множество различных статистических данных (есть также множество других способов мотивировать это). Суть в том, что у вас есть список функций, которые вы хотите запустить. Как вы их всех запускаете?

statFuncs :: [ [Double] -> Double ]
statFuncs = [minimum, maximum, mean, median, mode, stddev]

runWith funcs samples = map ($samples) funcs

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

Одна вещь, которая довольно забавна, хотя и не особенно практична, — это Церковные числительные. Это способ представления целых чисел с использованием только функций. Сумасшедший, я знаю. ‹shamelessPlug>Вот реализация на JavaScript, которую я сделал. Это может быть проще для понимания, чем реализация Lisp/Haskell. (Но, если честно, вероятно, нет. JavaScript не был предназначен для таких вещей.)‹/shamelessPlug>

Было упомянуто, что Javascript поддерживает некоторые функции более высокого порядка, включая эссе Джоэла Спольски< /а>. Марк Джейсон Доминус написал целую книгу под названием Perl высшего порядка; исходный код книги доступен для бесплатной загрузки в различных форматах, включая PDF.

@ARGV    = map { /\.gz$/ ? "gzip -dc < $_ |" : $_ } @ARGV;

@unempty = grep { defined && length } @many;

@txtfiles = map { $_->[1] }
            sort { 
                    $b->[0]  <=>     $a->[0]
                              ||
                 lc $a->[1]  cmp  lc $b->[1]
                              ||
                    $b->[1]  cmp     $a->[1]
            }
            map  { -s => $_ } 
            grep { -f && -T }
            glob("/etc/*");

@sorted_lines = map { $_->[0] }
                sort {
                     $a->[4] <=> $b->[4] 
                             ||
                    $a->[-1] cmp $b->[-1]
                             ||
                     $a->[3] <=> $b->[3]
                             ||
                     ...
                }
                map { [$_ => reverse split /:/] } @lines;

$sum = reduce { $a + $b } @numbers;

$max = reduce { $a > $b ? $a : $b } $MININT, @numbers;

try {
   something();
} catch {
   oh_drat();
};