可以使用Haskell的类型系统实现此功能吗？

Question

在Scala中,集合上的高阶操作始终在上下文中返回最佳类型.例如,BitSet如果你将int映射到int,你会得到一个BitSet,但是如果你将int映射到字符串,你会得到一个通用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转换将非常受欢迎.:-)

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]

我认为你的第二个例子与Haskell更相关,因为它更多的是基于所包含的类型选择最有效的数据结构实现,我怀疑使用类型族不应该太难,但我是不太熟悉那些,所以我会让别人试着回答那个部分.

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

但是这个实例与成对的实例冲突.因此没有好的方法为每个其他类型提供一个实例.