Haskell: Un ejemplo de un plegable que no es un Funtor (o no Transitable)?

A Foldable instance es probable que sea algún tipo de contenedor, y por lo tanto es probable que sea un Functor también. De hecho, esto dice{[14]]}

Un tipo Foldable es también un contenedor (aunque la clase técnicamente no requiere Functor, Foldable s interesantes son todos Functor s).

Entonces, ¿hay un ejemplo de un Foldable que no es naturalmente un Functor o un Traversable? (que quizás la página wiki de Haskell perdió: -))

Author: Petr Pudlák, 2011-12-02
Source

3 answers

Aquí hay un ejemplo completamente paramétrico: 

data Weird a = Weird a (a -> a)

instance Foldable Weird where
  foldMap f (Weird a b) = f $ b a

Weird no es un Functor porque a ocurre en una posición negativa.

 50
Author: Sjoerd Visscher,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-07-30 14:27:14

Este es un ejemplo sencillo: Data.Set.Set. Compruébelo usted mismo.

La razón de esto debería ser evidente si se examinan los tipos de las funciones especializadas fold y map definidas para Set: 

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

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

Debido a que la estructura de datos se basa en un árbol de búsqueda binario internamente, se necesita una restricción Ord para los elementos. Functor las instancias deben permitir cualquier tipo de elemento, así que eso no es viable, por desgracia.

Plegado, por otro lado, siempre destruye el árbol para producir el valor de resumen, por lo que no hay necesidad de ordenar los resultados intermedios del pliegue. Incluso si el pliegue está realmente construyendo un nuevo Set, la responsabilidad de satisfacer la restricción Ord radica en la función de acumulación pasada al pliegue, no al pliegue en sí.

Lo mismo probablemente se aplicará a cualquier tipo de contenedor que no sea completamente paramétrico. Y dada la utilidad de Data.Set, esto hace que la observación que usted citó sobre" interesante " Foldableparece un poco sospechoso, creo!

 42
Author: C. A. McCann,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-12-02 16:16:23

Leyendo Hermoso plegado Me di cuenta de que cualquier Foldable se puede hacer un Functor envolviéndolo en

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

Con un contructor inteligente simple: 

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

(Esto es solo una variante del tipo de datos comonad Store.)

Ahora podemos definir

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 esta manera, podemos hacer tanto Data.Set.Set como Sjoerd Visscher Weird un funtor. (Sin embargo, dado que la estructura no recuerda sus valores, plegarse repetidamente sobre ella podría ser muy ineficiente, si el la función que usamos en fmap es compleja.)

Update: Esto también proporciona un ejemplo de una estructura que es un funtor, plegable pero no transitable. Para hacer que Store sea transitable, necesitaríamos hacer que (->) r sea transitable. Así que necesitaríamos implementar

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

Tomemos Either b para f. Entonces tendríamos que implementar

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

Claramente, no existe tal función (se puede verificar con Djinn). Así que no podemos darnos cuenta sequenceA.

 22
Author: Petr Pudlák,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-07-30 14:36:55