Haskell佈局樹

Question

最近，我試圖解決Haskell 99問題，第66（緊湊地佈局一棵樹）。我成功了，但被這裏的解決方案搞糊塗了（http://www.haskell.org/haskellwiki/99_questions/Solutions/66）。

layout :: Tree a -> Tree (a, Pos) 
layout t = t' 
    where (l, t', r) = layoutAux x1 1 t 
    x1 = maximum l + 1 

    layoutAux :: Int -> Int -> Tree a -> ([Int], Tree (a, Pos), [Int]) 
    layoutAux x y Empty = ([], Empty, []) 
    layoutAux x y (Branch a l r) = (ll', Branch (a, (x,y)) l' r', rr') 
     where (ll, l', lr) = layoutAux (x-sep) (y+1) l 
      (rl, r', rr) = layoutAux (x+sep) (y+1) r 
      sep = maximum (0:zipWith (+) lr rl) `div` 2 + 1 
      ll' = 0 : overlay (map (+sep) ll) (map (subtract sep) rl) 
      rr' = 0 : overlay (map (+sep) rr) (map (subtract sep) lr) 

-- overlay xs ys = xs padded out to at least the length of ys 
-- using any extra elements of ys 
overlay :: [a] -> [a] -> [a] 
overlay [] ys = ys 
overlay xs [] = xs 
overlay (x:xs) (y:ys) = x : overlay xs ys 

爲什麼'x1'和'sep'的計算不會導致infinit循環？ 他們是如何計算的？

Answer 1

使用Haskell的原因是non-strict evaluation mode，而不是您在大多數語言中看到的嚴格評估。

在你給的例子，maximum l可以計算出，因爲l從layoutAux函數返回不包含在x1任何依賴。 x1用於返回值的t'部分。

另一個簡單的例子來顯示出類似的行爲是下面的代碼：

hello :: [Int] -> [Int] 
hello x = x' where 
    x' = hello' l x 
    l = length x' 
    hello' i lst = map (+i) lst 

這不會永遠循環下去，因爲得到一個列表的長度，你不需要知道它的內容，這就是爲什麼在列表內容依賴於l不會導致它永遠循環。而如果你有類似maximum而不是長度的東西，那會導致它永遠循環，因爲maximum需要知道列表的內容，並且內容取決於maximum的結果。