是否无法获取 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 获得有关它们内部事物的 "position" 的信息，而且我也已经知道仅 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看起来是一样的"shape"（唯一不同的是开头的lambda，连它们的类型都一样），但它们来自不同深度的树。这让我相信不可能找到 traverse 的深度，但我不是 100% 确定它，我不确定如何严格地解释它。

我说这不可能吗？如果是这样，那么实际上如何严格解释呢？如果没有，那你会如何实施？

Answer 1

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

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

... 就此而言，任何此类合并只能通过结果的组合应用效果 f 来实现（合法的 traverse 必须保持 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 等人称为“'naturality' in the datatype”的属性。在 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 保留树重排 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 ()) . 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

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

Is it impossible to get the depth of elements inside a Traversable?

haskell

depth

traversable