最近,我尝试解决 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'的计算不会导致无限循环? 它们是如何计算的?
最佳答案
其工作原理是 non-strict evaluation mode Haskell 的计算而不是您在大多数语言中看到的严格评估。
在您给出的示例中,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
需要知道list的内容,内容取决于maximum
的结果.
关于Haskell 布局树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19024318/