Haskell не ленивый, оценивая чередование

Question

Я работаю над проблемой (ее из класса UPenn, но я не принимаю ее (просто работаю над ней, чтобы узнать Haskell)), и дело в том, чтобы построить Stream (как определено ниже), который определяется «правителем» (линейка !! n = показатель наивысшей степени 2, который будет делить n). Проблема в том, что я считаю, что определение правителя ниже должно лениво оценивать, но, судя по всему, оно оценивается строго и бесконечно. Если я закрываю его, добавляя терминал, например «nthStream 10 = streamRepeat 10», он запускается и генерирует вывод до той точки, которую я хочу правильно.

data Stream a = Stream a (Stream a) 

streamToList :: Stream a -> [a] 
streamToList (Stream a rest) = [a] ++ streamToList rest 

instance Show a => Show (Stream a) where 
    show s = show $ take 100 $ streamToList s 

streamRepeat :: a -> Stream a 
streamRepeat a = Stream a (streamRepeat a) 

interleaveStreams :: Stream a -> Stream a -> Stream a 
interleaveStreams (Stream a arest) (Stream b brest) = (Stream a (Stream b (interleaveStreams arest brest))) 

nthStream :: Integer -> Stream Integer 

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

ruler :: Stream Integer 
ruler = nthStream 0 

Может ли кто-нибудь объяснить, почему линейка (и nthStream) не лениво оценивает?

Answer 1

Я попытаюсь подтолкнуть вас в правильном направлении или, по крайней мере, указать, что происходит не так. Функция nthStream никогда не будет оценивать, даже не свой первый элемент, из-за того, как она определена с помощью interleaveStreams. Чтобы дать вам пример, давайте работать, что он имеет значение для nthStream 0 (для краткости и читаемости я переименованной nthStream к nth, interleaveStream на interleave, streamRepeat к repeat и Stream к Strm):

nth 0 = interleave (repeat 0) (nth 1) 
     = interleave (Strm 0 _0) (interleave (repeat 1) (nth 2)) 
     = interleave (Strm 0 _0) (interleave (Strm 1 _1) (nth 2)) 
     = interleave (Strm 0 _0) (interleave (Strm 1 _1) (interleave (repeat 2) (nth 3))) 
     = interleave (Strm 0 _0) (interleave (Strm 1 _1) (interleave (Strm 2 _2) (nth 3))) 

I выбранный для представления хвостов каждого потока, возвращаемого с repeat, как _N, где N - это число, которое повторяется. В настоящее время они являются громкими, поскольку нам еще не приходилось запрашивать их ценности. Обратите внимание, что то, что строится, это цепочка interleave s, а не цепочка из Strm конструкторов. Мы получаем каждый, который нас интересует, но они никогда не смогут вернуться с interleave до тех пор, пока не будет оценен второй аргумент. Поскольку второй аргумент всегда сводится к новому вызову interleave, он никогда не уменьшит его.

Подсказка: как вы можете определить interleaveStreams рекурсивно, чтобы он зависел только от того, что его первый аргумент был построен уже? т.е.

interleaveStreams (Stream a arest) streamB = Stream a (???) 

Answer 2

Ваша проблема линия

interleaveStreams (Stream a arest) (Stream b brest) = (Stream a (Stream b (interleaveStreams arest brest))) 

Для того, чтобы функция возвращала даже начало результате как своих аргументов должны быть оценены, потому что вы по шаблону прямо на их конструкторах. Но вы используете его в

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

Это означает, что nthStream n не может вернуться ничего до nthStream (n+1) оценивали, что дает бесконечную рекурсию.

Чтобы это исправить, вы можете изменить второй рисунок в проблемной линии, чтобы быть явно ленивый с ~:

interleaveStreams (Stream a arest) ~(Stream b brest) = (Stream a (Stream b (interleaveStreams arest brest)))