monoid functors haskell ghc functor

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 de Functor para data 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 de functor 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 los Functors tengan instancias de Eq . 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?