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

Question

В настоящее время я прохожу курс функционального программирования, и меня довольно удивляет концепция функций и функций высшего порядка как граждан первого класса.Однако я пока не могу придумать много практически полезных, концептуально удивительных или просто интересных функций высшего порядка.(Помимо типичных и довольно скучных функций map, filter и т. Д.).

Знаете ли вы примеры таких интересных функций?

Может быть, функции, которые возвращают функции, функции, которые возвращают списки функций (?) И т. Д.

Я был бы признателен за примеры в Haskell, который является языком, который я изучаю в настоящее время:)

Answer 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 использует эти функции - делая ихвесьма полезно!

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

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

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

Answer 2

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

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

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

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

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

Answer 3

Я действительно почувствовал силу, когда узнал, что функция может быть частью структуры данных. Вот «потребительская монада» (technobabble: бесплатная монада свыше (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))

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

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

Answer 4

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

Answer 5

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

Answer 6

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

f :: A -> B -> C

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

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

Функция без каррирования с двумя аргументами будет иметь такой тип:

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

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

Answer 7

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

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

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

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

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

Answer 8

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

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

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

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

Answer 9

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

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

Answer 10

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

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

runWith funcs samples = map ($samples) funcs

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