這個功能可以用Haskell的類型系統實現嗎？

Question

在Scala中，集合的高階操作總是返回上下文中最好的類型。例如，在BitSet的情況下，如果您將整數映射爲整數，您將得到BitSet，但是如果將整數映射到字符串，則會得到一個通用的Set。同樣，如果你的map a Map具有產生一對的函數，那麼你得到Map作爲回報。否則你會得到一個簡單的Iterable。 map的結果的靜態類型和運行時表示都依賴於傳遞給它的函數的結果類型。

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) 

是否有可能在Haskell的類型系統中實現相同的功能？如果是，如何？上述代碼片段中的示例的Haskell翻譯將不勝感激。 :-)

Answer 1

我不認爲你的第一個例子是非常Haskell-y，因爲你重載了相同的名字來做兩件完全不同的事情。在Haskell中，當你通過某個容器映射一個函數時，你希望得到相同的容器類型。事實上，這在Haskell中非常普遍，以至於有一個類型類Functor它封裝了這個模式。

Haskell中的所有重載形式歸結爲使用類型類，雖然可以使用它們來實現類似的東西，但它會非常有用，並且不會僅僅使用純函數來完成您想要的一件事。

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] 

我覺得你的第二個例子是更相關的哈斯克爾，因爲它更多的是選擇最有效的實現了基於所含類型的數據結構的，我懷疑這不應該是太難用做type families，但我對這些不太熟悉，所以我會讓其他人試着回答這個問題。

Answer 2

我非常贊同哈馬爾，但這裏有一個辦法做到這一點，有點：

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

這是在行動：

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

理想情況下，你會想這樣做：

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

但是這個實例與pair對衝突。所以沒有什麼好辦法給每一個其他類型的實例。

Answer 3

添加到hammar：我認爲第二個例子是不可能的，因爲它存在隱式類型轉換。

忽略了討論的緣故，怎麼可能類型簽名是這樣的：

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

所以，是的，這是可能的，但有一個可能需要指定返回類型的規定。