разговоры о хаскеле

[thedeemon]

Есть такой подкаст о распределенных базах данных DevZen, почему-то выдающий себя за подкаст о программировании. Но недавно они сделали исключение, выгнали женщин и детей, пригласили двух замечательных гостей - Романа Чепляку, которого мы все любим за его Cartesian Closed Comics, и Дениса Шевченко, автора книжки "О Haskell по-человечески" - и получился довольно хороший и познавательный выпуск, рекомендую.

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

Comments

[juan-gandhi.livejournal.com]

Пытаюсь переварить про среднее арифметическое.
Неужели такая нехватка общего образования... аяяй.
В Питере бы сразу сказали: "посчитаем моменты".

[thedeemon.livejournal.com]

Тут чисто хаскелевая специфика, на ML или Скале или даже С++ это было бы просто. Но перенос такого решения в лоб на хаскель приводит к порождению цепочки недовычисленных санков. Ибо ленивость. А это не O(1).

[kodt-rsdn.livejournal.com]

Присоединяюсь к Ивану Ганди.
Казалось бы, foldl' во всех уччебниках для детей есть.
Или хаскеллисты стали умствовать про то, что арифметика нужна длинная, а это уже сразу O(n)... даже без лени и Шлемюэля?

Хотя да, нужно делать энергичный кортеж (количество,сумма), иначе фолдл его только до конструктора форсирует, а внутри будут санки.

[dmzlj.livejournal.com]

Отличный наброс, типа "хаскеллисты все тупые".

Неужели прям ни одного не нашлось, кто бы написал
явную рекурсию со строгим аккумулятором, т.е аналог
явного цикла, как Си?

[thedeemon.livejournal.com]

"практически никто" - значит кто-то грамотный все же был

[nponeccop.livejournal.com]

так foldl' полностью эквивалентен явной хвостовой рекурсии. Собственно, фишка в том, как сделать составной аккумулятор строгим.

[gineer.livejournal.com]

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

А что же тут удивительного?
Чай не императивщики. :) разглядывать ассемблерный код своего поделия не будут.

[dmzlj.livejournal.com]

Ну на это можно ответить собственными историями про собеседование эмбедщиков, которые постоянно рассматривают свой код на ассемблере. Или джавистов.

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

[dmytrish.livejournal.com]

Интересно, конечно. Я интервьюировался когда-то давно не у Романа, но в той же конторе, завалился на fold’ах и их ленивом поведении — в принципе, вполне заслужено, базовая вещь. Но поверить в то, что люди не могут взять среднее арифметическое за один проход — это уже как-то за гранью. Видимо, мое углубление в реализации функциональных языков с тех пор не прошло даром.

[thedeemon.livejournal.com]

Так среднее арифметическое и было лишь предлогом, сама задача именно про ленивость и фолды.

[dev117.livejournal.com]

А как найти среднее арифметическое за один проход?

[nponeccop.livejournal.com]

за гранью, блин. Одновременно считать сумму и длину, а потом поделить

[alexander tarasikov (from livejournal.com)]

Я написал на бумажке:
A1 = X1 / 1
A2 = (X1 + X2) / 2
A3 = (X1 + X2 + X3) / 3
AN = (A(N-1) * (N-1) + XN) / N

Потом написал такой код https://gist.github.com/astarasikov/c4506f456dd69e6a844e
потом вспомнил про kahan summation, посмотрел на время, и решил, что хватит зависать в социальных сетях на сегодня

Жопоболь

[livejournal.livejournal.com]

Пользователь nponeccop сослался на вашу запись в своей записи «Жопоболь (http://nponeccop.livejournal.com/449682.html)» в контексте: [...] http://thedeemon.livejournal.com/101735.html [...]

[sassa-nf.livejournal.com]

"надо найти их среднее арифметическое за один проход"

на бумажке?

[lispnik.livejournal.com]

Если за один проход и на бумажке — это эйлеровы графы, дааа? :)

[thedeemon.livejournal.com]

Ага.
http://dmytrish.livejournal.com/46655.html

[gliv.livejournal.com]

Я уже рассказывал где-то, что ребята у меня в конторе выработали следующие вопросы для первого интервью:
- сколько бит в байте
- сколько разных значений можно закодировать 6-ью битами

И это правило реально работает! Я не думал, что помогает, но реально находятся люди, которые этого не знают.

Не уверен, что для всех оно применимо, может на каком-нибудь "1С" или Visual Basic можно программировать не зная этого. Но мне даже странно слышать такое!

[gds.livejournal.com]

> сколько бит в байте

Возможно вы имели в виду: в октете

[juan-gandhi.livejournal.com]

Помню в одну контору интервьюировался, и меня подобные вопросы очень удивили.

[levgem.livejournal.com]

ну а в чём цимес первого вопроса кроме того, что человек может блеснуть своей эрудицией и рассказать про 7 или 9 битные компьютеры древности?

[udpn.livejournal.com]

А какой адрес у вашей конторы? :)

[levgem.livejournal.com]

avg([]) -> 0;
avg(List) -> avg(List, 0, 0).

avg([], Sum, Count) -> Sum / Count;
avg[N|List], Sum, Count) -> avg(List, Sum+N, Count+1).

так нельзя?

[thedeemon.livejournal.com]

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

[vshabanov.livejournal.com]

Вспоминается, как Зефиров давал C# программистам задачу найти разницу между максимальным и минимальным числом массива. И тоже очень многие лажали. А некоторые даже отказывались.
Я сам когда-то спрашивал банальное -- перевернуть список -- тоже не все могли.

Может это нервы, а может быть на каких-то работах можно даже без знания основ обойтись.

[rashid80.livejournal.com]

А в чем подвох задачи с массивом? Если массив небольшой можно встроенными средствами его отсортировать и  взять разность первого и последнего элемента. Для большого массива нужны 2 переменные (мин и макс) и итератором пройти массив.

Готов К Продакшну

[livejournal.livejournal.com]

Пользователь theiced сослался на вашу запись в своей записи «Готов К Продакшну (http://theiced.livejournal.com/328465.html)» в контексте: [...] http://thedeemon.livejournal.com/101735.html [...]