Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Жопоболь

http://thedeemon.livejournal.com/101735.html

Роман рассказал, что в свое время интервьюировал не меньше двух десятков хаскеллистов в Киеве, и практически никто не смог во время интервью решить такую задачку: есть длинный список чисел, надо найти их среднее арифметическое за один проход по списку и О(1) памяти.
Cходу я тоже не смог, при требовании сделать на бумажке в интервью отказался бы.

С компом и инетом методом направленного тыка за 30 минут частично справился - тестовая программа стала выдавать результат и потреблять 0 памяти, но при этом 900 метров собралось коллектором.

В случае хаскеля надо дополнительно оговаривать, в каком виде существует список - то ли он уже есть, то ли имеется ввиду, что список не нужен, а нужна композиция развёртки и свёртки - т.е. есть хороший производитель, к которому надо написать хорошего потребителя.

В последнем случае должна быть возможность избавиться от 100500 аллокаций и сделать тайтлуп, но мне понадобится наверное ещё полчаса, если не больше.

На интервью я бы смог расписать последовательность редукций, обнаружить проблему и предложить методы решения, но времени бы на это ушло немеряно. Знания есть, но повода применить их за 10 лет нашлось - для больших объёмов данных использовал кондуиты, которые избавляют от необходимости думать.

В целом хаскель очень прощающий язык - можно писать на нём, как на строгом, и довольно долго не впадать во фрустрацию. Поводов впасть может быть два: либо отладочная трассировка покажет невозможный контрол флоу (но у меня с этим проблем уже нет), либо начнётся поиск утечек санков (проблемы до сих пор есть).

Проблема тут не столько в языке, сколько в отсутствии неигрушечной практики. А знания о подсчёте среднего за O(1) на других языках - просто бесполезные. Научиться ставить бенг паттерны, тем более в таком простом коде, вполне реально, был бы повод.
Tags: fp, programming
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 61 comments