8

Foldable是 的超类Traversable，类似于andFunctor的超类。ApplicativeMonad

与 的情况类似，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单子。所以超类和方法的结合在这两种情况下都有一定的冗余。

在单子的情况下，可以说类型类的“更好”定义将是（我将跳过应用程序/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。再次很像Monadvs Functor：虽然>>=比join日常的 Haskell 编程更方便（因为你通常需要和的这种组合），但后者更容易掌握 monad 的含义。fmapjoin

4

2 回答 2

3

Foldableis to Functoras Traversableis to Monad，即Foldable和Functor是 and 的超类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 的这篇博文。

于 2014-01-13T03:42:38.373 回答
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行为相同。如果您想摆脱.traverseApplicativeFoldableMonoidfoldrfoldMapMonoid

列表很简单，因为它们是扁平结构。但是，我强烈怀疑您可以使用 Zipper 为任何结构获得正确的重建功能（因为 zippers 通常是可导出的，它们应该始终存在）。

但即使使用拉链，您也没有任何方法可以将该结构指示给 monoid/function。从概念上讲，它似乎Traversable增加了类似的东西

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

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

于 2014-01-13T09:59:20.913 回答