这个功能可以用Haskell的类型系统实现吗？

问题描述：

在Scala中，集合的高阶操作总是返回上下文中最好的类型。例如，在BitSet的情况下，如果您将整数映射为整数，您将得到BitSet，但是如果将整数映射到字符串，则会得到一个通用的Set。同样，如果你的map a Map具有产生一对的函数，那么你得到Map作为回报。否则你会得到一个简单的Iterable。 map的结果的静态类型和运行时表示都依赖于传递给它的函数的结果类型。这个功能可以用Haskell的类型系统实现吗？

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翻译将不胜感激。 :-)

答

我不认为你的第一个例子是非常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，但我对这些不太熟悉，所以我会让其他人试着回答这个问题。

答

我非常赞同哈马尔，但这里有一个办法做到这一点，有点：

{-# 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对冲突。所以没有什么好办法给每一个其他类型的实例。

答

添加到hammar：我认为第二个例子是不可能的，因为它存在隐式类型转换。

忽略了讨论的缘故，怎么可能类型签名是这样的：

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

所以，是的，这是可能的，但有一个可能需要指定返回类型的规定。

这个功能可以用Haskell的类型系统实现吗？

相关推荐