Questa funzionalità può essere implementata con il sistema di tipi Haskell?

Question

In Scala, le operazioni di ordine superiore su collezioni restituiscono sempre il miglior tipo possibile nel contesto. Ad esempio, nel caso di BitSet, se si esegue il mapping int a int si ottiene un BitSet, ma se si esegue il mapping interi in stringhe, si ottiene un generale Set. Allo stesso modo, se un mapMap con una funzione che produce una coppia, allora si ottiene un Map in cambio. Altrimenti ottieni un semplice Iterable. Sia il tipo statico che la rappresentazione runtime del risultato della mappa dipendono dal tipo di risultato della funzione che gli viene passato.

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) 

E 'possibile implementare la stessa funzionalità nel sistema di tipo di Haskell? Se sì, come? Una traduzione Haskell degli esempi nello snippet di codice sopra sarebbe molto apprezzata. :-)

Answer 1

Non credo che il tuo primo esempio è molto Haskell-y, come si sta sovraccaricando lo stesso nome per fare due cose molto diverse. In Haskell, quando si esegue il mapping di una funzione su un contenitore, si prevede di ottenere lo stesso tipo di contenitore. In effetti, in Haskell è così comune che esiste una classe di tipo, Functor che incapsula questo modello.

Tutte le forme di sovraccarico in Haskell si riducono ad usare le classi di tipo, e mentre si potrebbe utilizzare quelli per realizzare qualcosa di simile, sarebbe molto artificiosa e non molto utile nel corso usando solo le funzioni semplici che fare proprio l'unica cosa che si desidera .

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] 

Credo che il tuo secondo esempio è più rilevante per Haskell, come è più circa il selezionamento il più efficiente implementazione di una struttura di dati in base al tipo contenuta, e ho il sospetto questo non dovrebbe essere troppo difficile da fare con type families, ma non ho molta familiarità con quelli, quindi lascerò che qualcun altro cerchi di rispondere a quella parte.

Answer 2

sono molto d'accordo con Hammar, ma ecco un modo per farlo, una sorta di:

{-# 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 

Eccolo in azione:

*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] 

Idealmente che ci si vuole fare questo :

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

Ma questa istanza è in conflitto con quella per coppie. Quindi non c'è un buon modo per dare un'istanza per ogni altro tipo.

Answer 3

Aggiungendo a Hammar: Credo il secondo esempio non è possibile così com'è, perché ci sono conversioni di tipo implicite.

Ignorando che per il bene della discussione, come potrebbe la firma tipo di assomigliare:

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

Quindi, sì, questo è concepibile, ma con la clausola che uno potrebbe essere necessario specificare il tipo di ritorno.