Понимание совместного использования структуры в Haskell

Ответ 1

Чтобы понять это, нам нужно определение map

map _ []     = []
map f (x:xs) = f x : map f xs

Мы вычислим successors 0, делая вид, что позвоночник результирующего списка принудительно вычисляется. Мы начнем с привязки n к 0.

successors 0 = let ns = 0 : map (+1) ns 
               in ns

Везде, где мы находимся в результате вычисления - в (нестрочном) поле конструктора или привязки let или where, мы фактически храним thunk, который примет значение результат вычисления при оценке thunk. Мы можем представить этот заполнитель в коде, введя новое имя переменной. Для конечного результата map (+1) ns, помещенного в хвост конструктора :, мы представим новую переменную с именем ns0.

successors 0 = let ns = 0 : ns0 where ns0 = map (+1) ns 
               in ns

Первое расширение

Теперь давайте разворачиваем

map (+1) ns

Использование определения map. Мы знаем из привязки let, что мы просто написали, что:

ns = 0 : ns0 where ns0 = map (+1) ns

Поэтому

map (+1) (0 : ns0) = 0 + 1 : map (+1) ns0

Когда второй элемент принудительно, мы имеем:

successors 0 = let ns = 0 : ns0 where ns0 = 0 + 1 : map (+1) ns0
               in ns

Нам больше не нужна переменная ns, поэтому мы удалим ее, чтобы очистить ее.

successors 0 = 0 : ns0 where ns0 = 0 + 1 : map (+1) ns0

Мы вводим новые имена переменных n1 и ns1 для вычислений 0 + 1 и map (+1) ns0, аргументы в самый правый конструктор :.

successors 0 = 0 : ns0
                   where
                       ns0 = n1    : ns1
                       n1  = 0 + 1
                       ns1 =         map (+1) ns0

Второе расширение

Разложим map (+1) ns0.

map (+1) (n1 : ns1) = n1 + 1 : map (+1) ns1

После того, как третий элемент в списке позвоночника (но еще не его значение) принудительно, мы имеем:

successors 0 = 0 : ns0
                   where
                       ns0 = n1    : ns1
                       n1  = 0 + 1
                       ns1 =         n1 + 1 : map (+1) ns1

Нам больше не нужна переменная ns0, поэтому мы удалим ее, чтобы очистить ее.

successors 0 = 0 : n1 : ns1
                   where
                       n1  = 0 + 1
                       ns1 = n1 + 1 : map (+1) ns1

Мы будем вводить новые имена переменных n2 и ns2 для вычислений n1 + 1 и map (+1) ns1, аргументы в самый правый конструктор :.

successors 0 = 0 : n1 : ns1
                   where
                       n1  = 0 + 1
                       ns1 = n2     : ns2
                       n2  = n1 + 1
                       ns2 =          map (+1) ns1

Третье расширение

Если мы снова повторим шаги из предыдущего раздела, мы имеем

successors 0 = 0 : n1 : n2 : ns2
                   where
                       n1  = 0 + 1
                       n2  = n1 + 1
                       ns2 = n3     : ns3
                       n3  = n2 + 1
                       ns3 =          map (+1) ns2

Это явно растет линейно в позвоночнике списка и линейно в thunks для вычисления значений, содержащихся в списке. Как описывает dfeuer, мы имеем дело только с "маленьким круговым битом" в конце списка.

Если мы вынуждаем какое-либо из значений, содержащихся в списке, все остальные трюки, которые ссылаются на него, теперь будут ссылаться на уже вычисленное значение. Например, если мы нажмем n2 = n1 + 1, это заставит n1 = 0 + 1 = 1 и n2 = 1 + 1 = 2. Список будет выглядеть как

successors 0 = 0 : n1 : n2 : ns2
                   where
                       n1  = 1           -- just forced
                       n2  = 2           -- just forced
                       ns2 = n3     : ns3
                       n3  = n2 + 1
                       ns3 =          map (+1) ns2

И мы сделали только два дополнения. Добавления для подсчета до 2 никогда больше не будут выполняться, потому что результат вычисления является общим. Мы можем (бесплатно) заменить все n1 и n2 на только что вычисленные значения и забыть об этих именах переменных.

successors 0 = 0 : 1 : 2 : ns2
                   where
                       ns2 = n3   : ns3
                       n3  = 2 + 1       -- n3 will reuse n2
                       ns3 =        map (+1) ns2

Когда n3 будет принудительно, он будет использовать результат n2, который уже известен (2), и эти первые два добавления больше никогда не будут выполнены.

Ответ 2

Вкратце: вам разрешено притворяться в определении ns, что ns полностью оценивается. Так что мы фактически получаем, по существу,

successors n = let ns = n : map (+1) [n,n+1,n+2,n+3,n+4,...]

Вам нужно только подсчитать стоимость этого map.

Подумайте об этом оперативно.

ns = n : map (+1) ns

Что это делает? Ну, он выделяет бит памяти для хранения ns и сохраняет в нем конструктор (:), который указывает на значение n и на "thunk", представляющий map (+1) ns. Но этот thunk представляет ns как указатель на тот же самый бит памяти ns! Таким образом, у нас фактически есть круговая структура в памяти. Когда мы запрашиваем второй элемент ns, этот удар принудительно. Это включает в себя доступ к ns, но доступная часть уже рассчитана. Его больше не нужно рассчитывать. Эффект этого форсирования заключается в замене map (+1) ns на n+1:map (+1) ns', где ns' является указателем на (теперь известный) второй элемент ns. Итак, по мере того как мы продолжаем, мы создаем список, последний фрагмент которого всегда немного кругового бита.