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

Ответ 1

Хорошо, вы заметили, что у 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 использует эти функции, что делает их весьма полезными!

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

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

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

Ответ 2

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

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

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

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

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

Ответ 3

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

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

Таким образом, 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, а затем потребляет намного больше интов, прежде чем давать их сумму. Это можно рассматривать как функцию, которая принимает произвольно много аргументов, построенных без какой-либо языковой магии, только функций более высокого порядка.

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

f :: A -> B -> C

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

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

Вместо неточной операции двух аргументов вместо этого будет иметь вид типа:

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

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

Ответ 7

Martín Escardó предоставляет интересный пример функции более высокого порядка:

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

Учитывая два функционала f, g :: (Integer -> Bool) -> Int, тогда equal f g решает, являются ли (t23 > и g равными или нет, хотя f и g не имеют конечной области. На самом деле кодомен, Int, может быть заменен любым типом с разрешимым равенством.

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

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

Ответ 8

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

Мой 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 является чисто функциональным)

Ответ 9

Я являюсь частным фанатом воспоминаний более высокого порядка:

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

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

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

Ответ 10

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

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

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

Ответ 11

Вот небольшой фрагмент code:

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 -notation ".

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

Ответ 12

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

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

runWith funcs samples = map ($samples) funcs

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

Ответ 13

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

Ответ 14

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

С тех пор, как минимум Perl 3, Perl поддерживает функциональность, более напоминающую Lisp, чем C, но до тех пор, пока Perl 5 не будет полностью поддерживать закрытие, и все, что следует из этого, было доступно. И первая из первых реализаций Perl 6 была написана в Haskell, которая оказала большое влияние на развитие этого языка.

Примеры подходов функционального программирования в Perl появляются в повседневном программировании, особенно с map и grep:

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

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

Так как sort также допускает замыкание, шаблон map/sort/map является супер общим:

@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;

Функция reduce упрощает перехват списка без циклов:

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

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

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

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

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

Perl 5 не имеет встроенного currying, хотя для этого есть модуль. Perl 6, однако, имеет карьеры и первоклассные продолжения, встроенные в него, плюс намного больше.