пятница, 29 мая 2015 г.

Стрелки (arrows) и бесточечная (pointfree) нотация в haskell на конкретном примере

Стрелка — это модель обобщения вычислительного процесса, когда на вход вычисления может подаваться сразу несколько входных данных (например, в виде кортежа), а сам процесс вычисления строится с помощью комбинаторов типа first, second, (***), (&&&) и (>>>). Бесточечная нотация — это когда при записи функции в выражении (в том числе в ее определении), аргументы опускаются и, соответственно, не связываются (bind) в выражении. Поскольку стрелка абстрагирует входные данные, она выглядит хорошим кандидатом для применения в бесточечной нотации. Рассмотрим применение стрелки и бесточечной нотации на простом примере. Я взял его из очередного твита в 1HaskellADay. Задача простейшая — вывести на экран счет от целого числа from до целого числа to без использования явных циклов. Явные циклы в haskell, да и вообще в функциональном программировании, очень не приветствуются, поскольку относятся к миру императивного программирования. Поэтому данная задача выглядит простой и, в общем-то, таковой и является. Так как я собираюсь привести несколько решений, имеет смысл написать осто́вную функцию count, которая будет принимать основную функцию вычисления счета, передавать ей входные значения from и to, и выводить счет на экран.
count :: (Int -> Int -> [Int]) -> Int -> Int -> IO ()
count f from to = mapM_ print $ f from to
Здесь можно добавить проверку на то, что from меньше to, но я этого не сделал для простоты. Самую очевидную реализацию функции f я назвал cheating, поскольку в ней используется синтаксический сахар, предоставленный самим языком как раз для создания непрерывно возрастающего списка от некоторого числа m до некоторого числа n.
cheating from to = [from .. to]
Совершенно очевидное и незамысловатое решение. Его можно проверить в ghci или в функции main с помощью вызова
count cheating 1 10
Теперь простое решение без использования сахара haskell.
simple from to = takeWhile (<= to) . iterate succ $ from
Тоже несложно. Функция iterate succ строит бесконечный непрерывно увеличивающийся список, который начинается со значения from. Этот список трассируется функцией takeWhile до тех пор, пока выполняется предикат в скобках, то есть пока очередное значение в списке не превысит to. Обе функции cheating и simple просты и хороши. Но я бы хотел видеть их в бесточечной нотации, то есть без явного указания и связывания аргументов from и to. К сожалению, это невозможно, поскольку в первом случае синтаксис построения списка-диапазона требует указания обоих значений, а во втором случае значение to используется внутри предиката в самом центре тела функции. И здесь на помощь приходят стрелки! Для их использования необходимо импортировать модуль Control.Arrow.
import Control.Arrow
Я приведу тело функции arrowedPointfree, а ниже объясню, что в нем происходит.
arrowedPointfree = curry $ iterate succ *** (>=) >>> uncurry (flip takeWhile)
Видите, никаких from и to. Они неявно присутствуют в определении функции, но не связаны внутри ее тела. Оба аргумента склеиваются функцией curry в кортеж и передаются в вычислительный процесс, собранный из функций и стрелок, который начинается за символом $. Следуя традиции графического изображения стрелочных вычислений (см. здесь), я представлю (в меру своих художественных способностей) этот процесс вычисления на картинке.
Итак, кортеж (from, to) поступает на вход стрелочного комбинатора (***). Первый элемент кортежа (from) поступает на вход функции iterate succ, формируя бесконечный возрастающий список [from ..], второй (to) — на вход функции (>=), формируя новую функцию (>=) to. Заметьте, в функции simple мы использовали сечение (<= to). Наша новая функция эквивалентна сечению (to >=), что соответствует предикату из simple. На выходе комбинатора (***) новый кортеж ([from ..], (>=) to) поступает на оператор композиции (>>>), который передает вычисление в функцию uncurry. Функция uncurry декомпонует кортеж в последовательность двух аргументов (я изобразил это сужением вычислительного конвейера) и вызывает функцию flip takeWhile. Функция flip нужна для того, чтобы переставить аргументы [from ..] и (>=) to местами, сформировав takeWhile ((>=) to) [from ..]. Дело сделано! Не находите это решение красивым? Лично я нахожу. Это несмотря на то, что функции cheating и simple выглядят и проще, и понятнее. Но здесь нам удалось абстрагироваться от входных данных и сосредоточиться на потоке вычислений. Да, поначалу стрелки выглядят сложными, но только до тех пор, пока процесс вычисления не представлен графически. Есть еще один аспект. Часто в погоне за возможностью выразить код в бесточечном стиле (pointfree), программисты вынужденно усложняют понимание исходного кода, превращая его в pointless (бессмысленный). Поначалу я случайно назвал функцию arrowedPointfree arrowedPointless, и не сразу оценил всю глубину смысловой нагрузки этой оговорки. В этой статье приводится пример подобного усложнения (по мнению автора) и также обыгрываются синонимы pointfree и pointless. С другой стороны, невозможность записать выражение в бесточечном стиле может свидетельствовать об излишней монолитности функции. Попробуйте записать определение нашей осто́вной функции count в бесточечном стиле. Например,
count :: (Int -> Int -> [Int]) -> Int -> Int -> IO ()
count = mapM_ print
Этот вариант просто не скомпилируется: ghc пожалуется на то, что в функцию map передается слишком много аргументов. Максимальный уровень бесточечности, который можно выжать в определении функции count с такой сигнатурой, заключается в возможности опустить последний аргумент to, соединив mapM_ print и f from оператором (.).
count :: (Int -> Int -> [Int]) -> Int -> Int -> IO ()
count f from = mapM_ print . f from
Почему мы не можем выразить определение count в бесточечном стиле? Потому что мы намеренно усложнили ее определение, фактически объединив две разные функции в одну. Но в общем случае, зачем функции count знать о какой-то другой функции, принимающей какие-то аргументы и возвращающей список [Int]? Ей достаточно знать последний факт, то есть то, что она работает со списком целых чисел. Исходя из этого, определение count можно переписать в виде
count :: [Int] -> IO ()
count = mapM_ print
Вот и бесточечная нотация! Глядя на такое простое определение, мы можем заключить, что функция count нам вообще не нужна, это же просто mapM_ print, которую можно комбинировать напрямую в месте вызова. Например,
mapM_ print $ arrowedPointfree 1 10
Правда, в этом варианте пропало слово счет (count), но это уже вопрос правильного именования функций: при отсутствии осто́вной функции все функции счета следует переименовать.

Комментариев нет:

Отправить комментарий