この機能をHaskellのタイプシステムで実装できますか？

Question

Scalaでは、コレクションの上位演算は常にコンテキスト内で可能な限り最良の型を返します。たとえば、BitSetの場合、intをintにマップするとBitSetが得られますが、intを文字列にマップすると、一般的なSetが得られます。同様に、mapMapのペアを生成する関数では、Mapが返されます。それ以外の場合は、簡単なIterableを取得します。静的型とマップの結果のランタイム表現はどちらも、渡された関数の結果の型に依存します。

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で翻訳していただければ幸いです。 :-)

Answer 1

私はあなたの最初の例は非常に2つの非常に異なることを行うために同じ名前をオーバーロードしているので、非常にハスケルだとは思わない。 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のより関連性があると思うし、私は、これは使用して行うにはあまりにも難しいことではありません疑いますtype familiesしかし、私はあまりにもそれらに精通していないので、私は他の誰かがその部分に答えてみましょう。

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 

しかし、そのインスタンスはペアのインスタンスと競合します。だから、他のすべてのタイプのインスタンスを与える良い方法はありません。

Answer 3

hammarに追加：暗黙の型変換があるので、2番目の例はそのままでは不可能だと思います。議論のために、どのように型シグネチャは次のようになりうることを無視し

：だから

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

は、はい、これは考えられる、まだ1は、戻り値の型を指定する必要があり条項です。