Может ли эта функциональность быть реализована с помощью системы типов Haskell? - PullRequest
Новая
       50

Может ли эта функциональность быть реализована с помощью системы типов Haskell?

18 голосов
/ 09 октября 2011

В Scala операции высшего порядка над коллекциями всегда возвращают наилучший возможный тип в контексте. Например, в случае BitSet, если вы отображаете целые числа в целые, вы получаете BitSet, но если вы отображаете целые числа в строки, вы получаете общее Set. Точно так же, если вы map a Map с функцией, которая выдает пару, то вы получите 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 примеров в приведенном выше фрагменте кода был бы очень признателен. : -)

Ответы [ 3 ]

11 голосов
/ 09 октября 2011

Я не думаю, что ваш первый пример - очень 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, так как он больше касается выбора наиболее эффективной реализации структуры данных на основе содержимого типа, и я подозреваю, что это не должно быть слишком сложно сделать с использованием типа семьи , но я не слишком знаком с ними, поэтому я позволю кому-то другому попытаться ответить на эту часть.

7 голосов
/ 09 октября 2011

Я очень согласен с 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

Но этот экземпляр конфликтует с экземпляром для пар.Так что нет хорошего способа дать экземпляр для любого другого типа.

1 голос
/ 09 октября 2011

Добавление к Hammar: я думаю, что второй пример невозможен в его нынешнем виде, потому что существуют неявные преобразования типов.

Игнорирование этого ради обсуждения, как может выглядеть подпись типа:1003 * 

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

Итак, да, это возможно, но при условии, что может потребоваться указать тип возвращаемого значения.

...