Traversable类型类的目的

Question

有人可以向我解释,类型类的目的是Traversable什么？

类型定义是:

class (Functor t, Foldable t) => Traversable (t :: * -> *) where

这Traversable是一个Functor t和Foldable t.

该traverse函数是其成员Traversable并具有以下签名:

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

为什么结果必须包含在应用程序中？有什么意义呢？

我有以下示例:

module ExercisesTraversable where

  import Test.QuickCheck (Arbitrary, arbitrary)
  import Test.QuickCheck.Checkers (quickBatch, eq, (=-=), EqProp)
  import Test.QuickCheck.Classes (traversable)

  type TI = []

  newtype IdentityT a = IdentityT a
    deriving (Eq, Ord, Show)

  instance Functor IdentityT where
    fmap f (IdentityT a) = IdentityT (f a)

  instance Foldable IdentityT where
    foldMap f (IdentityT a) = f a

  instance Traversable IdentityT where
    traverse f (IdentityT a) = IdentityT <$> f a

  instance Arbitrary a => Arbitrary (IdentityT a) where
    arbitrary = do
      a <- arbitrary
      return (IdentityT a)

  instance Eq a => EqProp (IdentityT a) where (=-=) = eq

  main = do
    let trigger = undefined :: TI (Int, Int, [Int])
    quickBatch (traversable trigger)  

我们来看看traverse实现:

traverse f (IdentityT a) = IdentityT <$> f a

应用程序的结果类型f a必须是一个应用程序,为什么？算子不够吗？

Answer 1

Identity是一个很糟糕的例子,因为它总是只包含一个值.你是对的 - 在这种情况下,Functor f约束就足够了.但显然,大多数可穿越者并不是那么结构性的微不足道.

traverse它是什么:它以一些明确指定的顺序"访问"容器中的所有元素,对它们执行一些操作,并按原样重建结构.这比任何一个都强大

• Functor t,它还允许您访问/修改所有元素并重建结构,但只能完全相互独立(因此允许选择任意的计算顺序,在任何元素之前将thunk返回到结构中) lazily)映射到所有,等等).

• Foldable t,它以线性顺序带来元素,但不重建结构.基本上,Foldable只是可以降级为简单列表的容器类,如见证所示

  toList :: Foldable t => t a -> [a]
  

  ......或任何幺半群类型的串联,通过

  foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
  

  这里,通过幺半群操作组合对每个元素的操作的结果(或者,如果没有元素,则结果是mempty).

在这种情况下traverse,Applicative f约束基本上将这种幺半群组合提升到可以重建结构的东西.通信是

mempty      ::   m
pure mempty :: f m

和

(<>)        ::   m ->   m ->   m
liftA2 (<>) :: f m -> f m -> f m

...但另外,因为f也是一个仿函数,你可以将局部结果包装在任何数据构造函数中,从而不仅构建类似通用列表的东西,而且构建一个任意容器,包括一个具有原始结构的容器.

Answer 2

应用程序fa的结果类型必须是一个应用程序,为什么？算子不够吗？

这是一个很棒的问题.最初的McBride和Paterson论文走向了另一个方向:它注意到很多计算本质上是适用的(可以用pure和重写<*>).然后它注意到某些容器,例如[],允许这种类型的功能:

 idist :: Applicative f => [f a] -> f [a]
 idist = ...

我们现在sequence在Traversable课堂上打电话.一切都很好,但是当我们编写抽象时,它有助于探究我们假设的强度.如果我们尝试构建一个可遍历的库而不Applicative使用,该Functor怎么办？究竟会出什么问题？

产品!

为此,有助于阅读Jaskelioff和Rypacek论文,该论文试图确定类别理论中与应用函子和可遍历容器相对应的结构.可穿越集装箱最有趣的特性是它们在有限的总和和产品下是封闭的.这对Haskell编程非常有用,可以使用sums和products定义大量数据类型:

data WeirdSum a = ByList [a] | ByMaybe (Maybe a)

instance Traversable WeirdSum where
  traverse a2fb (ByList as) =
    ByList <$> traverse a2fb as
  traverse a2fb (ByMaybe maybeA) =
    ByMaybe <$> traverse a2fb maybeA

啊,更多证据表明我们不需要Applicative的全部力量!我们只fmap在这里使用.现在有限的产品:

data WeirdProduct a = WeirdProduct [a] (Maybe a)

instance Traversable WeirdProduct where
  traverse a2fb (WeirdProduct as aMaybe) =
    WeirdProduct <$> traverse a2fb as <*> traverse a2fb aMaybe

在这里,不可能只使用仿函数来编写一个定义:fmap对于总和很有用,但是我们无法将两个不同的函数值"粘合"在一起.只有<*>这样我们才能在有限的产品上"关闭"可移动的容器.

这一切都很好,但缺乏精确性.我们在这里挑选的证据Functor可能很糟糕,但我们是否可以从Applicative我们需要的第一原则进行论证,不多也不少？

分类理论!

这个问题在Jaskelioff和Rypacek论文的后半部分得到了解决.在类别理论术语中,如果算子T允许一系列自然变换,则它是可遍历的

{ sequence | sequence : TFX -> FTX, any applicative F }

其中每个自然变换都是"F中的自然变形",并且尊重" 应用仿函数组合的单一结构 ".这是最后一个短语,是最后一小段行话,重要的是有Applicative而不是Functor.有了Applicative f,我们能够胶水类型的值一起f a和f b,我们对他们的行为要么(一拉foo <$> fa <*> fb在那里foo :: a -> b -> c和fa, fb :: f a, f b)或只是推他们到一个元组f (a, b).这产生了上述"幺半群结构"; 我们需要这样才能证明可穿越仿函数是关于有限积的,就像我们在上面所展示的那样.如果没有应用程序,我们甚至无法开始讨论仿函数和产品如何交互!如果Hask是我们的Haskell类型的类别,然后一个适用仅仅是一种方式来命名Hask至- Hask endofunctors说,"表现良好",围绕(->)类型和产品类型.

希望这个双管齐下的答案,一个在实际编程中,一个在分类foo-foo中,在谈论可穿越性时给出了一个关于为什么你想要应用函子的直觉.我认为通常可穿越的东西是围绕着他们的魔法元素引入的,但是他们非常依赖于具有坚实理论基础的实际关注.其他语言生态系统可能有更容易使用的迭代模式和库,但我喜欢简单和优雅的traverse和sequence.

Answer 3

Traversable在Haskell中,使用"内部迭代器"的概念统一了映射在容器上的概念(获得类似形状的容器),该概念对每个元素执行效果.

与外部迭代器相比,内部迭代器受到限制,因为我们不能使用为一个元素获得的值来决定如何处理其他元素.我们不能说"mmmm,如果某个元素的操作返回7,则在处理下一个元素时启动导弹".

这种类型的"刚性"计算,不能根据中间确定的值改变过程,在Applicative类型中由Haskell表示.这就是原因Traversable(容器)和Applicative(效果)齐头并进的原因.Functor是不够的,因为它没有提供组合有效行动的方法.

允许任何形式的Applicative效果是一个福音; 这意味着我们可以遍历执行IO的容器,从故障中提前存在,收集日志消息,从失败的迭代中收集错误消息,同时迭代 ......或这些效果的任意组合.