functors - haskell applicative
¿Las instancias de Functor son únicas? (2)
"¿Cuándo puede GHC derivar una instancia de funtor y cuándo no?"
Cuando tengamos estructuras circulares de datos intencionales. El sistema de tipos no nos permite expresar nuestra intención de una circularidad forzada. Entonces, ghc puede derivar una instancia, similar a la que queremos, pero no es lo mismo.
Las estructuras de datos circulares son probablemente el único caso en el que el Functor debe implementarse de una manera diferente. Pero, de nuevo, tendría la misma semántica.
data HalfEdge a = HalfEdge { label :: a , companion :: HalfEdge a }
instance Functor HalfEdge where
fmap f (HalfEdge a (HalfEdge b _)) = fix $ HalfEdge (f a) . HalfEdge (f b)
EDITAR:
Los HalfEdges son estructuras (conocidas en gráficos de computadora, mallas 3d ...) que representan bordes no dirigidos en un gráfico, donde puede tener una referencia a cualquiera de los extremos. Por lo general, almacenan más referencias a HalfEdges vecinos, nodos y caras.
newEdge :: a -> a -> HalfEdge a
newEdge a b = fix $ HalfEdge a . HalfEdge b
Semánticamente, no hay fix $ HalfEdge 0 . HalfEdge 1 . HalfEdge 2
fix $ HalfEdge 0 . HalfEdge 1 . HalfEdge 2
fix $ HalfEdge 0 . HalfEdge 1 . HalfEdge 2
, porque los bordes siempre se componen de exactamente dos medios bordes .
EDIT 2:
En la comunidad de haskell, la cita "Atar el nudo" es conocida por este tipo de estructura de datos. Se trata de estructuras de datos que son semánticamente infinitas porque circulan. Sólo consumen memoria finita. Ejemplo: dados ones = 1:ones
, tendremos estas implementaciones semánticamente equivalentes de twos
:
twos = fmap (+1) ones
twos = fix ((+1)(head ones) :)
Si recorremos (primero n elementos de) twos
y todavía tenemos una referencia al comienzo de esa lista, estas implementaciones difieren en velocidad (evalúe 1 + 1 cada vez contra una sola vez) y consumo de memoria (O (n) vs O (1 )).
Me preguntaba hasta qué punto las instancias de Functor
en Haskell están determinadas (únicamente) por las leyes de funtor.
Dado que ghc
puede derivar instancias de Functor
para al menos los tipos de datos "comunes", parece que deben ser únicos al menos en una amplia variedad de casos.
Por conveniencia, la definición de Functor
y las leyes del funtor son:
class Functor f where
fmap :: (a -> b) -> f a -> f b
fmap id = id
fmap (g . h) = (fmap g) . (fmap h)
Preguntas:
¿Se puede derivar la definición de
map
partiendo del supuesto de que es una instancia deFunctor
paradata List a = Nil | Cons a (List a)
data List a = Nil | Cons a (List a)
? Si es así, ¿qué suposiciones deben hacerse para hacer esto?¿Hay algún tipo de datos de Haskell que tenga más de una instancia de
Functor
que cumpla con las leyes de este?¿Cuándo puede
ghc
obtener una instancia defunctor
y cuándo no?¿Todo esto depende de cómo definamos la igualdad? Las leyes de
Functor
se expresan en términos de igualdad de valores, pero no requerimos que losFunctors
tengan instancias deEq
. Entonces, ¿hay alguna opción aquí?
Con respecto a la igualdad, ciertamente hay una noción de lo que yo llamo "igualdad de constructor" que nos permite razonar que [a,a,a]
es "igual" a [a,a,a]
para cualquier valor de a
de cualquier tipo, incluso si a
no tiene (==)
definido para ello. Todas las demás nociones (útiles) de igualdad son probablemente más basas que esta relación de equivalencia. Pero sospecho que la igualdad en las leyes de Functor
es más una relación de "igualdad de razonamiento" y puede ser específica de la aplicación. Tiene alguna idea sobre esto?
Ver la Typeclassopedia Brent Yorgey:
A diferencia de otras clases de tipos que encontraremos, un tipo dado tiene a lo sumo una instancia válida de Functor. Esto se puede probar a través del teorema libre para el tipo de fmap. De hecho, GHC puede derivar automáticamente instancias de Functor para muchos tipos de datos.