Каррирование и замыкания

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

Каррирование

В хаскеле все функции изначально являются каррированными, т.е. они принимают 1 аргумент, продуцируя новую функцию, которая принимает ещё один аргумент и т.д. Есть 2 встроенные функции, позволяющие производить операции каррирования: curry и uncurry.

import Data.Typeable

curriedPower :: Integer -> Integer -> Integer
curriedPower a 1 = a
curriedPower a n = a * curriedPower a (n - 1)

main = do
    print $ typeOf curriedPower
    print $ curriedPower 2 10
    let uncurriedPower = uncurry curriedPower
    print $ typeOf uncurriedPower
    print $ uncurriedPower (2, 10)

    {-
	OUTPUT:
	Integer -> Integer -> Integer
        1024
        (Integer,Integer) -> Integer
        1024
    -}

Функция декаррирования создаёт функцию от 2-х аргументов, что в описании функции описано как (Integer,Integer) -> Integer. Каррированная форма является более удобной, поскольку она позволяет выполнять частичное применение функции. На практике это означает, что имеется возможность зафиксирововать 1 и более аргументов какими-либо значения, получив новую функцию с меньшим числом аргументов:

power :: Integer -> Integer -> Integer
power a 1 = a
power a n = a * power a (n - 1)

sqr a = power a 2
base n = power 2 n

main :: IO ()
main = do
  print $ sqr 4
  print $ base 3

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

import Data.List

insertionSort xs = foldr insert [] xs

main = do
    let xs = insertionSort [5, 3, 9, 5, 6, 1, 2, 4, 8, 7]
    print xs

Замыкания

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

f x = (\y -> x + y)

main = do
    print $ f 3 2

Функция f возвращает замыкание, поскольку в абстрактной функции (\y -> x + y) переменная x не используется, а её значение определяется извне через аргумент функции f. Стоит напомнить, что абстрактная функция имеет следующий вид записи: (\аргументы -> выражение), здесь обратная черта заменяет греческую букву λ, используемую в лямбда исчислении, а -> отделяет аргументы функции от тела функции. В математической форме описываемая функция записывается как .