Traversable1中的上下文界限

Question

在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 (不带pure的Applicative )而不是Functor？显然，您需要覆盖其中的一个定义，所以这对于“仅仅”一个Functor是不可能的吗

Answer 1

这只是对签证的稍微严格的定义-所有的Traversable1都是Traversable，但不是相反。有关Traversable为什么需要Applicatives的更多详细信息，也许值得一看Applicative Programming with Effects。从手势上讲，如果你只有一个Functor，那么如果它包含很多值，就不可能对该函数的效果进行“排序”，因为“注入”函数(a -> f b)是获得bs的唯一方法，并且你不能join你的f的层。

但是，从广义上讲，当您定义Traversables时，您只需要对“默认”值使用无影响的注入函数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

对于Maybe的“默认”Nothing情况，我们需要pure (它只比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，然后在遍历之后替换它来避免那个空案例。

这种方法(和数据类型定义)与半组和半群集库本身使用的版本非常相似，并且非常有用，因为它们可以利用常规[]背后的库动力，但如果我们对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