pieghevole vs Traversable

Question

Mentre studiavo più profondo Applicative sono venuto a Traversable, anche se conoscevo già Foldable da LYHGG, non ho visto il primo ancora, quindi ho iniziato a leggere il Haskell wiki about Traversable.

Durante la lettura ho capito perché Foldable.fold è parallelo a Traversable.sequenceA e Foldable.foldMap è parallelo a Traversable.traverse.

ho visto anche che ogni Traversable è anche un Foldable e un Functor e sequenceA e traversal dispone di un'implementazione di default in termini di vicenda:

traverse f = sequenceA . fmap f 
sequenceA = traverse id 

Quindi, come ho visto in LYHGG che foldMap è una definizione completa minima per Foldable, ho pensato che è parallela a traverse, quindi fold (che è parallela a sequenceA) sarebbe anche una definizione completa minima (che non lo è) ... Foldable non è un Functor come Traversable è, quindi non possiamo applichiamo questo:

foldMap f = fold . fmap f 
fold = foldMap id -- this is ok 

Perché non è ogni Foldable un Functor, e che sarebbe un esempio di Foldable che in realtà non è un Functor?

Answer 1

Come dice Dfeuer, Set è un buon esempio di Foldable che non è un Functor.

considerare il tipo di Set.map:

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

Si noti che questo è quasifmap, ma richiede un ulteriore Ord b vincolo. Poiché si dispone di questo vincolo, non è possibile creare un'istanza di Functor.

Nota che Set non è un functor su Haskell, anche con questa restrizione. Con un'impostazione intelligente delle istanze Eq possiamo infrangere la legge che fmap f . fmap g === fmap (f . g). Vedere questa domanda Stack Overflow per più vari discussione:

Sets, Functors and Eq confusion

Come notato lì, Setè un (endo) funtore sulla "sottocategoria di Hask" con i tipi ordinati come set e con mappe ordine preservando come morfismi.

Quindi, anche se non è evidente, il fatto che non siamo in grado di rendere un Set un functor allude effettivamente a un vero problema matematico e non solo a una limitazione del nostro macchinario di tipografia.