1

我试图计算三叉树的平均值。似乎不可能在一个函数中完成它。有什么办法可以解决这个问题，还是需要使用两个函数？谢谢。

-- 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
4

1 回答 1

2

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

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

-- 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 实践是通过将树遍历分包给通用函数来改进问题，也就是说，我们（或语言库）无论如何都会提供函数以支持我们的树结构，而不考虑任何数字问题。

关于普通列表...

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

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

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

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

我们如何只遍历列表一次？好吧，计算平均值显然是一种折叠操作，即您遍历复杂的结构以产生单个值。请参阅Graham Hutton 的经典论文，了解折叠操作的优点。

列表有一个Foldablechepner 评论中提到的类的实例。因此，除其他外，该库还提供了一个foldr列表函数：

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

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

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

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 程序员都会同意这算作一个函数 :-)

请注意，也可以使用GHC 扩展来提供Functor实例，从而提供fmap函数。DeriveFunctor

于 2021-06-05T12:01:29.703 回答