Traversable相较于Foldable有哪些“独特的方法”？

Question

Traversable相较于Foldable有哪些“独特的方法”？

8

Foldable 是 Traversable 的超类，类似于 Functor 是 Applicative 和 Monad 的超类。

类似于 Monad 的情况，可以基本上将 fmap 实现为:

liftM :: Monad m => (a->b) -> m a -> m b
liftM f q = return . f =<< q

我们还可以将foldMap模拟为

foldLiftT :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldLiftT f = fst . traverse (f >>> \x -> (x,x))
           -- or: . sequenceA . fmap (f >>> \x -> (x, x))

使用Monoid m => (,) m单子。因此，超类和方法的组合在两种情况下都有一定的冗余。

在单子的情况下，可以认为类型类的“更好”定义是（我将跳过applicative / monoidal）。

class (Functor m) => Monad m where
  return :: a -> m a
  join :: m (m a) -> m a

至少在范畴论中是这样使用的。这个定义不使用Functor超类，不允许liftM，因此它没有这种冗余。

Traversable类是否可以进行类似的转换？

澄清一下：我想重新定义它，我们称之为

class (Functor t, Foldable t) => Traversable t where
  skim :: ???

这样我们就可以将实际的 Traverse 方法变成顶级函数。

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

但是通常无法通用化

instance (Traversable t) => Foldable t where
  foldMap = ... skim ...

data T
instance Traversable T where
  skim = ...

我提出这个概念性问题并不是因为我特别需要它; 而是为了更好地理解 Foldable 和 Traversable 之间的区别。就像 Monad 和 Functor 一样：在日常 Haskell 编程中，>>= 比 join 更方便（因为你通常需要精确地结合 fmap 和 join），但后者使得理解单子变得更加简单。

- leftaroundabout

1

独特的方法是“traverse”。你不能用“Foldable”实现它。 - Gabriella Gonzalez

当然不可以，但你可以通过使用 traverse 实现 Foldable。 - leftaroundabout

1

这就是为什么Foldable是Traversable的超类。超类应该可以根据子类来实现。 - Gabriella Gonzalez

1

我认为@leftaroundabout的问题等同于：你能否定义一个类TraversableMinusFoldable，使得class（Foldable t，TraversableMinusFoldable t）=> Traversable t where没有新函数，但现有函数是兼容的。也就是说，你能否在不引用Foldable中的任何内容的情况下定义traverse。但即使是这个问题，我也不确定这是否是研究这种情况的正确方式。旧的Monad很混乱，最好忘记它 :-) - misterbee

1

@misterbee：这差不多了，但还不够。我感兴趣的只是为Traversable方法提供“最弱签名”，以便实际使用需要Foldable超类。目前，你可以像在历史悠久的Monad中那样省略超类，但正如你所说的那样并不好。 - leftaroundabout

2个回答

3

因时间较晚，这里的解释可能有些含糊，但可遍历（Traversable）相较于可折叠（Foldable）更具备重建原始数据结构的能力。例如，在列表中：

module MyTraverse where

import Data.Foldable
import Data.Traversable
import Control.Applicative
import Data.Monoid

data ListRec f x = ListRec
  { el :: f (Endo [x])
  }

instance Applicative f => Monoid (ListRec f x) where
    mempty = ListRec (pure mempty)
    mappend (ListRec l) (ListRec r) =
        ListRec (mappend <$> l <*> r)

toM :: Functor f => f b -> ListRec f b
toM this = ListRec $ (Endo . (:)) <$> this

fromM :: Functor f => ListRec f b -> f [b]
fromM (ListRec l) = flip appEndo [] <$> l

myTraverse :: Applicative f => (a-> f b)  -> [a] -> f [b]
myTraverse f xs = fromM $ foldMap (toM . f) xs

我认为这个myTraverse与traverse的行为相同，仅使用Applicative、Foldable和Monoid这些类。如果您想要摆脱Monoid，可以重新编写它，使用foldr代替foldMap。

由于列表是一种扁平结构，因此很容易处理。但是，我强烈怀疑您可以使用Zipper来获取任意结构的适当重构函数（因为Zipper是可以泛化推导的，所以它们应该总是存在）。

但即使有了Zipper，您也没有任何方法将该结构传递给Monoid/函数。从概念上讲，似乎Traversable添加了一些东西。

class Traversed t where
  type Path t :: *
  annotate :: t a -> [(Path t, a)]
  fromKeyed :: [(Path t, a)] -> t a

这似乎与Foldable有很大的重叠，但我认为在试图将路径与其组成值关联时，这是不可避免的。

- John L

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- J. Abrahamson · Accepted Answer

Foldable是对应于Functor的，就像Traversable是对应于Monad的，即Foldable和Functor是Monad和Traversable的超类（除了所有的applicative/monad提案噪音）。

事实上，这已经在代码中了。

instance Foldable f => Traversable f where
  ...

因此，目前还不清楚需要更多的是什么。 Foldable 的特点在于 toList :: Foldable f => f a -> [a]，而 Traversable 不仅仅能像 toList 一样将内容抽象为列表，还能提取形状。

shape :: Functor f => f a -> f ()
shape = fmap (const ())

然后重新组合它们

combine :: Traversable f => f () -> [a] -> Maybe (f a)
combine f_ = evalStateT (traverse pop f_) where
  pop :: StateT [a] Maybe a
  pop = do x <- get
           case x of
             [] = empty
             (a:as) = set as >> return a

这取决于traverse。

有关此属性的更多信息，请参见Russell O'Connor的博客文章。