Статья о ленивых вычислениях и бесконечных списках в стиле "tying the knot".

[dastapov]

Я сподобился написать еще одну статью о ФП на русском. На этот раз - о бесконечных списках и ленивых вычислениях (в стиле "Tying The Knot", если кто в курсе). Буду рад, если вы прочтете и покритикуете.

Comments

[singalen]

1. Чистить от лишних слов. Для этого - читать Нору Галь, "Слово живое и мёртвое". У вас лишних слов немного, но есть. Упрощать язык.
"Описание ... выглядит так:" -> "правила игры", или вообще ничего.
2. Это не разные описания, это разные формы одной игры.
3. Позиции, наверное, не оптимальные, а выигрышные.
4. Название строки "Номер позиции (n)" лишнее, оставить только "№".
5. К самым интересным (и самым сложным) хаскельным строкам я бы всё-таки приложил "русский подстрочник" вроде:

column = zipWith    (+)  [1..]                    row
column = это список сумм ряда натуральных чисел и ряда row

[http://users.livejournal.com/_adept_/]

1. За ссылку на Галь - спасибо, почитаю. Есть у меня грешок такой, городить больше слов, чем реально нужно.

5. А там zipWith - это ссылка на страницу документации с примерами. В том числе там есть пример с (+). Ссылка не помогла или ее не видно?

[singalen]

Что делает zipWith, я знаю, так что в доку лезть не стал. Замечание в том, что проще прочесть одно предложение в основном тексте, чем ходить по ссылке. Тем более что в ссылке довольно много информации.
Да, немного не прав с комментарием, не "список", а "блок кода, вычисляющий список", или типа того.

[http://users.livejournal.com/_adept_/]

Поэлементная сумма? :)

[gabriel-irk.livejournal.com]

1. Можно ещё Юрия Никитина почитать: "Как стать писателем и заработать миллион".
Тоже есть электронный вариант в Сети.

[singalen]

Да, из схемы ничего не понял :) Может, её можно улучшить?

[http://users.livejournal.com/_adept_/]

Так-таки совсем ничего, или понятно хоть что-то, а с остальным - вопросы?

Я просто не совсем представляю себе, как можно иначе нарисовать producer-ов и consumer-ов потенциально бесконечных списков, тем более - взаиморекурсивных.

Как, например, нарисовать, что результатом "zipWith (+) row [1..]" будет thunk, который при вычислении выдаст список, голова которого - сумма первых эл-тов исходых списокв, а хвост - thunk, вычисляющий "zipWith (+)" от того, что осталось?

[gabriel-irk.livejournal.com]

А я в схеме и не разбирался - мне из кода понятно. Вообще предпочитаю разбираться сразу в коде, а не в схемах. :)

[singalen]

Угу. Нашему брату читать псевдокод гораздо легче, чем схемы.

[avalez.livejournal.com]

Я попытался представить схему по-своему и вот что у меня получилось: http://spreadsheets.google.com/pub?key=pHugjZLAJhuDLoQ2nScH9Vg
Конечно не хватает понятий thunk и из-за этого наверное не понятна магия с отниманием winning_positions, ведь он тоже бесконечный, но при этом оно работает :)

[http://users.livejournal.com/_adept_/]

О, классная идея. Только в первой колонке у тебя должно быть что-то вроде такого:

[1..] : (remove (1,2) [1..])
[1..]:[3..]:(remove (3,5) [3..])
[1..]:[3..]:[4,6..]:(remove (4,7) [4.6..])
[1..]:[3..]:[4,6..]:[6,8..]:(remove (6,10) [6,8..])

[avalez.livejournal.com]

Спасибо, исправил, не совсем так но все же - нюанс с первой итерацией - scanl не применяет функцию в первый раз, и это спасает ситуацию с "зацикливанием" рекурсии по-моему (я понял!? :)

Странно, что на zvon.org в определении сказано что scanl применяет второй аргумент к первому элементу списка и так далее, но это на самом деле так только со второй итерации, и даже у них в примере это видно, или я не понял? :)

[http://users.livejournal.com/_adept_/]

Да, ты абсолютно правильно понял. Исходный текст scanl выглядит так:

scanl f q ls = q : case ls of
[] -> []
x:xs -> scanl f (f q x) xs


На zvon.org все правильно сказано про применение, но не сказано про порядок выдачи результатов :)

[fonmax.livejournal.com]

эм-мм.. "Mutual friends: 666" -- с чем оффтопово поздравляю. (:

[http://users.livejournal.com/_adept_/]

Капец. За мной следят :)