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 中有 none，"范围" 的概念就足够了。

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"]

foldTree一步步评估

foldTree step-by-step evaluation

haskell

functional-programming

scope

closures

evaluation