Упражнение в комбинаторах с использованием Haskell
В своем стремлении научиться использовать Haskell я начал решать набор задач Project Euler. Я также увлекся идеей бесточечного или неявного программирования, стиля, в котором аргументы функции неявны, т.е. аргумент функции не имеет точек, на которые он ссылается. (Примечание: в этой статье предполагается базовое понимание синтаксиса и основных функций Haskell, особенно операторов приложения ($) и композиции (.))
Без точек
Термин «бесточечный» не связан с информатикой, но означает он только то, что функция не имеет явных аргументов. Например, addOne n = n + 1 не является безточечным, но мы можем немного изменить определение до addOne = (+) 1, чтобы сделать его безточечным. Последовательность частичного применения и композиции может сделать аргументы неявными в определении.
Мы также можем назвать эти функции и этот стиль «молчаливыми». Английское определение слова tacit: «не произносится» или «подразумевается или выводится из действий или заявлений». В бесточечных функциях аргументы есть, но они не озвучиваются, они неявны.
(Точка не относится к оператору композиции ., на самом деле код без точек имеет много .)
В чем смысл"
Неявное программирование может очень быстро стать очень запутанным, но оно также может быть более чистым способом выражения идей. Как и в любом программном (и инженерном) дизайнерском решении, здесь есть компромиссы.
Возвращаясь к нашему простому примеру с addOne, предположим, что вместо добавления единицы к числу мы хотели увеличить каждое значение в списке на единицу. Наивная реализация может быть addOneList list = map (\n -> n + 1) list. Это, безусловно, сработает, но сразу видно, что лямбда добавляет ненужную сложность. Давайте попробуем отключить это, как в примере с дополнением addOneList list = map ((+) 1) list. Теперь карта читается немного более декларативно как «добавить по одному в каждый элемент списка», но в определении функции все еще есть один аргумент list. Поскольку list является последним аргументом, а также последней вещью в теле функции, мы можем выполнить эта-абстракцию лямбда-исчисления (\x->Ax = A), чтобы получить addOneList = map ((+) 1). Этот код читается намного яснее и лаконичнее, чем тот, с которого мы начали, и является вероятным примером распространенных вариантов использования бесточечного стиля.
Идем глубже
В своем глупом стремлении сделать все, что я пишу на Haskell, бесточечным, я придумал несколько полезных определений и правил.
Эта-сокращение: func x = <stuff> x =› func = <stuff>
Состав:func x = <stuff> $ <stuff2> x =› func x = <stuff> . <stuff2>
Переключение. С определением c (кардинального) комбинатора c f a b = f b a = flip мы можем применить правила композиции и эта-редукции для большего эффекта, например:
--<primes = ...>-- getPrimes n = take n primes getPrimes n = c take primes n --flip getPrimes = c take primes --eta-reduce getMorePrimes n = take (n * 2) primes getMorePrimes n = c take primes (n * 2) --flip getMorePrimes n = c take primes ((*) 2 n) getMorePrimes n = c take primes $ (*) 2 n getMorePrimes = c take primes . (*) 2 --compose
Все вместе это становится трудно читать, но если мы пойдем в обратном направлении, эти определения все еще довольно читабельны и, возможно, даже предпочтительнее (в зависимости от вашей терпимости к комбинаторам). Окончательное определение getMorePrimes можно прочитать так: «умножить входные данные, которые еще предстоит определить, на 2 и передать результат функции, которая примет еще не определенное количество простых чисел». Это, конечно, только один из способов рассуждения, и он немного сумбурный, но я считаю, что рассуждения о композиции в обратном порядке могут быть полезными.
Феникс. С определением комбинатора p(феникс) p a f g x = a (f x) (g x) мы получаем возможность использовать функции с двумя аргументами. p принимает бинарную функцию и две унарные функции. Он применяет аргумент к двум унарным функциям, а затем объединяет результаты с бинарной функцией. Мне нравится думать об этом как об операции «разделить-объединить». Потенциальный вариант использования для фильтрации кратных 5 и 3 из списка:
f35 lat = filter (\x -> (x `mod` 3 /= 0) && (x `mod` 5 /= 0)) lat = filter (\x -> (x `mod` 3 /= 0) && (x `mod` 5 /= 0)) -- eta = filter (\x -> (&&)(x `mod` 3 /= 0) (x `mod` 5 /= 0)) = filter (p (&&) (\x -> x `mod` 3 /= 0) (\x -> x `mod` 5 /= 0)) = filter (p (&&) (\x -> ((/=) 0) $ x `mod` 3 ) (\x -> x `mod` 5 /= 0)) = filter (p (&&) (\x -> ((/=) 0) $ c mod 3 x) (\x -> x `mod` 5 /= 0)) = filter (p (&&) (((/=) 0) . c mod 3) (\x -> x `mod` 5 /= 0)) -- compose f35 = filter (p (&&) (((/=) 0) . c mod 3) (((/=) 0) . c mod 5))
Это окончательное определение еще труднее разобрать. Это все еще возможно, но по мере того, как мы идем дальше, вероятно, лучше всего просто начать с правильной функции «точка-заполнение» и довериться процессу «молчания».
Бесточечный проект Эйлера
Задача 3 требует наибольшего простого делителя числа 600851475143. Мое решение включает функцию biggestDiv :: Integer -> [Integer] -> Integer, которая принимает целое число и список возможных делителей (в данном случае простых чисел) и находит первый из них. Идея состоит в том, что вы можете передать число и список простых чисел в эту функцию, чтобы найти наибольший простой делитель указанного числа.
biggestDiv n potentialDivisors =
if (n == 1)
then (head potentialDivisors)
else
if (mod n (head potentialDivisors) == 0)
then (biggestDiv (n `div` (head potentialDivisors)) potentialDivisors)
else (biggestDiv n (tail potentialDivisors))
Чтобы сделать это неявным, нам нужно новое определение if, которое является функцией, а не ключевым словом.
if' :: Bool -> a -> a -> a if' True x _ = x if' False _ y = y
Отсюда мы получаем
biggestDiv n pd =
if' (n == 1)
(head pd)
(if' (mod n (head pd) == 0)
(biggestDiv (n `div` (head pd)) pd)
(biggestDiv n (tail pd)))
Попробуем сначала исключить крайний левый аргумент pd. Есть две ветви if’, которые используют аргумент pd, которые «объединяются» вместе с (if’ (n == 1)), это выглядит как хорошее место для p!
biggestDiv n =
p (if' (n == 1))
(\pd -> (head pd))
(\pd -> if' (mod n (head pd) == 0)
(biggestDiv (n `div` (head pd)) pd)
(biggestDiv n (tail pd)))
Теперь у нас есть две функции, объединенные с if, и каждая принимает неявный аргумент. К сожалению, мы заменили одну явную точку еще двумя, так что давайте попробуем сделать и эти лямбды неявными.
biggestDiv n =
p (if' (n == 1))
head
(\pd -> if' (mod n (head pd) == 0)
(biggestDiv (n `div` (head pd)) pd)
(biggestDiv n (tail pd)))
Первый был легким! Теперь нам придется проделать тот же трюк с p для этой секунды if, но немного по-другому, так как предикат также нуждается в pd. Здесь нам также придется несколько раз использовать комбинатор Haskell s (<*>). f <*> g = \x -> fx(gx) похоже на p, но один аргумент передается напрямую, а не через функцию. Вы также можете думать о <*> как о применении f к g после того, как они оба приняли аргумент. Здесь мы начинаем пропускать шаги, так что старайтесь не отставать или просто наслаждайтесь!
biggestDiv n =
p (if' (n == 1))
head
(\pd -> (p if'
(((==) 0) . mod n . head)
((c biggestDiv) <*> (div n . head)) pd)
(biggestDiv n (tail pd)))
-- use an s to chain the first part of the if to the else clause
biggestDiv n =
p (if' (n == 1)) head
((<*>) ((p if')
(((==) 0) . mod n . head)
(c biggestDiv <*> (div n . head)))
(biggestDiv n . tail))
pd больше нет! Теперь, чтобы устранить n. Это становится намного сложнее, так как мы должны начать переворачивать аргументы.
biggestDiv =
(\n -> (c p) head (if' $ (==) 1 n)) <*>
(\n -> (<*>) ((p if')
(((==) 0) . mod n . head)
(c biggestDiv <*> (div n . head)))
(biggestDiv n . tail))
-- flip to eliminate first lambda
biggestDiv =
((c p) head . if' . (==) 1) <*>
(\n -> (<*>) ((p if')
(((==) 0) . mod n . head)
(c biggestDiv <*> (div n . head)))
(biggestDiv n . tail))
-- use a p to pass the n to the two functions applied to <*>
biggestDiv =
((c p) head . if' . (==) 1) <*>
(p (<*>) (\n -> (p if')
(((==) 0) . mod n . head)
(c biggestDiv <*> (div n . head)))
(\n -> biggestDiv n . tail))
-- eliminate the first lambda with a p
biggestDiv =
((c p) head . if' . (==) 1) <*>
(p (<*>) (p (p if')
(\n -> ((==) 0) . mod n . head)
(\n -> c biggestDiv <*> (div n . head)))
(\n -> (.) (biggestDiv n) tail))
-- eliminate the second lambda with some flips
biggestDiv =
((c p) head . if' . (==) 1) <*>
(p (<*>) (p (p if')
(\n -> ((==) 0) . mod n . head)
(\n -> c biggestDiv <*> (div n . head)))
(\n -> (c (.)) tail (biggestDiv n)))
biggestDiv =
((c p) head . if' . (==) 1) <*>
(p (<*>) (p (p if')
(\n -> ((==) 0) . mod n . head)
(\n -> c biggestDiv <*> (div n . head)))
((c (.)) tail . biggestDiv))
-- we have created another 2 lambdas so its time for more elimination!
biggestDiv =
((c p) head . if' . (==) 1) <*>
(p (<*>) (p (p if')
(\n -> (c (.)) head (((==) 0) . mod n))
(\n -> c biggestDiv <*> (div n . head)))
((c (.)) tail . biggestDiv))
biggestDiv =
((c p) head . if' . (==) 1) <*>
(p (<*>) (p (p if')
((c (.)) head . (((==) 0 .) . mod))
(\n -> c biggestDiv <*> (div n . head)))
((c (.)) tail . biggestDiv))
biggestDiv =
((c p) head . if' . (==) 1) <*>
(p (<*>) (p (p if')
(((==) 0 .) . (c (.)) head . mod)
(\n -> c biggestDiv <*> (div n . head)))
((c (.)) tail . biggestDiv))
biggestDiv =
((c p) head . if' . (==) 1) <*>
(p (<*>) (p (p if')
(((==) 0 .) . (c (.)) head . mod)
(\n -> c biggestDiv <*> ((c (.)) head (div n))))
((c (.)) tail . biggestDiv))
biggestDiv =
((c p) head . if' . (==) 1) <*>
(p (<*>) (p (p if')
(((==) 0 .) . (c (.)) head . mod)
((c biggestDiv <*>) . ((c (.)) head . div )))
((c (.)) tail . biggestDiv))
Теперь мы полностью свободны от точек! Нигде нет именованных параметров! Однако обратите внимание, что у нас есть много (c (.)) (обратных композиций). В попытке сделать это более «хаскеллийским», я определил инфиксный оператор обратной композиции.
(^.) :: (a->b) -> (b->c) -> (a->c) f ^. g = c (.) f g
Используя ^., мы можем сократить определение еще больше до
biggestDiv =
((c p) head . if' . (==) 1) <*>
(p (<*>) (p (p if')
(((==) 0 .) . (head ^.) . mod)
((c biggestDiv <*>) . ((head ^.) . div )))
((tail ^.) . biggestDiv))
Добавьте несколько завершающих штрихов, чтобы убрать парочку скобок…
biggestDiv =
(<*>) ((c p) head . if' . (==) 1) $
p (<*>) (p (p if')
(((==) 0 .) . (head ^.) . mod)
((c biggestDiv <*>) . ((head ^.) . div ))) $
(tail ^.) . biggestDiv
И теперь мы наконец-то можем отдохнуть. Очевидно, что это определение совершенно громоздкое и его невозможно изменить и отладить, но оно предлагает забавное упражнение и доказательство концепции. Когда вы можете манипулировать аргументами своих функций с помощью комбинаторов, явные аргументы — это просто синтаксис. Я нахожу тот факт, что любую функцию можно сделать неявной в (довольно) простом виде, очень красиво, но это может привести к ужасному коду. Отсюда мое описание этой формы bigDiv как «безобразно красивое».
Примечание. Когда я действительно решал проблему, я придумал эту форму:
biggestDiv = p (<*>) ((head ^.) . if' . (==) 1) $
p (<*>)
(p (p if')
(((==) 0 .) . (head ^.) . mod)
((c biggestDiv <*>) . (head ^.) . div )) $
(tail ^.) . biggestDiv
Это почти то же самое, что я придумал в этой статье (моя вторая попытка), но первая строка немного отличается. Определения эквивалентны, так как они дают одинаковые ответы, но может быть забавным упражнением попытаться преобразовать две формы, чтобы формально доказать эквивалентность. Я еще этого не делал, поэтому оставлю это в качестве упражнения для читателя. Я не помню, как я получил другую скидку в первый раз.
Если вы не работаете с таким языком, как APL, полное молчаливое программирование почти никогда не будет правильным решением. Однако во многих случаях написание без точек или даже просто удаление нескольких точек может создать более чистый и понятный код. Я считаю, что неявные функции особенно хорошо подходят для использования в качестве аргументов для функций отображения и редукции.
Об авторе
Эрик Брейер — студент факультета компьютерных наук Университета Райса. Найти его можно на его сайте, а также на GitHub и LinkedIn.
