Неудачная попытка определить бесконечный поток

Question

Я работаю над UPENN Haskell Homework 6 Exercise 5, пытаясь определим ruler function

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

где п-й элемент в потоке (при условии, первый элемент соответствует n = 1) является наибольшее power of 2, которое равномерно делит n.

Я только что пришел с идеей построить его без каких-либо испытаний делимости:

data Stream x = Cons x (Stream x) deriving (Eq) 

streamRepeat x = Cons x (streamRepeat x) 

interleaveStreams (Cons x xs) (Cons y ys) = 
    Cons x (Cons y (interleaveStreams xs ys)) 

ruler = 
    interleaveStreams (streamRepeat 0) 
     (interleaveStreams (streamRepeat 1) 
      (interleaveStreams (streamRepeat 2) 
       (interleaveStreams (streamRepeat 3) (...)) 

где первые 20 элементов

ruler = 
    interleaveStreams (streamRepeat 0) 
     (interleaveStreams (streamRepeat 1) 
      (interleaveStreams (streamRepeat 2) 
       (interleaveStreams (streamRepeat 3) (streamRepeat 4)))) 

является

[0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2]

Очевидно, что я не мог определить его вручную до бесконечности, поэтому я определил infInterStream, чтобы помочь такое бесконечное определению рекурсии:

infInterStream n = interleaveStreams (streamRepeat n) (infInterStream (n+1)) 

ruler = infInterStream 0 

Но теперь я застреваю при вводе в ruler в ghci, он, вероятно, попадет в бесконечный цикл.

Это не должно быть, если работает ленивая оценка. Я хочу знать, почему здесь ленивая оценка.

---

Вспомогательная функция для наблюдения Stream:

streamToList (Cons x xs) = x : streamToList xs 

instance Show a => Show (Stream a) where 
    show = show . take 20 . streamToList 

Answer 1

Ваша функция перемежения слишком строги. Следующие работы:

interleaveStreams (Cons x xs) ys = Cons x (interleaveStreams ys xs) 

Это также работает:

interleaveStreams (Cons x xs) ~(Cons y ys) = 
    Cons x (Cons y (interleaveStreams xs ys)) 

Первоначальное определение переходит в бесконечный цикл, поскольку interleaveStreams требует, чтобы оба аргумента должны быть Cons форм. infInterStream n оценивает чередование двух потоков, а первый может быть немедленно оценен до Cons, но второй должен также быть снижен сначала до Cons, поэтому мы рекурсивно вызываем infInterStream (n + 1), который продолжает называть себя бесконечно.

Если interleaveStreams может вернуть Cons a _ без предварительного принуждения второго аргумента, infInterStream также может поэтапно строить результат.

Answer 2

Нет необходимости в новом типе для потоков, и мы можем просто использовать ленивые списки Haskell. Как отмечали другие, определение чередования должно быть достаточно ленивым, чтобы он мог создать первый элемент вывода перед тестированием того, является ли второй аргумент непустым.Это определение будет делать:

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

Если вы хотите interleave работать также для конечных списков, вы можете добавить уравнение

interleave [] ys = ys 

Следует также отметить, что, используя функции из стандартной прелюдии,

ruler = interleave (repeat 0) (map (+1) ruler) 

Здесь repeat 0 Список [0, 0, 0, ...].