Haskell: Un exemple de Foldable qui n'est pas un Functor (ou qui n'est pas Traversable)?

Question

Un Foldable instance est susceptible d'être une sorte de conteneur, et est donc susceptible d'être un Functor ainsi. En effet, cela dit

Un Foldable type est également un conteneur (même si la classe n'a techniquement pas besoin Functor, intéressant Foldables sont tous Functors).

Donc, il y a un exemple d' Foldable ce qui n'est pas naturellement un Functor ou Traversable? (qui est peut-être le Haskell page wiki raté :-) )

Answer 1

Voici un exemple entièrement paramétrique:

 data Iter a = Iter (a -> a) a Int

instance Foldable Iter where
  foldMap f (Iter g a i) = f $ iterate g a !! i
 

Iter n'est pas un Functor car a se trouve dans une position négative.

Edit : Cet exemple est un peu plus intéressant.

Answer 2

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

La raison pour cela devrait être évident si vous examinez les types d'spécialisées fold et map fonctions définies pour l' Set:

foldr :: (a -> b -> b) -> b -> Set a -> b

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

Parce que la structure de données repose sur un arbre de recherche binaire en interne, une Ord contrainte est nécessaire pour les éléments. Functor instances doivent permettre à tout type d'élément, ce qui n'est pas viable, hélas.

Le pliage, d'autre part, toujours détruit l'arbre à produire de la valeur de résumé, il n'est donc pas nécessaire de trier les résultats intermédiaires de la pliure. Même si le pli est en fait la construction d'un nouveau Set, la responsabilité de satisfaire l' Ord contrainte se trouve sur la fonction d'accumulation passé à la fois, ne pas le plier lui-même.

La même chose va probablement s'appliquer à tout type de conteneur qui n'est pas entièrement paramétrique. Et compte tenu de l'utilité de l' Data.Set, ce qui rend la remarque que vous avez cité à propos de "intéressant" Foldables semble un peu suspect, je pense!

Answer 3

La lecture de Belle pliage J'ai réalisé que tout Foldable peut être fait une Functor en l'enveloppant dans

data Store f a b = Store (f a) (a -> b)

avec un simple smart constructeur:

store :: f a -> Store f a a
store x = Store x id

(C'est juste une variante de la Boutique comonad type de données.)

Nous pouvons maintenant définir

instance Functor (Store f a) where
    fmap f (Store x g)   = Store x (f . g)

instance (F.Foldable f) => F.Foldable (Store f a) where
    foldr f z (Store x g)    = F.foldr (f . g) z x

De cette façon, nous pouvons faire les deux Data.Set.Set et Sjoerd Visscher l' Iter un foncteur. (Cependant, puisque la structure n'est pas memoize à ses valeurs, à plusieurs reprises, se repliant sur elle pourrait être très inefficace, si la fonction que nous avons utilisé, en fmap est complexe.)

---

Mise à jour: il fournit également un exemple d'une structure qui est un foncteur, pliable, mais pas traversable. Pour faire Store traversable, nous aurions besoin de prendre (->) r traversable. Nous avions donc besoin de mettre en œuvre

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

Prenons Either b pour f. Alors que nous aurions besoin pour mettre en œuvre

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

Clairement, il n'y a pas une telle fonction (vous pouvez vérifier avec Djinn). Donc, nous ne pouvons ni nous réalisons sequenceA.