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

Question

Я определил бесконечный список бесконечных списков 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', поскольку я только частично оценил это. Почему это не работает?

Answer 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) это правильное с точки зрения обозначения уравнение, в реализации Haskell в GHC это уравнение не является функционально надежным - и :p все об операционной семантике и трепетно ​​относится к денотационной семантике. Особенно, map не (не может) наблюдать за тем, как в repeat x; следовательно это производит нециклический бесконечный список. поскольку map f (repeat x) имеет меньше обмена, заставляя часть map f (repeat x) не приводит к представлению в памяти, которое оценивается как полностью.