3

假设我有这种Tree类型：

{-# LANGUAGE DeriveFoldable, DeriveFunctor #-}

data Tree a = Leaf | Branch (Tree a) a (Tree a) deriving(Functor,Foldable)

instance Traversable Tree where -- equivalent to the one I could derive, but written out for clarity
  traverse _ Leaf = pure Leaf
  traverse f (Branch l x r) = Branch <$> traverse f l <*> f x <*> traverse f r

编写一个函数来计算特定类型内事物的最大深度很容易：

depth Leaf = 0
depth (Branch l _ r) = 1 + max (depth l) (depth r)

但是要计算任意Traversable. 我已经知道这Functor还不够，因为您无法通过 获得有关它们内部事物“位置”的信息fmap，而且我也已经知道这Foldable还不够，因为foldr两者foldMap都只提供尽可能多的信息列表的结构。Traversable不过，可能是因为它比Functor和更通用Foldable。

但是，在做了一些实验之后，我认为Traversable两者都没有办法。到目前为止，这是我的逻辑。考虑这两棵树：

fooTree = Branch (Branch Leaf () Leaf) () (Branch Leaf () Leaf)
barTree = Branch (Branch Leaf () (Branch Leaf () Leaf)) () Leaf

现在，traverse (\() -> thingy) fooTree是：

Branch <$> (Branch <$> pure Leaf <*> thingy <*> pure Leaf) <*> thingy <*> (Branch <$> pure Leaf <*> thingy <*> pure Leaf)

在大量使用应用法则和一些简化之后，它变成：

(\x y z -> Branch (Branch Leaf x Leaf) y (Branch Leaf z Leaf)) <$> thingy <*> thingy <*> thingy

同样，traverse (\() -> thingy) barTree是：

Branch <$> (Branch <$> pure Leaf <*> thingy <*> (Branch <$> pure Leaf <*> thingy <*> pure Leaf)) <*> thingy <*> pure Leaf

在大量使用应用法则和一些简化之后，它变成：

(\x y z -> Branch (Branch Leaf x (Branch Leaf y Leaf)) z Leaf) <$> thingy <*> thingy <*> thingy

现在看起来它们具有相同的“形状”（唯一的区别是开头的 lambda，甚至它们的类型都相同），但它们来自具有不同深度的树traverse (\() -> thingy) fooTree。traverse (\() -> thingy) barTree这使我相信不可能找到 的深度traverse，但我不是 100% 确定它，我不知道如何严格解释它。

我说得对吗，这是不可能的？如果是这样，那么如何才能真正严格地解释这一点？如果没有，那么你将如何实现它？

4

1 回答 1

4

这确实是不可能的，因为从Foldable到Traversable实际上并没有帮助。获取Trees 的深度需要合并一个分支下两个子树的信息。据，直到...为止...

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)

... 就……而言，任何这样的合并只能通过结果的组合应用效果来实现f（合法的traverse必须保持t结构的形状，每个值都是通过函数b从单个值中获得的）。但是，已经可以通过...获得综合效果。aa -> f bFoldable

traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()

......所以额外的力量在Traversable这里没有任何区别。

如果仅仅指向traverse_感觉不够清晰，这里有一种替代方式来呈现上述论证的最后一步。的自然性属性之一traverse是 Bird 等人称为“数据类型中的“自然性””的属性。在了解惯用的向后和向前遍历（有关详细信息，请参阅该论文的第 6 节）：

-- r is a natural transformation that preserves toList:
-- toList = toList . r
fmap r . traverse f = traverse f . r

考虑一个任意的toList保留树重排r :: Tree a -> Tree a，以及一些f这样的结果以traverse f某种方式对树的深度进行编码。因为，如上所述，只有组合效果对计算深度很重要，所以对深度的fmap (const ()) . traverse f编码与traverse f. 现在，让我们取 naturality 属性并fmap (const ())在两边进行组合：

fmap (const ()) . fmap r . traverse f = fmap (const ()) . traverse f . r
-- Or simply:
fmap (const ()) . traverse f = fmap (const ()) . traverse f . r

由于fmap (const ()) . traverse f对深度进行编码，这意味着r无论它是什么，都不会改变树的深度。然而，情况并非如此，例如，如下反例所示：

-- Makes a tree with only leaves as left subtrees, preserving traversal order.
-- Assuming a toList that matches your traverse, or the derived one. 
straighten :: Tree a -> Tree a
straighten = foldr dangle Leaf . toList
    where
    dangle x t = Branch Leaf x t
于 2019-09-26T03:34:48.157 回答