haskell - uber - cuanto cobran por hacer una app

¿Existen aplicaciones útiles para la Clase de Tipo Divisible?

Question

Últimamente he estado trabajando en una API en Elm, donde uno de los tipos principales es contravariante. Entonces, busqué en Google para ver qué se puede hacer con tipos contravariantes y encontré que el paquete Contravariant en Haskell define la clase de tipo Divisible .

Se define de la siguiente manera:

class Contravariant f => Divisible f where
divide :: (a -> (b, c)) -> f b -> f c -> f a
conquer :: f a 

Resulta que mi tipo particular se ajusta a la definición de clase de tipo Divisible. Aunque Elm no admite clases de tipo, sí miro a Haskell de vez en cuando en busca de inspiración.

Mi pregunta: ¿hay algún uso práctico para esta clase de tipo? ¿Hay API conocidas en Haskell (u otros idiomas) que se benefician de este patrón de divide y vencerás? ¿Hay algún problema que deba tener en cuenta?

Muchas gracias por su ayuda.

Answer 1

Aquí hay un posible caso de uso.

En las bibliotecas de transmisión, uno puede tener construcciones plegables como las del paquete foldl , que se alimentan con una secuencia de entradas y devuelven un valor de resumen cuando se agota la secuencia.

Estos pliegues son contravariantes en sus entradas, y pueden hacerse Divisible . Esto significa que si tiene un flujo de elementos donde cada elemento puede descomponerse en partes b y c , y también tiene un pliegue que consume b s y otro pliegue que consume c s, entonces puede construir un pliegue que consume la secuencia original

Los pliegues reales de foldl no implementan Divisible , pero podrían hacerlo, utilizando un envoltorio newtype. En mi paquete de process-streaming tengo un tipo de plegado que implementa Divisible .

divide requiere que los valores de retorno de los pliegues constituyentes sean del mismo tipo, y ese tipo debe ser una instancia de Monoid . Si los pliegues devuelven diferentes monoides no relacionados, una solución alternativa es poner cada valor de retorno en un campo separado de una tupla, dejando el otro campo como mempty . Esto funciona porque una tupla de monoides es en sí misma un Monoid .

Answer 2

Examinaré el ejemplo de los tipos de datos centrales en las técnicas de clasificación de radix generalizadas de Fritz Henglein, tal como lo implementó Edward Kmett en el paquete de discriminación .

Si bien hay muchas cosas sucediendo allí, se centra en gran medida en un tipo como este

data Group a = Group (forall b . [(a, b)] -> [[b]])

Si tiene un valor de tipo Group a , esencialmente debe tener una relación de equivalencia en a porque si le doy una asociación entre a s y algún tipo b completamente desconocido para usted, entonces puede darme "agrupaciones" de b .

groupId :: Group a -> [a] -> [[a]]
groupId (Group grouper) = grouper . map (/a -> (a, a))

Puede ver esto como un tipo central para escribir una biblioteca de grupos de utilidad. Por ejemplo, podemos querer saber que si podemos Group a y Group b entonces podemos Group (a, b) (más sobre esto en un segundo). La idea principal de Henglein es que si puede comenzar con algunos Group s básicos en enteros (podemos escribir implementaciones de Group Int32 muy rápidas mediante radix sort) y luego usar combinators para extenderlos sobre todos los tipos, entonces habrá radix generalizado para tipos de datos algebraicos .

Entonces, ¿cómo podríamos construir nuestra biblioteca de combinador?

Bueno, f :: Group a -> Group b -> Group (a, b) es muy importante ya que nos permite crear grupos de tipos similares a los productos. Normalmente, obtendríamos esto de Applicative y de liftA2 pero Group , como notará, es Contravaiant , no Functor .

Entonces, en su lugar usamos Divisible

divided :: Group a -> Group b -> Group (a, b)

Tenga en cuenta que esto surge de una manera extraña desde

divide :: (a -> (b, c)) -> Group b -> Group c -> Group a

ya que tiene el típico carácter de "flecha invertida" de cosas contravariantes. Ahora podemos entender cosas como divide y conquer en términos de su interpretación en Group .

Divide dice que si quiero construir una estrategia para equiparar a s usando estrategias para equiparar b s y c s, puedo hacer lo siguiente para cualquier tipo x

1. Tome su relación parcial [(a, x)] y trace un mapa sobre ella con una función f :: a -> (b, c) , y una pequeña manipulación de tuplas, para obtener una nueva relación [(b, (c, x))] .

2. Usa mi Group b para discriminar [(b, (c, x))] a [[(c, x)]]

3. Usa mi Group c para discriminar cada [(c, x)] a [[x]] dándome [[[x]]]

4. Aplanar las capas internas para obtener [[x]] como necesitamos

   instance Divisible Group where
   conquer = Group $ return . fmap snd
   divide k (Group l) (Group r) = Group $ /xs ->
   -- a bit more cleverly done here...
   l [ (b, (c, d)) | (a,d) <- xs, let (b, c) = k a] >>= r

También obtenemos interpretaciones del refinamiento Decidable más difícil de Divisible

class Divisible f => Decidable f where
lose :: (a -> Void) -> f a
choose :: (a -> Either b c) -> f b -> f c -> f a
instance Decidable Group where
lose :: (a -> Void) -> Group a
choose :: (a -> Either b c) -> Group b -> Group c -> Group a

Dicen que para cualquier tipo a de los cuales podemos garantizar que no hay valores (no podemos producir valores de Void de ninguna manera, una función a -> Void es un medio de producir Void dado a , por lo que no debemos poder para producir valores de a por cualquier medio!) entonces inmediatamente obtenemos una agrupación de valores cero

lose _ = Group (/_ -> [])

También podemos ir a un juego similar al de arriba, pero en lugar de secuenciar nuestro uso de los discriminadores de entrada, alternamos.

Usando estas técnicas construimos una biblioteca de cosas " Group ", a saber, Grouping

class Grouping a where
grouping :: Group a

y tenga en cuenta que casi todas las definiciones surgen de la definición básica encima de groupingNat que utiliza manipulaciones vectoriales monádicas rápidas para lograr una ordenación de radix eficiente.

Answer 3

Un ejemplo:

Aplicativo es útil para el análisis sintáctico, porque puede convertir los analizadores sintácticos de las partes en un analizador sintáctico de totalidades, necesitando solo una función pura para combinar las partes en un todo.

Divisible es útil para la serialización (¿deberíamos llamar a esto coparsing ahora?), Porque puede convertir serializadores Divisibles de partes en un serializador de totalidades, necesitando solo una función pura para dividir el todo en partes.

De hecho, no he visto un proyecto que funcionara de esta manera, pero estoy trabajando (lentamente) en una implementación de Avro para Haskell.

Cuando me topé con Divisible por primera vez, lo quería divide , y no tenía idea de qué uso posible conquer podría ser otro que hacer trampa (un fa de la nada, para cualquier a ?). Pero para hacer que las leyes Divisibles revisen mis serializadores, conquer convirtió en un "serializador" que codifica cualquier cosa en cero bytes, lo que tiene mucho sentido.