4

由于惰性求值，Haskell 可以立即处理以下表达式。

head.head $ let m = 1000000000000000 in map (\n -> [m*n .. m*(n+1)]) [1 .. m]

但我注意到下面的表达式没有完成，但内存使用率仍然很低。

last.last $ let m = 1000000000000000 in map (\n -> [m*n .. m*(n+1)]) [1 .. m]

haskell 能做到这一点并不奇怪。但我想知道它是如何工作的。更准确地说，haskell 如何分配内存。有没有办法检查内存布局或类似的东西？

4

2 回答 2

9

让我们稍微简化一下这个例子，看看会发生什么。您只需考虑惰性求值和图形缩减就可以解决大部分问题，而无需进行任何更低级别的操作。ourLast (mkList 3)让我们看一下这段代码的简化简化：

ourLast :: [a] -> a
ourLast [] = error "ourLast []"
ourLast (x:[]) = x
ourLast (_:xs) = ourLast xs

mkList :: Int -> [Int]
mkList 0 = []
mkList n = let rest = mkList (n-1) in n : rest

?foo意思是“我们还没有看过的值”。我们用“let”创建这些。 foo@bar意思是“我们已经计算bar出的?foo值是”foo@bar foo := barfoobar

    -- We start here by creating some value and giving it to ourLast to
    -- look at.
let ?list3 = mkList 3
ourLast ?list3
    -- At this point ourLast examines its argument to figure out whether
    -- it's of the form (_:_) or []
    -- mkList sees that 3 /= 0, so it can pick the second case, and it
    -- computes the value for ?list3.
    -- (I'll skip the arithmetic reductions and other boring things.)
    let ?list2 = mkList 2
    list3 := 3 : ?list2 -- we don't need to compute ?list2 yet, so
                        -- (mkList 3) is done and we can go back to ourLast
ourLast list3@(3 : ?list2)
    -- ourLast needs to examine ?list2 to find out whether it's [] or not,
    -- so mkList does the same thing again
    let ?list1 = mkList 1
    list2 := 2 : ?list1
ourLast list3@(3 : list2@(2 : ?list1))
    -- Now ourLast has enough information to continue;
    -- ourLast (_ : xs@(_ : _)) = ourLast xs
    -- Notice how we don't need to compute list2 a second time; we save its
    -- value the first time we compute it. This is what lazy evaluation is.
ourLast list2@(2 : ?list1)
    -- at this point, there are no references to `list3` anywhere, so it
    -- can be GCed.
    -- Repeat (ourLast examines ?list1, mkList sees that 1 /= 0).
    let ?list0 = mkList 0
    list1 := 1 : ?list0
ourLast list2@(2 : list1@(1 : ?list0))
ourLast list1@(1 : ?list0)
    -- Can GC list2.
    -- Now mkList is being called with 0, so it just returns an empty list.
    list0 := []
ourLast list1@(1 : list0@[])
1
    -- We're done! (And we can GC list1.)

请注意，在任何给定时间，我们只需要实际分配几个 thunk，其余的要么尚未计算，要么可以进行 GC。当我们评估时，评估在和ourLast list3之间来回跳转（有点像协程）。ourLastmkList

如果您想更准确地了解 Haskell 编译器的工作原理，在“分配何时以及如何发生”的级别上，以下内容很有帮助：

仅从图形简化的角度来大致了解惰性求值的工作原理——例如这篇文章——是有用的。

于 2012-11-28T12:22:22.823 回答
2

我会按照此处的说明进行一些堆分析。为此，您需要使用 cabal 安装分析库。该解释非常全面且易于理解。

于 2012-11-28T11:16:06.963 回答