是否无法获得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必须保留t结构的形状，并且每个b值为通过a函数从单个a -> f b值获得）。但是，要获得综合效果，is already possible through Foldable ...

Foldable

...因此traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f () 的附加幂在这里没有区别。

[如果仅指向Traversable感觉不够清晰，这是呈现上述论证的最后一步的另一种方法。 Bird等人将traverse_的自然属性之一称为“数据类型中的”自然”。在traverse中（有关详细信息，请参见该论文的第6节）：

Understanding Idiomatic Traversals Backwards and Forwards

[考虑任意保留

-- 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一样。现在，让我们采用naturality属性，并在两边都组成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 ()) . traverse f不管它是什么，都不会改变树的深度。然而，事实并非如此，例如，例如此反例所示：

r