Haskell: Un exemple d’un Pliable qui n’est pas un Functor (ou non Traversable)?

Voici un exemple entièrement paramésortingque:

 data Weird a = Weird a (a -> a) instance Foldable Weird where foldMap f (Weird ab) = f $ ba 

Weird n’est pas un Functor car a se produit dans une position négative.

Voici un exemple simple: Data.Set.Set . Voir par vous-même.

La raison en est évidente si vous examinez les types de fonctions de fold et de map spécialisées définies pour Set :

 foldr :: (a -> b -> b) -> b -> Set a -> b map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b 

La structure de données reposant sur une arborescence de recherche binary en interne, une contrainte Ord est requirejse pour les éléments. Functor instances de Functor doivent autoriser n’importe quel type d’élément, donc ce n’est pas viable, hélas.

Le pliage, par contre, détruit toujours l’arbre pour produire la valeur de résumé, il n’est donc pas nécessaire de sortinger les résultats intermédiaires du pli. Même si le pli est en train de construire un nouvel Set , la responsabilité de satisfaire la contrainte Ord réside dans la fonction d’accumulation transmise au pli et non dans le pli lui-même.

La même chose s’appliquera probablement à tout type de conteneur qui n’est pas entièrement paramésortingque. Et compte tenu de l’utilité de Data.Set , cela rend la remarque que vous avez citée à propos de “intéressant” Foldable semble un peu suspect, je pense!

Lecture Beau pliage Je me suis rendu compte que tout Foldable peut être transformé en Functor en l’ Functor dans

 data Store fab = Store (fa) (a -> b) 

avec un simple constructeur intelligent:

 store :: fa -> Store faa store x = Store x id 

(Ceci est juste une variante du type de données Store comonad.)

Maintenant, nous pouvons définir

 instance Functor (Store fa) where fmap f (Store xg) = Store x (f . g) instance (F.Foldable f) => F.Foldable (Store fa) where foldr fz (Store xg) = F.foldr (f . g) zx 

De cette façon, nous pouvons créer à la fois un foncteur Data.Set.Set et Sjoerd Visscher. (Cependant, comme la structure ne mémorise pas ses valeurs, le repli à plusieurs resockets peut être très inefficace si la fonction utilisée dans fmap est complexe.)

Mise à jour: Ceci fournit également un exemple d’une structure qui est un foncteur, pliable mais non traversable. Pour rendre Store traversable, nous devrons rendre (->) r traversable. Donc, nous devrions mettre en œuvre

 sequenceA :: Applicative f => (r -> (fa)) -> f (r -> a) 

Prenons E Either b pour f . Ensuite, il faudrait mettre en œuvre

 sequenceA' :: (r -> Either ba) -> Either b (r -> a) 

Clairement, il n’y a pas une telle fonction (vous pouvez vérifier avec Djinn ). Nous ne pouvons donc pas non plus réaliser de sequenceA .