Почему использование head/tail вместо сопоставления с образцом завершает оценку?

Как упражнение, я пытаюсь определить значение ruler

ruler :: (Num a, Enum a) => [a]

который соответствует функции линейки

0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2...

где n '-й элемент списка (при условии, что первый элемент соответствует n=1), является наибольшей степенью 2, которая равномерно делит n. Чтобы сделать его более интересным, я пытаюсь реализовать ruler, не выполняя никаких тестов на делимость.

Используя вспомогательную функцию

interleave :: [a] -> [a] -> [a]

который просто чередует элементы из двух приведенных списков, я придумал это, но, увы, он не работает:

interleave :: [a] -> [a] -> [a]
interleave  (x:xs) (y:ys) = x : y : interleave xs ys
interleave  _      _      = []

ruler :: (Num a, Enum a) => [a]
ruler = foldr1 interleave . map repeat $ [0..]

main :: IO ()
main = print (take 20 ruler)

В конечном итоге программа использует все пространство стека.

Теперь, что странно, что программа работает нормально, если я настраиваю определение interleave так, чтобы он читал

interleave (x:xs) ys = x : head ys : interleave xs (tail ys)

т.е. Я больше не использую сопоставление шаблонов во втором аргументе. Почему использование head и tail здесь делает ruler terminate - в конце концов, сопоставление шаблонов является довольно защитным (я только оцениваю первый элемент списка позвонков, нет?).

Ответ 1

Вы применяете foldr со строгой функцией комбинации к бесконечному списку.

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

*Main> :t const
const :: a -> b -> a
*Main> :t flip seq
flip seq :: c -> a -> c
*Main> foldr1 const [0..]
0
*Main> foldr1 (flip seq) [0..]
^CInterrupted.

Исправление, как объяснено в других ответах, сделать interleave ленивым.

Более конкретно, вот что происходит. Сначала мы разрешаем foldr1, заменяя каждый : внешнего списка на interleave:

foldr1 interleave [[0..], [1...], ...]
= interleave [0...] (interleave [1...] (...))

Для достижения прогресса первый interleave хочет оценить второй аргумент перед созданием первого значения. Но тогда второй хочет оценить свой второй аргумент и т.д.

При ленивом определении interleave первое значение создается перед оценкой второго аргумента. В частности, interleave [1...] (...) будет оценивать до 1 : ... (что помогает первому interleave сделать прогресс), прежде чем оценивать материал дальше.

Ответ 2

Разница в том, что совпадение шаблонов заставляет первый элемент в позвоночнике head/tail не делать.

Вы можете использовать ленивые шаблоны для достижения одной и той же цели:

interleave  (x:xs) ~(y:ys) = x : y : interleave xs ys

Обратите внимание на ~: это эквивалентно определению y и ys с помощью head и tail.

Например: список ниже undefined.

fix (\ (x:xs) -> 1:x:xs)

где fix - комбинатор с фиксированной точкой (например, от Data.Function). Для сравнения, этот другой список повторяется 1 навсегда:

fix (\ ~(x:xs) -> 1:x:xs)

Это связано с тем, что 1 создается до того, как список разбит на x и xs.

Почему принудительное включение первого элемента в позвоночник вызывает проблему?

При рассуждении о рекурсивном уравнении, таком как

x = f x

часто помогает рассматривать x как значение, "приближенное" к последовательности значений

undefined
f undefined
f (f undefined)
f (f (f undefined))
...

(Указанная выше интуиция может быть уточнена с помощью некоторой денотационной семантики и теоремы о неподвижной точке Клине.)

Например, уравнение

x = 1 : x

определяет "предел" последовательности

undefined
1 : undefined
1 : 1 : undefined
...

который явно сходится к списку повторений.

При использовании сопоставления шаблонов для определения рекурсивных значений уравнение становится, например,

(y:ys) = 1:y:ys

который из-за соответствия шаблону переводится в

x = case x of (y:ys) -> 1:y:ys

Рассмотрим его аппроксимирующую последовательность

undefined
case undefined of (y:ys) -> ....   = undefined
case undefined of (y:ys) -> ....   = undefined
...

На втором этапе case расходится, делая результат еще undefined. Последовательность не подходит к списку "повторяющихся", но постоянно undefined.

Использование ленивых шаблонов вместо

x = case x of ~(y:ys) -> 1:y:ys

получаем последовательность

undefined
case undefined of ~(y:ys) -> 1:y:ys 
    = 1 : (case undefined of (y:_) -> y) : (case undefined of (_:ys) -> ys)
    = 1 : undefined : undefined      -- name this L1
case L1 of ~(y:ys) -> 1:y:ys
    = 1 : (case L1 of (y:_) -> y) : (case L1 of (_:ys) -> ys)
    = 1 : 1 : undefined : undefined  -- name this L2
case L2 of ~(y:ys) -> 1:y:ys
    = 1 : (case L2 of (y:_) -> y) : (case L2 of (_:ys) -> ys)
    = 1 : 1 : 1 : undefined : undefined

который сходится к намеченному списку. Обратите внимание на то, что ленивые шаблоны "продвигаются вперед" без предварительной оценки аргумента case. Это то, что делает их ленивыми. Таким образом, 1 создается до того, как выполняется сопоставление шаблонов, что делает результат рекурсивно определенного объекта нетривиальным.

Ответ 3

Проблема здесь не столько в сопоставлении шаблонов, либо с использованием head и tail. Проблема заключается в том, как это сделать, определяя вашу функцию как

interleave :: [a] -> [a] -> [a]
interleave  (x:xs) (y:ys) = x : y : interleave xs ys
interleave  _      _      = []

Вы строго придерживаетесь своих аргументов, то есть нам нужно знать, что они являются списками хотя бы одного элемента, прежде чем мы сможем выбрать первую ветвь. Поскольку вы свертываете эту функцию по бесконечному списку списков, мы не можем это понять, и у нас заканчивается пространство стека.

Чтобы развернуть это (чтобы прояснить ситуацию, возникшую в комментариях), в первый раз, когда мы пытаемся оценить interleave (в ruler), мы получим что-то вроде

interleave (repeat 0) (foldr1 interleave (map repeat [1..]))

Первый аргумент здесь, конечно, совпадает с шаблоном, но для выяснения, есть ли второй аргумент, мы должны попытаться его оценить, поэтому мы переходим к

interleave (repeat 1) (foldr1 interleave (map repeat [2..]))

Теперь мы не можем оценить это, если не знаем больше о втором аргументе. Поскольку список [2..] никогда не заканчивается, этот процесс может продолжаться вечно.

Одно из решений этого - сделать ленивую привязку шаблона к второму аргументу:

interleave  (x:xs) ~(y:ys) = x : y : interleave xs ys

Это действует как обещание, что второй аргумент соответствует шаблону, поэтому не беспокойтесь об этом (конечно, это не удастся, если это не так). Это означает, что эта первая оценка interleave может продолжаться, не углубляясь в повторную складку, которая в доминоподобном эффекте решает проблему.

Посторонним является то, что ваша версия interleave (а также ваша версия head/tail) будет работать только в списках, где второй список длиннее или длиннее первого.