Почему: p замерзает в GHCi, когда я даю ему эту кореквизирующую ценность?

Я определил бесконечный список бесконечных списков pathCounts и бесконечный список конечных списков pathCounts':

import Data.Function (fix)

nextRow xs = fix $ \ys -> zipWith (+) xs (0:ys)

pathCounts = repeat 1 : map nextRow pathCounts
pathCounts' = map (take 100) pathCounts

Отбрасывание в ghci, если я вообще не оценил, я могу использовать :p либо успешно:

ghci> :p pathCounts
pathCounts = (_t1::[[Integer]])
ghci> :p pathCounts'
pathCounts' = (_t2::[[Integer]])

Но если я частично оцениваю pathCounts', то :p зависает на pathCounts, но все же преуспевает pathCounts':

ghci> head . head $ pathCounts'
1
ghci> :p pathCounts'
pathCounts' = (1 : (_t4::[Integer])) : (_t5::[[Integer]])
ghci> :p pathCounts
^CInterrupted.

Я бы ожидал, что :p pathCounts напечатает то же самое, что и :p pathCounts', поскольку я только частично его оценил. Почему он не работает?

Ответ 1

Я бы ожидал, что :p pathCounts напечатает то же самое, что и :p pathCounts', поскольку я только частично его оценил.

А, но это интересный бит! Фактически вы полностью оценили (бесконечно длинную) голову pathCounts. Давайте рассмотрим несколько меньший пример, чтобы упростить обсуждение:

> let v = repeat 1 :: [Int]
> head v
1
> :p v
^C

Я утверждаю, что после полной оценки head v, фактически v также полностью оценивается. Это связано с тем, что в памяти v является циклическим односвязным списком. Поэтому, если вы достаточно оценили, чтобы узнать первый элемент, оценить нечего!

В результате, когда вы запрашиваете :print, GHC должным образом пытается построить строку, представляющую всю оцениваемую часть структуры, и, очевидно, не может, поскольку она никогда не перестанет перемещаться. (:p просто не имеет способа указывать совместное использование в структуре.)

Для сравнения:

> let x = 1 :: Int; v = (x, x)
> fst v
1
> :p v
(1,1)

Хотя вы только запросили оценку первой части v, на самом деле все v были оценены здесь, поэтому :p распечатывает все это - и не указывает общий доступ, который существует между первая и вторая части.

Теперь, почему pathCounts' не имеет такой же проблемы? Ну, дело в том, что, хотя map f (repeat x) = repeat (f x) является денотационально правильным уравнением, в реализации GHC Haskell это уравнение не работает оперативно, а :p - это все о функциональной семантике и превью его носа на денотационная семантика. В частности, map не может (не может) наблюдать совместное использование в repeat x; следовательно, он создает нециклический бесконечный список. Поскольку map f (repeat x) имеет меньшее количество разделов, принудительная часть map f (repeat x) не приводит к представлению в памяти, которое полностью оценивается.