Написание функции, полиморфной в семействе типов - PullRequest
Новая
       32

Написание функции, полиморфной в семействе типов

13 голосов
/ 12 июля 2011

Вчера я экспериментировал с семействами типов и столкнулся с препятствием со следующим кодом: 

  {-# LANGUAGE TypeFamilies #-}

  class C a where
      type A a
      myLength :: A a -> Int

  instance C String where
      type A String = [String]
      myLength = length

  instance C Int where
      type A Int = [Int]
      myLength = length

  main = let a1 = [1,2,3]
             a2 = ["hello","world"]
         in print (myLength a1)
            >> print (myLength a2)

Здесь у меня есть тип, связанный с классом C, и функция, которая вычисляет длину связанного типа. Однако приведенный выше код дает мне эту ошибку: 

 /tmp/type-families.hs:18:30:
     Couldn't match type `A a1' with `[a]'
     In the first argument of `myLength', namely `a1'
     In the first argument of `print', namely `(myLength a1)'
     In the first argument of `(>>)', namely `print (myLength a1)'
 /tmp/type-families.hs:19:30:
     Couldn't match type `A a2' with `[[Char]]'
     In the first argument of `myLength', namely `a2'
     In the first argument of `print', namely `(myLength a2)'
     In the second argument of `(>>)', namely `print (myLength a2)'
 Failed, modules loaded: none.

Если, однако, я изменяю «тип» на «данные», код компилируется и работает: 

  {-# LANGUAGE TypeFamilies #-}

  class C a where
      data A a
      myLength :: A a -> Int

  instance C String where
      data A String = S [String]
      myLength (S a) = length a

  instance C Int where
      data A Int = I [Int]
      myLength (I a) = length a

  main = let a1 = I [1,2,3]
             a2 = S ["hello","world"]
             in
               print (myLength a1) >>
               print (myLength a2)

Почему «длина» не работает так, как ожидалось в первом случае? Строки «type A String ...» и «type A Int ...» указывают, что тип «A a» является списком, поэтому myLength должен иметь следующие типы соответственно: «myLength :: [String] -> Int» или "myLength :: [Int] -> Int".

1 Ответ

14 голосов
/ 12 июля 2011

Hm. Давайте на минутку забудем о типах.

Допустим, у вас есть две функции: 

import qualified Data.IntMap as IM

a :: Int -> Float
a x = fromInteger (x * x) / 2

l :: Int -> String
l x = fromMaybe "" $ IM.lookup x im
  where im = IM.fromList -- etc...

Скажите, что существует какое-то значение n :: Int, которое вас волнует. Учитывая только значение a n, как найти значение l n? Конечно, нет.

Какое это имеет отношение? Ну, тип myLength равен A a -> Int, где A a - результат применения «функции типа» A к некоторому типу a. Однако, myLength, являющийся частью класса типов, параметр класса a используется, чтобы выбрать, какую реализацию myLength использовать. Итак, учитывая значение некоторого определенного типа B, применение к нему myLength дает тип B -> Int, где B ~ A a, и вам нужно знать a, чтобы посмотреть до реализации myLength. Учитывая только значение A a, как найти значение a? Конечно, нет.

Вы могли бы обоснованно возразить, что в вашем коде функция A является обратимой, в отличие от функции a в моем предыдущем примере. Это правда, но компилятор не может ничего с этим поделать из-за предположения open world , где задействованы классы типов; ваш модуль теоретически может быть импортирован другим модулем, который определяет свой собственный экземпляр, например ::

instance C Bool where
    type A Bool = [String]

Глупый? Да. Действительный код? Тоже да.

Во многих случаях использование конструкторов в Haskell служит для создания тривиально инъективных функций : конструктор вводит новую сущность, которая определяется только и уникально с помощью заданных аргументов, упрощая восстановление исходные значения. В этом и заключается разница между двумя версиями вашего кода; семейство данных делает функцию типа обратимой, определяя новый, отдельный тип для каждого аргумента.

...