Мыслим Pointfree

Pointfree. Думаю многим уже знакомо это слово. Каждый уважающий себя Haskell-программист должен овладеть этим кунг-фу.

Это не сложно.

Так что же такое pointfree style? Вот вырезка из русскоязычной Википедии:

Комбинáторное программирование (англ. function-level programming)  — это парадигма программирования, не требующая явного упоминания аргументов определяемой функции (программы) и использующая вместо переменных комбинаторы и композицию функций.

Простым языком, pointfree style - это такой стиль программирования (парадигма), который не требует явного упоминания аргументов определяемой функции, используя для этого комбинаторы и композицию функций.

Что ж, простым языком не получилось.  На самом деле цитата из Википедии написана максимально простым языком. И если вас это смущает, можете обратиться к ссылкам, которые я специально оставил в вырезке.

Pointfree с одним аргументом

Изучение pointfree стоит начать с примеров, ибо они позволяют прийти к мастерству наиболее быстро.

Мы имеем функцию, которая получает аргумент, превращает его в строку и выводит на экран:

x :: Show a => a -> IO ()
x a = putStrLn $ show a

Несложная функция. Но мы записали её в pointful варианте. А теперь запишем в pointfree.

x :: Show a => a -> IO ()
x = putStrLn . show

Мы убрали аргумент a (...не требует явного упоминания аргументов...) и использовали оператор (.) (композиция функций).

Порядок вычисления идет справа налево. Т.е. сначала к полученному аргументу применяется функция show, а далее результат выполнения (show аргумент) передается в функцию putStrLn.

Также вы можете рассуждать по такому принципу: "Аргумент a крайний до знака равно и крайний после знака равно. Раз он и там, и там крайний - то мы его отбросим."

f a = map show a
f   = map show

Я не думаю, что это сложно. Особо любознательные могут заметить, что здесь надо было использовать функцию print из Prelude. Т.е. писать просто:

x = print

Ибо функция print определена следующим образом:

print x = putStrLn (show x)

Что равнозначно нашему определению. Но в учебных целях мы можем об этом забыть.

Вот еще парочка примеров:

filterSpaces x = filter (\c -> c /= ' ') x
filterSpaces   = filter (\c -> c /= ' ')
filterSpaces   = filter (/= ' ')

-- | Функция, для удаления лишних пробелов.
stripWs x = unwords $ words x
stripWs   = unwords . words

Pointfree и арифметика
Эту тему я не зря вынес в отдельную, ибо она часто вызывает затруднения.

Простые примеры:

addOne x = x + 1
add = (+1)

add x y = x + y
add = (+)

mult x y = x * y
mult = (*)

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

sub x y = x - y
sub = (-)

div x y = x / y
div = (/)

Хорошо, тут понятно. Что же делать, если нужно поменять порядок аргументов?

Вспоминаем функцию flip, которая переворачивает порядок получения аргументов у принимаемой функции. Для функции (-) также можно использовать (+).

subOne x = x - 1
subOne   = flip (-) 1
subOne   = (+ (-1))

-- тут уже проще
oneSub x = 1 - x
oneSub   = (1 -)

sub' x y = y - x
sub'     = flip (-)

ourDiv x y = x / y
ourDiv     = (/)

ourDiv' x y = y / x
ourDiv'     = flip (/)

divByTwo x = x / 2
divByTwo   = ( / 2)

twoDivBy x = 2 / x
twoDivBy   = (2 /)

Использование pointfree с двумя и более операторами

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

В этой статье я ваш мастер. И вам, как лучшему моему ученику, я открою секретную технику.
Эта техника пришла ко мне не во время бурных медитаций с GHCI. Пришла она не из уст других мастеров.
Это техника пришла ко мне ночью, в то время когда птицы уже начинали просыпаться, а я не мог заснуть из-за сильнейшего потока мыслей.
Она проста, но в тоже время я не видел упоминания подобного в англоязычной литературе. Суть её в точках. Да-да, в точках.
Сколько параметров - столько точек!

На самом деле, чтобы понять причины - достаточно взглянуть на тип функции (.). Первый и второй аргумент функции (.) - функция с одним аргументом.

(.) :: (b -> c) -> (a -> b) -> a -> c

Но зачем вспоминать тип, когда тут можно просто запомнить "правило точек"? Это ведь очень просто!

Если я вас попрошу написать функцию, которая фильтрует по заданным условиям, а затем выводит отфильтрованный список на экран, то вероятно вы напишите что-то такое:

filterThenPrint p y = print $ filter p y

Верно. А что если в pointfree style? Ученик, который забыл мои учения - выдаст такой вариант и не моргнет глазом:

filterThenPrint = print . filter

Но эта ошибка. Ведь сколько параметров - столько и точек!

filterThenPrint :: Show a => (a -> Bool) -> [a] -> IO ()
filterThenPrint = (print .) . filter

Две точки - два параметра! Заметьте, что тут был явно указан тип. Без этого функция не будет работать.

Рассуждать можно так:

filterThenPrint p y = print $ filter p y -- y крайнее, убираем и ставим точку
filterThenPrint p   = print . filter p -- p крайнее, убираем и ставим точку
filterThenPrint     = (print .) . filter

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

Для закрепления материала - пример с тремя параметрами:

f x y z = x + y - z
x' :: Int -> Int -> Int -> IO ()
x' = ((print .) .) . f

Pointfree package

Соревнования по составлению pointfree выражений имело бы смысл, если бы не замечательный пакет "pointfree" из Hackage. Он позволяет превратить почти любое pointful выражение в pointfree.

$ cabal install pointfree
$ pointfree "f x = putStrLn $ show x"
f = putStrLn . show

Многим известный lambdabot, который обитает на irc-каналах также владеет pointfree-фу.

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

The Owl

На картинке, с которой начинается статья, вовсе не испуганное лицо, как вы могли подумать.
Это функция под названием "The Owl". Было бы неправильно оставить её без внимания.

The Owl имеет следующее определение и сигнатуру:

((.)$(.)) :: (a -> b -> c) -> a -> (g -> b) -> g -> c

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

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

((.)$(.)) map show (filter (> 0)) [-1,-2,5,2,-3,-4,8,99]
>["5","2","8","99"]
((.)$(.)) (+) 10 (*2) 5
>20

Итог

Знания не должны нести вред. Как и боевое искусство, знания должны быть использованы во благо. 

Поэтому пишите правильно! ;)