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

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 mapea ints a ints obtienes un BitSet, pero si mapeas ints a cadenas, obtienes un Set general. Del mismo modo, si map a 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

No creo que su primer ejemplo sea muy Haskell-y, ya que está sobrecargando el mismo nombre para hacer dos cosas muy diferentes. En Haskell, cuando mapea una función sobre un contenedor, espera obtener 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 utilizar clases de tipo, y aunque podría usarlas para lograr algo similar, sería muy artificial y no muy útil sobre simplemente usar funciones simples que hacen exactamente lo que usted quiere .

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 es más acerca de escoger la implementación más eficiente de una estructura de datos en función del tipo contenida, y sospecho que esto no debería ser demasiado difícil de hacer uso de type families, pero no estoy muy familiarizado con ellos, entonces dejaré que otra persona intente responder esa parte.

Answer 2

Estoy muy de acuerdo con Hammar, pero aquí es una manera de hacerlo, más o menos:

{-# 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 que te gustarí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 los pares. Entonces, no hay una buena manera de dar una instancia para cada otro tipo.

Answer 3

Agregando a hammar: Creo que el segundo ejemplo no es posible tal como está, porque hay conversiones de tipo implícitas.

Haciendo caso omiso de que por el bien de la discusión, ¿cómo se ve el tipo de firma como:

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

Así que, sí, esto es concebible, sin embargo, con la condición de que uno puede tener que especificar el tipo de retorno.