Funky haskell ленивый список неявной рекурсии

Ответ 1

В этом случае изображение может указывать тысячу слов.

Во-первых, помните, как работает cons (конструктор списка (:)). Это пара двух вещей: элемент и ссылка на хвост списка (который является либо другим минусом, либо []).

Как вы знаете, когда вы говорите [1, 2, 3], это просто ярлык для (1:(2:(3:[]))) или 1:2:3:[]. Если вы визуализируете каждую пару cons как поле с двумя слотами, это выражение выглядит так:

┌───┬──┐  ┌───┬──┐  ┌───┬──┐  ┌────┐
│ 1 │ ─┼─>│ 2 │ ─┼─>│ 3 │ ─┼─>│ [] │
└───┴──┘  └───┴──┘  └───┴──┘  └────┘

Один цикл

Когда вы говорите g = 4 : g, вы на самом деле не создаете "бесконечный" список, вы строите круговой список: g определяется как минус, чья ссылка на хвост просто указывает на g:

┌──────────┐
│ ┌───┬──┐ │
└>│ 4 │ ─┼─┘
  └───┴──┘

На самом деле это не имеет ничего общего с ленинностью и всем с самооценкой: например, вы можете сделать то же самое в (нетерпеливом) Common Lisp с помощью синтаксиса типа '#1=(4 . #1#) (где #1 g).

Говорите ли вы, что g !! 0 или g !! 1000000000000, g никогда не растет: (!!) просто пробегает цикл на месте, столько раз, сколько вы ему сказали, пока он не исчерпает себя и не вернет элемент, 4.

Две петли

Когда вы говорите f = (f !! 10) : f, происходит то же самое - кроме этого, слот элемента содержит другое выражение, чем 4:

┌──────────┐
│ ┌───┬──┐ │
└>│ ╷ │ ─┼─┘
  └─┼─┴──┘
    │
    │ ┌───────────┐
    └>│ (f !! 10) │
      └───────────┘

Реально, это подвыражение также относится к f, как и хвост:

 ┌──────────┐
 │ ┌───┬──┐ │
┌┴>│ ╷ │ ─┼─┘
│  └─┼─┴──┘
│    │
│    │ ┌───────────┐
│    └>│ (f !! 10) │
│      └──┼────────┘
└─────────┘

Итак, когда вы запрашиваете f !! n, (!!) сначала запускается вокруг верхнего цикла n раз, а затем возвращает элемент, как и для g. Однако вместо того, чтобы сбежать из цикла, (f !! 10) просто повторно вводит его, и процесс повторяется: цикл повторяется 10 раз сверху, затем один раз по дну и обратно.

Ответ 2

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

Более конкретно, этот код в порядке:

Prelude> let x = [(x !! 1) + 1, 3] in x
[4,3]

Вы можете ожидать, что x !! 1 еще не существует. Но вот как работает реализация, такая как GHC.

При создании списка f он создает объект in-memory ( "thunk" ) для представления выражения (x !! 1) + 1. Пока нет оценки x. Он переносит указатель на этот кусок, плюс указатель на 3, в связанный список и передает его в GHCi неявный show.

Теперь экземпляр show для списков должен показывать элементы один за другим. show будет требовать ( "force" ) оценку thunk для (x !! 1) + 1, что заставляет этот код "вводиться". По определению (+), заставляя (x !! 1) + 1 силы x !! 1, что, в свою очередь, заставляет две вещи:

• позвоночник списка (его ячейки cons) через вторую ячейку и
• значение второго элемента ( "автомобиль" второй ячейки, в терминах Lisp), потому что (+) хочет работать с этим значением.

И второе значение уже присутствует - it 3. Если бы это был еще один удар, мы бы это заставили и так далее. См. этот пост в блоге для интересного просмотра самореферентных контейнеров.

Теперь, как скомпилированный код GHC обнаруживает бесконечный цикл в вашем другом примере? Когда мы входим в thunk, мы должны помнить, чтобы вернуться позже и перезаписать его с окончательным значением. Это то, что конкретно означает "ленивая оценка", а не "нестрогая семантика", и это мешает нам дублировать работу.

В любом случае, как оптимизация при входе в thunk, среда выполнения GHC сначала перезапишет ее другим объектом, называемым "черной дырой". Мы вернемся позже и перепишем черную дыру окончательным значением. Но что произойдет, если мы войдем в черную дыру, прежде чем это сделать? Это означает, что оценка x требует сначала оценки x, неразрешимого цикла. Поэтому вход в черную дыру вызывает исключение.

Ответ 3

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

Что касается того, почему он не создает исключения, попробуйте выполнить его компиляцию вместо запуска в GHCi:

$ ghc --make Loop.hs
$ ./Loop.exe
Loop.exe: <<loop>>

Я предполагаю, что это NonTermination exception. Pff, проблема с остановкой? Ха.

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