サイクリックリストのWHERE句の評価

Question

Haskellの機能的な考察（p 213）では、サイクリックリストの2つのバージョンが示されています。一つは、二次の時間に評価されます。

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

重要な詳細は、iterate2のxsがそれ自体で定義され、循環構造を作成することです。

グラフとして視覚化すると、評価は次のようになります（警告：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を見て、することができます。