haskell - 是否无法获取 Traversable 中元素的深度？

Question

假设我有这个 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

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

我说这是不可能的吗？如果是这样，那么实际上如何严格解释呢？如果没有，那么您将如何实现？

Answer 1

这确实是不可能的，因为从 Foldable 到 Traversable 实际上无济于事。获取 Tree 的深度需要合并来自分支下两个子树的信息。至于……

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

... 就此而言，任何此类合并只能通过结果的组合应用效果 f 来实现(合法的 traverse 必须保持 的形状code>t 结构，每个 b 值都是通过 a -> f b 函数从一个单独的 a 值获得的)。但是，获得综合效果，is already possible through Foldable ...

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

...因此 Traversable 的额外功能在这里没有任何区别。

如果仅仅指向 traverse_ 感觉不够清晰，这里有另一种方式来呈现上述论证的最后一步。 traverse 的自然属性之一被 Bird 等人称为“数据类型中的‘自然’”。在 Understanding Idiomatic Traversals Backwards and Forwards (有关详细信息，请参阅该论文的第 6 节):

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

考虑一个任意的 toList-preserving tree rearrangement r::Tree a -> Tree a 和一些 f 这样的结果traverse f 以某种方式对树的深度进行编码。因为，如上所述，对于计算深度，fmap (const ()) 只有组合效应很重要。 traverse f 将像 traverse f 一样对深度进行编码。现在，让我们利用自然属性，在两边组成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 ()) 。遍历 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