Недавно я столкнулся с проблемой программирования, в которой меня попросили написать код, который определит количество документов формата A0, которые вы можете сделать, на основе заданного количества документов формата A0, A1, A2 и т. Д., Которые у вас уже есть. Идея, на которой основана задача, проста: две статьи A(n + 1)
могут быть объединены в одну бумагу A(n)
.
Это довольно тривиально. Если вам дан список, который идет [1, 1, 2]
, это означает, что у вас есть 1 лист формата А0, 1 лист А1 и 2 листа А2.
Если вы возьмете две бумаги формата А2, вы можете объединить их в одну бумагу формата А1. Это означает, что теперь у вас есть две статьи формата A1, которые, как вы уже догадались, можно объединить в бумагу формата A0. Итак, у вас уже была одна бумага формата A0, так что теперь у вас их две.
Предполагая, что вы еще не поняли это, вы можете просто решить эту проблему программно:
- начиная справа (или наименьшего размера),
- деление числа вдвое целочисленным делением (или объединение каждой пары в одну),
- добавив его к числу слева (или классифицируя вашу пару листов Франкенштейна меньшего размера как большую),
- повторяйте, пока у вас не останется только один номер
Если вы все сделали правильно, то теперь у вас должно быть столько A0
документов, которое вы могли бы сделать из документов, которые у вас были ранее.
Это походило на концепцию, о которой я узнал, когда выучил язык Haskell по прихоти. Вот как я это реализовал:
mergePapers a = foldr (\cur acc -> (acc `div` 2) + cur) 0 a
Я признаю, что это, вероятно, читается как греческий для любого, кто не использовал Haskell, даже для тех, кто программировал на каком-либо другом языке в какой-либо степени. Но, чтобы дать этим людям ориентир, вот как я сделал это на Java:
public int mergePapers(int[] a) { int acc = 0;
for (int cur = a.length - 1; cur >= 0; cur--) { acc = acc / 2 + a[cur]; }
return acc; }
Я обещаю, что код Haskell не особо запутан, он достаточно близок к идиоматическому коду. Функционально он также выполняет те же функции, что и код Java, и шаги, которые я описал ранее.
Я не могу научить вас Haskell, но я могу попробовать переписать код в стиле, похожем на тот, с которым знакомо большинство программистов, что, конечно же, является синтаксисом в стиле C.
mergePapers(a) = foldr(
((cur, acc) -> div(acc, 2) + cur),
0,
a
)
Единственное, что я изменил, это то, как обозначаются функции. В Haskell и определение, и вызов функции выглядят как func arg1 arg2
, тогда как в большинстве других языков это будет выглядеть как func(arg1, arg2)
. Еще я изменил то, как выглядела лямбда (или анонимная функция), которая, конечно, сильно варьируется от языка к языку, но я просто использовал (arg1, arg2) -> arg1 + arg2
, который представляет собой просто функцию, которая принимает два аргумента и возвращает их сумму.
Еще одна тривиальная вещь, от которой стоит отказаться - это функция div
, которая представляет собой просто функцию целочисленного деления.
Теперь перейдем к сути кода, функции foldr
. Его цель - «свернуть функцию по списку справа с начальным аккумулятором». Если вы поймете, что это значит, вы поймете, что в основном он выполняет за меня всю мою работу. Если нет, то лучший способ объяснить это - сравнить его с кодом Java.
Как я сказал ранее, обе части кода функционально выполняют одно и то же:
- с начальным аккумулятором
Начнем с самого очевидного. В Java я использовал аккумулятор, определив int acc = 0
. В Haskell это просто второй аргумент, 0
я предоставил функцию foldr
.
- над списком справа
Для этого в Java я создал цикл for
, который начинается в конце массива a
и заканчивается в начале for (int cur = a.length - 1; cur >= 0; cur--)
. В Haskell это делается путем предоставления списка в качестве третьего аргумента функции foldr
в отличие от, как вы уже догадались, функции foldl
.
- свернуть функцию
Чтобы связать все это, в Java я добавляю к аккумулятору с течением времени, сколько бумажных пар я объединяю, используя acc = acc / 2 + a[cur]
. В Haskell это делается путем предоставления функции (cur, acc) -> div(acc, 2) + cur
в качестве первого аргумента, которая выполняет то же самое, что и фрагмент кода Java, только вместо этого в качестве функции.
Теперь вы можете сказать, что я написал все это, чтобы сказать, что в Haskell есть удобная функция, которой нет в Java. Вы были бы правы… до некоторой степени. Но что меня больше всего поразило при написании этого кода, так это то, насколько естественно он транслировался из моего мыслительного процесса и насколько я был удовлетворен после написания этого тривиального фрагмента кода. Когда я решил проблему, я обнаружил, что думаю на Haskell, как если бы это был другой разговорный язык.
Это не значит, что люди не могут испытать это на других языках. Сказать ли это о Java? Наверное. (У меня определенно нет страстной ненависти к Java.) Например, Python - это язык, который я бы назвал наиболее близким к разговорной речи с множеством синтаксических конструкций, похожих на повседневный английский.
Однако в Haskell это точно не известно. Это функциональный язык, поэтому он выглядит скорее математическим по своей природе. Написание кода на Haskell похоже на составление правильных функций в правильном порядке для получения желаемого результата. Но в тот момент, решая эту простую задачу, я обнаружил, что Haskell почти идеально отражает мои мысли.