Оценка предложения where в циклических списках

Question

В Мышление функционально в Haskell (стр. 213) показаны две версии циклического списка. Один оценивает в квадратичное время:

iterate3 f x = x:map f (iterate3 f x) 

iterate3 (2*) 1 
= 1:map (2*) (iterate3 (2*) 1) 
= 1:2:map (2*) (map (2*) (iterate3 (2*) 1)) 
= 1:2:4:map (2*) (map (2*) (map (2*) (iterate3 (2*) 1))) 

Другой, который использует where, оценивает линейное время:

iterate2 f x = xs where xs = x:map f xs 

iterate2 (2*) 1  
xs   where xs = 1:map (2*) xs 
= 1:ys  where ys = map (2*) (1:ys) 
= 1:2:zs where zs = map (2*) (2:zs) 
= 1:2:4:ts where ts = map (2*) (4:ts) 

Я не совсем понимаю эту оценку. Как x переназначается для каждого последующего элемента списка вместо 1 (как в первой версии)?

Answer 1

Важная деталь заключается в том, что xs в iterate2 определяется в терминах самого себя, создавая круговую структуру.
(Это иногда называют «связыванием узла».)

Визуализируя это как график, оценка выглядит примерно так (предупреждение: искусство ASCII).

xs where xs = 1 : map (2*) xs:

 : <----------+ 
/ \   | applies to 
    1 map (2*) --+ 

-->

 : 
/ \ 
    1  : <--------+ 
    / \   | applies to 
    2 map (2*) --+ 

-->

 : 
/ \ 
    1  : 
    / \ 
    2  : <---------+ 
     / \   | applies to 
     4 map (2*) --+ 

И так далее.

Answer 2

Давайте раскатать рекурсию в iterate2:

xs = x : map f xs 
    = x : map f (x : map f xs)       -- Inline xs 
    = x : (f x) : map f (map f xs)      -- Definition of map 
    = x : (f x) : map f (map f (x : map f xs))   -- Inline xs 
    = x : (f x) : map f ((f x) : map f (map f xs))  -- Definition of map 
    = x : (f x) : (f (f x)) : map f (map f (map f xs))) -- Definition of map 
    ... 

Таким образом, вы можете увидеть, что список, возвращаемый iterate2 f x имеет x в качестве первого элемента, f x как второй, и так далее.