scala - titulo - ¿Se puede implementar esta funcionalidad con el sistema de tipos de Haskell?

para que sirve la etiqueta title

Question

En Scala, las operaciones de orden superior en las colecciones siempre devuelven el mejor tipo posible en el contexto. Por ejemplo, en el caso de BitSet , si BitSet a BitSet obtiene un BitSet , pero si BitSet a cadenas, obtendrá un Set general. Del mismo modo, si map un Map con una función que produce un par, obtendrá un Map a cambio. De lo contrario obtienes un simple Iterable . Tanto el tipo estático como la representación en tiempo de ejecución del resultado del mapa dependen del tipo de resultado de la función que se le pasa.

scala> Map(2 -> ''a'', 6 -> ''b'') map { case (k, v) => (k + 1, v.toString) }
res0: scala.collection.immutable.Map[Int,java.lang.String] = Map(3 -> a, 7 -> b)

scala> Map(2 -> ''a'', 6 -> ''b'') map { _._1 }
res1: scala.collection.immutable.Iterable[Int] = List(2, 6)

scala> import collection.immutable.BitSet
import collection.immutable.BitSet

scala> BitSet(2, 44, 93).map(1 +)
res3: scala.collection.immutable.BitSet = BitSet(3, 45, 94)

scala> BitSet(2, 44, 93).map(_ + "hola")
res4: scala.collection.immutable.Set[String] = Set(2hola, 44hola, 93hola)

¿Es posible implementar la misma funcionalidad en el sistema de tipos de Haskell? Si es así, ¿cómo? Una traducción de Haskell de los ejemplos en el fragmento de código anterior sería muy apreciada. :-)

Answer 1

Agregando a Hammar: creo que el segundo ejemplo no es posible tal como está, porque hay conversiones de tipos implícitas.

Ignorando eso por el bien de la discusión, ¿cómo podría ser la firma de tipo?

setmap :: (Set a, Set b) => a e -> (e -> f) -> b f 

Entonces, sí, esto es concebible, pero con la disposición de que uno puede necesitar especificar el tipo de retorno.

Answer 2

Estoy muy de acuerdo con Hammar, pero aquí hay una forma de hacerlo:

{-# LANGUAGE MultiParamTypeClasses, TypeFamilies, FlexibleInstances #-}

import Prelude hiding (map)

import qualified Data.Map as M
import qualified Data.IntSet as I
import qualified Data.Set as S

type family Elem c :: *
type instance Elem (M.Map k v) = (k, v)
type instance Elem I.IntSet = Int
type instance Elem (S.Set a) = a

class Map c o where
  type Result c o :: *
  map :: (Elem c -> o) -> c -> Result c o

instance Map I.IntSet Int where
  type Result I.IntSet Int = I.IntSet
  map = I.map

instance Map I.IntSet String where
  type Result I.IntSet String = S.Set String
  map f = S.fromList . fmap f . I.toList

instance (Ord k, Ord k1) => Map (M.Map k v) (k1, v1) where
  type Result (M.Map k v) (k1, v1) = M.Map k1 v1
  map f = M.fromList . fmap f . M.toList

instance (Ord k) => Map (M.Map k v) Int where
  type Result (M.Map k v) Int = [Int]
  map f = fmap f . M.toList

Aquí está en acción:

*Main> map fst (M.fromList [(2::Int, ''a''), (6, ''b'')])
[2,6]
*Main> map (/(k, v) -> (k + 1, show v)) (M.fromList [(2, ''a''), (6, ''b'')])
fromList [(3,"''a''"),(7,"''b''")]
*Main> :t it
it :: M.Map Integer [Char]

Lo ideal sería hacer esto:

instance (Ord k) => Map (M.Map k v) a where
  type Result (M.Map k v) a = [a]
  map f = fmap f . M.toList

Pero esa instancia entra en conflicto con la de las parejas. Así que no hay una buena manera de dar una instancia para cada otro tipo.

Answer 3

No creo que tu primer ejemplo sea muy Haskell-y, ya que estás sobrecargando el mismo nombre para hacer dos cosas muy diferentes. En Haskell, cuando asigna una función a un contenedor, espera recuperar el mismo tipo de contenedor. De hecho, esto es tan común en Haskell que existe una clase de tipo, Functor que encapsula este patrón.

Todas las formas de sobrecarga en Haskell se reducen a usar clases de tipos, y aunque podría usarlas para lograr algo similar, sería muy artificial y no muy útil solo con el uso de funciones simples que hacen lo que usted desea.

Prelude> import qualified Data.Map as M
Prelude Data.Map> let m = M.fromList [(2, ''a''), (6, ''b'')]
Prelude Data.Map> M.map show $ M.mapKeys (+1) m
fromList [(3,"''a''"),(7,"''b''")]
Prelude Data.Map> M.keys m
[2,6]

Creo que su segundo ejemplo es más relevante para Haskell, ya que se trata más de elegir la implementación más eficiente de una estructura de datos basada en el tipo contenido, y sospecho que no debería ser demasiado difícil hacerlo con familias de tipos , pero No estoy demasiado familiarizado con esos, así que dejaré que alguien más intente responder esa parte.