В чем разница между циклическим списком и бесконечным списком в haskell?

Ссылка на @dfeuer ответ на этот вопрос: Самый дорогой способ создания циклического списка в Haskell, в котором говорится, что использование циклических списков "поражает" сборщик мусора, поскольку он имеет чтобы сохранить все, что вы потребляете, из циклического списка, выделенного до тех пор, пока вы не отбросите ссылку на любые ячейки cons в списке.

По-видимому, в Haskell циклический список и бесконечный список - это две отдельные вещи. Этот блог (https://unspecified.wordpress.com/2010/03/30/a-doubly-linked-list-in-haskell/) говорит, что если вы реализуете cycle следующим образом:

cycle xs = xs ++ cycle xs

это бесконечный список, а не циклический список. Чтобы сделать его циклическим, вы должны его реализовать таким образом (как в исходном коде Prelude):

cycle xs = xs' where xs' = xs ++ xs'

В чем же разница между этими двумя реализациями? И почему это так, что если вы держите на одной ячейке cons где-нибудь в циклическом списке, то сборщик мусора должен сохранить все до его выделения?

Ответ 1

Разница полностью в представлении памяти. С точки зрения семантики языка они неразличимы - вы не можете написать функцию, которая может отличить их друг от друга, поэтому ваши две версии cycle считаются двумя реализациями одной и той же функции (они точное сопоставление аргументов с результатами). На самом деле, я не знаю, гарантирует ли определение языка, что один из них является циклическим, а другой - бесконечным.

Но так или иначе, пусть выведет искусство ASCII. Циклический список:

   +----+----+                 +----+----+
   | x0 |   ----->   ...   --->| xn |    |
   +----+----+                 +----+-|--+
     ^                                |
     |                                |
     +--------------------------------+

Бесконечный список:

   +----+----+
   | x0 |   ----->  thunk that produces infinite list
   +----+----+

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

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

Отметим также, что это различие можно обобщить на два различных способа реализации функции fix:

fix, fix' :: (a -> a) -> a
fix  f = let result = f result in result
fix' f = f (fix' f)

-- Circular version of cycle:
cycle  xs = fix (xs++)

-- Infinite list version of cycle:
cycle' xs = fix' (xs++)

Библиотеки GHC подходят для моего определения fix. Способ компиляции кода GHC означает, что созданный для result thunk используется как результат, так и аргумент приложения f. I.e., thunk, когда принудительно, вызовет объектный код для f с самим файлом как его аргументом и заменит содержимое thunk результатом.

Ответ 2

Циклические списки и бесконечные списки различаются оперативно, но не семантически.

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

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

Причиной этого различия является то, что без оптимизаций типичная реализация Haskell, такая как GHC, будет выделять память один раз для значения, например xs' во втором определении cycle, но будет многократно выделять память для вызова функции, как cycle xs в первом определении.

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

Ответ 3

cycle xs = xs ++ cycle xs            -- 1
cycle xs = xs' where xs' = xs ++ xs' -- 2

В чем же разница между этими двумя реализациями?

Используя GHC, разница в том, что реализация # 2 создает самореферентное значение (xs'), а # 1 просто создает тон, который бывает одним и тем же.

И почему это так, что если вы держите ячейку cons cons где-то в циклическом списке, то сборщик мусора должен хранить все до его выделения?

Это снова конкретный GHC. Как сказал Луис, если у вас есть ссылка на одну ячейку cons в циклическом списке, вы можете добраться до всего списка, просто пройдя цикл. Сборщик мусора является консервативным и не собирает ничего, что вы все еще можете достичь.

Haskell чист, и где-рефакторинг звучит... только когда вы игнорируете использование памяти (и несколько других вещей, таких как использование ЦП и время вычисления). Язык Haskell не указывает, что должен делать компилятор, чтобы отличать # 1 и # 2. GHC реализация следует определенным шаблонам управления памятью, которые разумны, но не сразу очевидны.