Ответ 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), и эти первые два добавления больше никогда не будут выполнены.