Недавно я столкнулся с проблемой программирования, в которой меня попросили написать код, который определит количество документов формата 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 почти идеально отражает мои мысли.