Haskell: ¿Un ejemplo de un Plegable que no es un Functor(o no Traversable)?
fold traversal (3)
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!
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écnicamenteFunctor
, losFoldable
interesantes son todos losFunctor
).
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ó :-))
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.
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.