haskell - Traversable1中的上下文范围

在semigroupoids包中，我找到了以下定义:

class (Foldable1 t, Traversable t) => Traversable1 t where
  traverse1 :: Apply f => (a -> f b) -> t a -> f (t b)
  sequence1 :: Apply f => t (f b) -> f (t b)

  sequence1 = traverse1 id
  traverse1 f = sequence1 . fmap f

为什么将上下文范围设置为Apply(不带Applicative的pure)而不设置为Functor？显然，您需要覆盖其中一个定义，因此仅使用Functor就能做到这一点吗？

最佳答案

这只是Traversable的稍微严格的定义-所有Traversable1都是Traversable，反之则不然。关于Traversable为什么需要Applicative的许多(许多)更多细节，也许值得一看Applicative Programming with Effects。手势上，如果您只有Functor，则该函子包含许多值时就不可能对其进行“排序”，因为“注入(inject)”函数(a -> f b)是获取b的唯一方法，而您不能join f的各层。

但是，广义上讲，当您定义Traversable时，您只需要对“默认”值使用无效果注入(inject)功能pure，这正是Traversable1消除的。这就是NonEmpty是实例但[]不是实例的原因。

为了使事情变得具体，请考虑身份函子，Maybe，NonEmpty列表和常规[]的这些示例实例。

newtype Id a = Id a
instance Functor Id where fmap f (Id a) = Id (f a)

instance Applicative Id where
  pure = Id
  (Id f) <*> (Id x) = Id (f x)

正是因为Functor仅具有一个元素并且没有“默认”分支，所以我们在这里只需要一个Id实例即可。

instance Traversable Id where traverse inj (Id a) = Id <$> inj a
instance Traversable1 Id where traverse1 inj (Id a) = Id <$> inj a

对于pure的“默认” Nothing情况(仅比Maybe稍微复杂一点)，我们需要Id。

instance Traversable Maybe where
  traverse _ Nothing = pure Nothing
  traverse inj (Just a) = Just <$> inj a

instance Traversable1 Maybe不存在，因为Maybe具有默认分支；我们看到这是因为如果我们只有pure约束，就不能使用Apply。

data NonEmpty a = NonEmpty a [a]

instance Functor NonEmpty where fmap f (NonEmpty a as) = NonEmpty (f a) (fmap f as)

instance Apply NonEmpty where
  (NonEmpty f fs) <.> (NonEmpty x xs) = NonEmpty (f x) (fs <*> xs)

instance Pointed NonEmpty where
  point a = NonEmpty a []

instance Applicative NonEmpty where
  (<*>) = (<.>)
  pure = point

instance Traversable NonEmpty where
  traverse inj (NonEmpty a as) = NonEmpty <$> inj a <*> (traverse inj a as)

由于我们只使用了(<*>)而不是pure，因此我们可以将其设为Traversable1实例

instance Traversable1 NonEmpty where
  traverse1 inj (NonEmpty a []) = (`NonEmpty` []) <$> inj a
  traverse1 inj (NonEmpty a (b: bs)) =
    (\a' (NonEmpty b' bs') -> NonEmpty a' (b': bs'))
    <$> inj a
    <.> traverse1 inj (NonEmpty b bs)

但这不适用于[]，因为我们最终将pure用于“默认”分支

instance Traversable [] where
  traverse _   []     = pure []
  traverse inj (x:xs) = (:) <$> inj x <*> traverse inj xs

编辑:最初，我对Traversable1 NonEmpty的定义玩得很快而松懈。当前版本确实有效，但在外观上要困难得多。以前，我尝试使用内部列表traversing，因为它在本质上是可行的，因为[]的第二个插槽中的NonEmpty具有第一个插槽来帮助它，但是由于内部列表的空格[]需要pure，因此无法直接使用。相反，我们必须通过“窃取”始终存在的a到第一个位置，然后在遍历之后将其替换来避免这种空的情况。

该方法(和数据类型定义)与Semigroups和Semigroupoids库本身中使用的版本非常相似，并且非常有用，因为它们可以利用常规[]背后的库动力，但是如果我们对NonEmpty进行一些不同的定义，我们可以看到存在一个Traversable和Traversable1之间存在很大的并行性。 Traversable1实例可以存在的事实确实是单独的数据类型的功能-定义基本上是相同的。

import Data.Monoid
import qualified Data.Semigroup as Se
import Data.Traversable
import Data.Foldable
import Data.Semigroup.Foldable
import Data.Semigroup.Traversable
import Data.Functor.Apply
import Control.Applicative

-- For comparison
data List     a = Empty | List a (List     a)
data NonEmpty a = One a | Many a (NonEmpty a)

instance Functor NonEmpty where
  fmap f (One a) = One (f a)
  fmap f (Many a as) = Many (f a) (fmap f as)

instance Apply NonEmpty where
  (One f) <.> (One a)         = One (f a)
  (One f) <.> (Many a _)      = One (f a)
  (Many f _) <.> (One a)      = One (f a)
  (Many f fs) <.> (Many a as) = Many (f a) (fs <.> as)

instance Applicative NonEmpty where
  pure = One
  (<*>) = (<.>)

instance Foldable NonEmpty where
  foldMap f (One a) = f a
  foldMap f (Many a as) = f a <> foldMap f as

instance Foldable1 NonEmpty where
  foldMap1 f (One a) = f a
  -- Core distinction: we use the Semigroup.<> instead of the Monoid.<>
  foldMap1 f (Many a as) = f a Se.<> foldMap1 f as

instance Traversable NonEmpty where
  traverse inj (One a) = One <$> inj a
  traverse inj (Many a as) = Many <$> inj a <*> traverse inj as

instance Traversable1 NonEmpty where
  traverse1 inj (One a) = One <$> inj a
  traverse1 inj (Many a as) = Many <$> inj a <.> traverse1 inj as