Kontekst ograniczającą w Traversable1

Question

W semigroupoids opakowaniu znalazłem następującą definicję:

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 

Dlaczego kontekst granic ustawiony Apply (AN Applicative bez pure), a nie do Functor? Oczywiście musisz nadpisać jedną z definicji, więc jest to niemożliwe z "po prostu" Functor?

Answer 1

To tylko nieznacznie zaostrzona definicja Traversable --- wszystkie są s są Traversable, ale nie odwrotnie. Dla wielu (wielu) więcej szczegółów na temat tego, dlaczego Traversable s potrzebują s, warto spojrzeć na Applicative Programming with Effects być może. Gesturalnie, gdybyś miał tylko Functor, nie byłoby możliwe "sekwencyjne" działanie tego funktora, gdyby zawierał wiele wartości, ponieważ twoja funkcja "iniekcji" (a -> f b) jest jedynym sposobem uzyskania s i nie możesz join warstwy twojego f.

Ale ogólnie, podczas definiowania Traversable s trzeba tylko użyć funkcji wtrysku Effect-Free, pure, dla wartości „default”, który właśnie Traversable1 eliminuje. Dlatego NonEmpty jest instancją, ale nie jest to [].

Żeby beton, należy rozważyć następujące przykładowych dla funktora tożsamości, Maybe, NonEmpty list i regularne [].

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) 

Musimy tylko instancję Functor tutaj właśnie dlatego Id ma tylko jeden element, a nie „default” branch-to dość trywialne.

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

Musimy pure dla "default" Nothing przypadek Maybe (która jest tylko nieco bardziej skomplikowane niż Id).

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

instance Traversable1 Maybe nie może istnieć, ponieważ Maybe ma domyślny oddział; widzimy to, ponieważ nie możemy użyć pure, jeśli mamy tylko ograniczenie 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) 

a ponieważ mamy tylko używane (<*>) a nie pure, możemy zrobić to instancja 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) 

ale to nie działa dla [] ponieważ kończy się przy użyciu pure dla „default” oddział

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

---

Edytuj: Początkowo grałem szybko i swobodnie z moją definicją Traversable1 NonEmpty. Obecna wersja faktycznie działa, ale jest o wiele trudniejsza dla oczu.Poprzednio próbowałem traversing wewnętrznej listy, która działa w duchu, ponieważ [] w drugim gnieździe NonEmpty ma pierwsze gniazdo, aby mu w tym pomóc, ale to nie może działać bezpośrednio, ponieważ lista wewnętrzna ma pustą obudowę [], która potrzebuje pure. Zamiast tego, musimy unikać tego pustego przypadku przez "kradzież" zawsze istniejącego a w pierwszym położeniu, a następnie zastąpienie go po przejściu.

Metoda (oraz definicja typu danych) jest bardzo podobna do wersji stosowanych w półgrup i Semigroupoids bibliotek siebie i są użyteczne, ponieważ mogą one skorzystać z rozpędu biblioteki za regularne [], ale jeśli trochę określić NonEmpty inaczej możemy zobacz, że istnieje wiele paralelizmu między Traversable i Traversable1. Fakt, że instancja Traversable1 może istnieć, jest rzeczywiście cechą samego typu danych - definicje są zasadniczo identyczne.

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