Haskell：三元树平均值，带有嵌套的“where”

Question

我正在尝试计算三元树的平均值。似乎不可能在一个函数内完成它。有什么办法可以解决这个问题，还是必须用两个函数？谢谢

-- define a tree
data Ttree t = Nil | Node3 t (Ttree t) (Ttree t) (Ttree t)

-- get the Ternary tree and return the average
treeAverage :: Ttree Double -> Double
treeAverage Nil = 0.0    -- empty tree
treeAverage tree = treeAverage' tree (0.0) 
           -- try to use accumulator and another function 
  where
    treeAverage' Nil _ =  0.0    -- empty tree
    treeAverage' (Node3 n left mid right) (sum/count) = 
        ((n+sumL+sumM+sumR) / (1+countL+countM+countR))  -- average
      where
        (sumL,countL) = treeAverage' left 
            -- calculate left subtree with sum and count
        (sumM,countM) = treeAverage' mid 
        (sumR,countR) = treeAverage' right

Answer 1

为了计算平均值，您必须在过程的最后执行一次除法，类似于 (allSum / allCount)。由于除法不能成为递归树遍历过程的一部分，因此似乎很难在一个函数内实现你想要的。

让我们首先为您的代码提供一些修复。尚不清楚您的辅助 treeAverage' 函数 returns 是一对还是单个数值。我们可以像这样重写整个事情，其中明确地 returns 一对：

-- define a tree structure:
data Ttree t = Nil | Node3 t (Ttree t) (Ttree t) (Ttree t)
                  deriving (Eq, Show)

treeAverage1 :: Ttree Double -> Double
treeAverage1 Nil = 0.0 -- empty tree
treeAverage1 tree =
  let   (sum1, count1) = treeAverage' tree
  in    sum1 / count1
    where
      treeAverage'  Nil  =  (0,0) -- empty tree
      treeAverage'  (Node3 n left mid right) =
          let  (sumL,countL) = treeAverage' left   -- calculate left subtree
               (sumM,countM) = treeAverage' mid 
               (sumR,countR) = treeAverage' right
          in
              ((n+sumL+sumM+sumR) , (1+countL+countM+countR)) -- (sum, count)

并且该代码似乎有效：

$ ghci
 GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
 λ> 
 λ> :load  q67816203.hs
 Ok, one module loaded.
 λ> 
 λ> leaf x = Node3 x Nil Nil Nil
 λ> 
 λ> tr0 = Node3 4 (leaf 5) (leaf 6) (leaf 7) :: Ttree Double
 λ> tr1 = Node3 2 (leaf 10) tr0 (leaf 15)
 λ> 
 λ> tr1
 Node3 2.0 (Node3 10.0 Nil Nil Nil) (Node3 4.0 (Node3 5.0 Nil Nil Nil) (Node3 6.0 Nil Nil Nil) (Node3 7.0 Nil Nil Nil)) (Node3 15.0 Nil Nil Nil)
 λ> 
 λ> treeAverage1 tr1
 7.0
 λ>

但是，在这段代码中，树遍历与算术密不可分。

解耦...

常见的 Haskell 做法是通过分包树遍历通用功能来改进问题，即我们（或语言库）将提供的功能无论如何为了支持我们的树结构，不管任何数字问题。

关于普通列表 ...

到那时，我们可以考虑一个更简单的问题：我们如何计算普通 list 数字的平均值？

正如 chepner 在评论中提到的，您可以使用：

listAverage xs = (sum xs) / (length xs)

我们可以将这种方法应用于 Ttree 个对象，并提出 treeSum 和 treeLeafCount 函数。但那将是次优的。在现代硬件中，内存访问比算术更昂贵，并且 listAverage 不必要地遍历列表两次 .

我们如何才能只遍历列表一次？好吧，计算平均值显然是一个 fold 操作，也就是说你遍历一个复杂的结构以产生一个单一的值。参见 classic paper by Graham Hutton 关于折叠操作的优点。

列表有 chepner 评论中提到的 Foldable class 的实例。因此，该库提供了一个 foldr 列表函数：

foldr :: (a -> b -> b) -> b -> [a] -> b

foldr的第一个参数是一个组合函数，它从输入列表中获取一个累加器值和一个标量值，returns一个更新的累加器值。第二个参数只是累加器的初始值。

所以我们可以这样写一个单遍历列表平均：

listAverage :: [Double] -> Double
listAverage xs  =  sum1 / count1
  where
    cbf x (sum0, count0) = (sum0+x, count0+1)  --  combining function
    (sum1, count1) = foldr cbf (0,0) xs

这很好用：

 λ> 
 λ> :type listAverage
 listAverage :: [Double] -> Double
 λ> 
 λ> listAverage [1,2,3,4,5]
 3.0
 λ>

现在，我们可以将这种方法应用于树吗？

树遍历

所以我们需要以某种方式为我们的树获得一个 foldr 的版本。

我们可以手动编写，从右到左遍历结构：

treeFoldr  ::  (v -> r -> r) -> r -> Ttree v -> r
treeFoldr cbf r0  Nil  =  r0
treeFoldr cbf r0  (Node3 v left mid right)  =
    let  rr = treeFoldr cbf  r0  right
         rm = treeFoldr cbf  rr  mid
         rl = treeFoldr cbf  rm  left
    in
         cbf v rl

请注意，这里能够指定初始累加器值非常重要。

所以我们现在有一个树遍历机制，它是完全通用的并且与任何数字问题无关。

例如，我们可以用它来展平任何类型的（可能是非数字的）树：

toListFromTree:: Ttree v -> [v]
toListFromTree tr  =  let  cbf = \v vs -> v:vs
                      in   treeFoldr cbf [] tr

这可以进一步简化：

toListFromTree tr  =  treeFoldr (:) [] tr

测试：

 λ> 
 λ> treeFoldr (:) [] tr1
 [2.0,10.0,4.0,5.0,6.0,7.0,15.0]
 λ>

此时，我们可以为树定义 Foldable 实例：

instance Foldable Ttree  where  foldr = treeFoldr

上面列表平均器的相当短的代码现在可以不加修改地用于平均树，主要是通过调整其类型签名。

treeAverage :: Ttree Double -> Double
treeAverage tr  =  sum1 / count1
  where
    cbf x (sum0, count0) = (sum0+x, count0+1)  --  combining function
    (sum1, count1) = foldr cbf (0,0) tr

现在，我们可以做些更简单的事情了。 GHC 编译器碰巧提供了一个扩展 DeriveFoldable，它允许我们要求编译器自动编写 treeFoldr。这直接导致我们的：

最短解法：

{-#  LANGUAGE  DeriveFoldable    #-}

-- define a tree structure:
data Ttree t  =  Nil  |  Node3 t  (Ttree t)  (Ttree t)  (Ttree t)
                  deriving  (Eq, Show, Foldable)

treeAverage :: Ttree Double -> Double
treeAverage tr = sum1 / count1
    where
        cbf x (s,c)    =  (s+x,c+1)
        (sum1, count1) =  foldr cbf (0,0) tr

而且我认为大多数 Haskell 程序员会同意这算作一个函数:-)

请注意，还可以提供 Functor 个实例，因此使用 DeriveFunctor GHC 扩展提供 fmap 函数。

Haskell：三元树平均值，带有嵌套的“where”

Haskell: ternary tree average, with nested `where`

haskell

average

ternary-tree

解耦...

关于普通列表 ...

树遍历

最短解法：