foldTree逐步评估

Question

假设foldTree、Tree和函数f的这些定义

foldTree : (a -> [b] -> b) -> Tree a -> b
foldTree f = go
    where
        go (Node x ts) = f x (map go ts)

tree :: Tree String
tree = Node
      "Alpha"
      [ Node "Beta" [Node "Epsilon" [], Node "Zeta" [], Node "Eta" []]
      , Node "Gamma" [Node "Theta" []]
      , Node "Delta" [Node "Iota" [], Node "Kappa" [], Node "Lambda" []]
      ]

f x xs = [x] <> (map ('\t' :) (concat xs))

我将尝试评估foldTree f tree

  foldTree f tree
= go (Node "Alpha" [ Node "Beta" [Node "Epsilon" [], Node "Zeta" [], Node "Eta" []], Node "Gamma" [Node "Theta" []], Node "Delta" [Node "Iota" [], Node "Kappa" [], Node "Lambda" []]]
= f "Alpha" (map go [...])
...

此时，我的问题是:等式推理是如何与闭包一起工作的？go的定义有f；但是，在它的参数之间肯定不是这样。有什么诡计允许插入这个定义吗？

Answer 1

简单地说，定义可以引用范围内的任何名称。

“闭包”是一个在突变的情况下更相关的概念。在没有“范围”的Haskell中，“范围”的概念就足够了。

go的定义嵌套在foldTree的定义中，因此可以访问它的参数f，换句话说，在go的定义中，f在范围内。

定义可以重写为

{-
foldTree f t = go t
    where
         go (Node x ts) = f x (map go ts)
-}
foldTree f t =
   let { go (Node x ts) = f x (map go ts) } 
   in go t

而任何调用foldTree f1 t1都被计算为

> foldTree f1 t1 
=>
  let { f=f1; t=t1 }
  in
    let { go (Node x ts) = f x (map go ts) } 
    in go t
=>
  ....

这些都是简单的嵌套let，因此内部可以访问外部名称所定义的每个名称。

为了更容易地了解正在发生的事情，首先尝试使用一个简单的示例数据(如Node "Alpha" []、Node "Alpha" [Node "Beta" []]等)对其进行评估。

例如，用

f0 x xs = [x] <> (map ('\t' :) (concat xs))

对Node "Alpha" []的评估进展如下

> foldTree f0 (Node "Alpha" []) 
=>
  let { f=f0; t=Node "Alpha" [] }
  in
    let { go (Node x ts) = f x (map go ts) } 
    in go t
=>
  let { f x xs = [x] <> (map ('\t' :) (concat xs))
      ; go (Node x ts) = f x (map go ts) 
      } 
  in go (Node "Alpha" [])
=>
  let { f x xs = [x] <> (map ('\t' :) (concat xs))
      ; go (Node x ts) = f x (map go ts) 
      ; (Node x1 ts1) = (Node "Alpha" [])
      } 
  in f x1 (map go ts1)
=>
  let { f x xs = [x] <> (map ('\t' :) (concat xs))
      ; go (Node x ts) = f x (map go ts) 
      ; x1 = "Alpha"
      ; ts1 = []
      ; xs1 = map go ts1
      } 
  in [x1] <> (map ('\t' :) (concat xs1))
=>
  ["Alpha"] <> (map ('\t' :) (concat []))
=>
  ["Alpha"] <> (map ('\t' :) [])
=>
  ["Alpha"] <> []
=>
  ["Alpha"]