如何高效处理共享度高的递归数据结构？

Question

考虑一个递归的分支数据结构：

data Tree a = Node (Tree a) (Tree a) | Leaf a
    deriving (Show)

可以构造Tree具有许多相同分支的 a ，并且这似乎可以有效处理（至少在 GHC 中） - 例如，通过：

maketree :: Integer -> a -> Tree a
maketree 1 value = Leaf value
maketree depth value = let child = maketree (depth-1) value in Node child child

maketree 32 "Hello"将返回Tree String概念上包含 4294967295 个节点的 a - 但实际上只有 32 个节点将存储在内存中，并且 的主体maketree将仅被评估 32 次。

但是，假设我们实际上尝试以某种方式使用整个树 - 例如，计算节点数：

count :: Tree a -> Integer
count n = case n of
    Leaf _   -> 1
    Node a b -> 1 + count a + count b

count (maketree 32 "Hello")将（正确）评估为 4294967295，但它将通过评估count4294967295 次的主体来实现。

但是由于实际上只有 32 个“节点对象”存储在内存中，并且由于count是纯的（作为 Haskell 函数），因此应该可以缓存每个节点对象的结果，并且count总共只评估32 次。

有没有办法让 GHC（或任何 Haskell 实现）做到这一点？