Haskell: ¿Un ejemplo de un Plegable que no es un Functor(o no Traversable)?

fold traversal

Question

Una instancia Foldable es probable que sea algún tipo de contenedor, y también es probable que sea un Functor . De hecho, this dice

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

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

Answer 1

Aquí hay un ejemplo fácil: Data.Set.Set . Ver por ti mismo.

El motivo de esto debería ser evidente si examina los tipos de funciones especializadas de 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 instancias de Functor deben permitir cualquier tipo de elemento, por lo que no es viable, ¡ay!

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 doblez. Incluso si el pliegue en realidad está construyendo un nuevo Set , la responsabilidad de satisfacer la restricción de Ord recae en la función de acumulación pasada al doblez, no en el doblez mismo.

Lo mismo probablemente se aplicará a cualquier tipo de contenedor que no sea totalmente paramétrico. Y dada la utilidad de Data.Set , ¡esto hace que la observación que citó acerca de las " Foldable " interesantes parezca un poco sospechosa, creo!

Answer 2

Aquí hay un ejemplo totalmente 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.

Answer 3

Reading Beautiful folding 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 simple contructor inteligente:

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 forma, podemos hacer que tanto Data.Set.Set como Sjoerd Visscher''s Weird funcionen. (Sin embargo, dado que la estructura no memoriza sus valores, doblarla repetidamente podría ser muy ineficiente, si la función que usamos en fmap es compleja).

Actualización: Esto también proporciona un ejemplo de una estructura que es un funtor, plegable pero no atravesable. Para hacer que la Store atravesable, necesitaríamos hacer (->) r atravesable. Entonces, 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 (puede verificarlo con Djinn ). Entonces no podemos darnos cuenta de la sequenceA A.