7

In semigroupoids package I found the following definition:

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

Why are the context bounds set to Apply (an Applicative without pure) and not to Functor? Obviously you need to overwrite one of the definitions, so is this impossible with "just" a Functor?

4

1 回答 1

6

这只是对 a Traversable---all Traversable1s are的稍微严格的定义Traversable，但反之亦然。对于为什么Traversables 需要Applicatives 的许多（许多）更多细节，也许值得一看Applicative Programming with Effects。从手势上看，如果你只有 a ，那么如果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情况。MaybeId

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所以不能直接工作。相反，我们必须通过“窃取”第一个位置的始终存在并在遍历后替换它来避免这种空情况。[]purea

该方法（和数据类型定义）与 Semigroups 和 Semigroupoids 库本身中使用的版本非常相似，并且很有用，因为它们可以利用 regular 背后的库动力[]，但如果我们定义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
于 2013-05-11T18:16:33.493 回答