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(Applicative没有pure)而不是Functor？显然你需要覆盖其中一个定义,所以这只是"只"一个不可能Functor吗？

Answer 1

这只是一个略微收紧的定义Traversable- 所有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

我们需要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