Кои са някои интересни приложения на функции от по-висок ред?

Е, забелязахте, че 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 използва тези функции - което ги прави доста полезни!

Те са първата стъпка към добрата абстракция, защото вече можем да включим потребителско поведение в скелетна функция с общо предназначение.

По-конкретно, монадите са възможни само защото можем да свързваме заедно и да манипулираме функции, за да създаваме програми.

Факт е, че животът е доста скучен, когато е от първи ред. Програмирането става интересно само след като имате по-висок ред.

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

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

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

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

Така че моят отговор би бил, че функциите от по-висок ред често се използват за изпълнение на същите видове задачи, които изпълняват OO програмистите, но директно и с много по-малко шаблони.

Наистина започнах да усещам силата, когато научих, че една функция може да бъде част от структура от данни. Ето една "потребителска монада" (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))

Това изразходва 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

Тук се случват всякакви добрини от по-висок порядък, някои от които са споменати в други отговори. Но искам да посоча функцията '$'. Когато за първи път видях това използване на '$', бях поразен. Преди това не го смятах за много полезен, освен като удобен заместител на скобите...но това беше почти магическо...

Едно нещо, което е доста забавно, макар и не особено практично, е Church Numerals. Това е начин за представяне на цели числа, като се използват само функции. Луд, знам. ‹shamelessPlug>Ето една имплементация в JavaScript, която направих. Може да е по-лесно за разбиране от реализация на Lisp/Haskell. (Но вероятно не, ако трябва да бъда честен. JavaScript всъщност не е предназначен за подобни неща.)‹/shamelessPlug>

Беше споменато, че Javascript поддържа определени функции от по-висок порядък, включително есе от Джоел Сполски. Марк Джейсън Доминус написа цяла книга, наречена Higher–Order 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/*");

or

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

Има много повече от това, но това е само вкус. Затварянията улесняват създаването на генератори на функции, писане на ваши собствени функции от по-висок ред, а не само използване на вградените. Всъщност един от най-често срещаните модели на изключение,

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

е не вградена. Това обаче е почти тривиално дефинирано, като try е функция, която приема два аргумента: затваряне в първия аргумент и функция, която приема затваряне във втория.

Perl 5 няма вградено currying, въпреки че има модул за това. Perl 6 обаче има къри и първокласни продължения, вградени направо в него, плюс много повече.