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

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

Но в любом случае давайте представим искусство ASCII. Циклический список:

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

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

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

Суть циклического списка в том, что от каждой cons-ячейки в списке есть путь ко всем остальным и самой. Это означает, что с точки зрения сборщика мусора, если одна из 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, используется и как результат, и как аргумент приложения f. То есть преобразователь при принудительном вызове вызовет объектный код для f с самим преобразователем в качестве аргумента и заменит содержимое преобразователя результатом.

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

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

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

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

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

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

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

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

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

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

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