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 

Почему caculation 'x1' и 'sep' не вызывает бесконечную петлю? Как они были рассчитаны?

Answer 1

Причина этого в работе: 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 должен знать содержимое списка, а контент зависит от результата maximum.