这个功能能否使用Haskell的类型系统来实现？

Question

在Scala中，集合上的高阶操作总是返回上下文中最佳的可能类型。例如，在BitSet的情况下，如果您将整数映射到整数，则会得到一个BitSet，但如果您将整数映射到字符串，则会得到一个通用的Set。同样地，如果您使用生成对的函数map一个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。

- missingfaktor

Answer 1

我认为你的第一个例子不太符合Haskell的风格，因为你重载了同一个名称来做两件非常不同的事情。在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]

我认为你的第二个例子更适用于Haskell，因为它更多地涉及基于包含类型选择最有效实现的数据结构，我怀疑这应该不难使用类型族来实现，但我对此并不太熟悉，所以我会让其他人尝试回答这一部分。

- hammar

Answer 2

我非常同意hammar的观点，但是这里有一种方法可以实现，差不多是这样：

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

但这个实例与成对的实例相冲突。因此，没有好的方法为每种其他类型提供实例。

- Sjoerd Visscher

Answer 3

补充一下hammar的观点：我认为第二个例子不可能按原样实现，因为存在隐式类型转换。

为了讨论的方便，我们忽略这一点，那么类型签名应该是什么样的：

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

是的，这是可以想象的，但前提是可能需要指定返回类型。

- Ingo