Почему вывод типа терпит неудачу для полиморфной функции, примененной к различным входам с одной и той же функцией - PullRequest
Новая
       8

Почему вывод типа терпит неудачу для полиморфной функции, примененной к различным входам с одной и той же функцией

0 голосов
/ 05 июня 2018

Я делаю переводчик для подмножества C ++.Интерпретатор написан на языке Haskell.

Моя eval функция для выражений возвращает новое окружение и значение.Я кодирую значения как новый тип с именем Val.Минимальный пример: 

data Val = I Integer | D Double

Чтобы оценить арифметические выражения, я хочу создать общую функцию, которая применяет полиморфную функцию, такую ​​как (+) или (*), к числам, заключенным в конструкторы Val.

Я хочу иметь функцию, подобную этой: 

-- calculate :: Num a => (a -> a -> a) -> Val -> Val -> Val
calculate f (I i1) (I i2) = I (f i1 i2)
calculate f (D d1) (D d2) = D (f d1 d2)

Это дает следующую ошибку: 

tmp/example.hs:4:32: error:
    • Couldn't match expected type ‘Double’ with actual type ‘Integer’
    • In the first argument of ‘D’, namely ‘(f d1 d2)’
      In the expression: D (f d1 d2)
      In an equation for ‘calculate’:
          calculate f (D d1) (D d2) = D (f d1 d2)
  |
4 | calculate f (D d1) (D d2) = D (f d1 d2)
  |                                ^^^^^^^

tmp/example.hs:4:34: error:
    • Couldn't match expected type ‘Integer’ with actual type ‘Double’
    • In the first argument of ‘f’, namely ‘d1’
      In the first argument of ‘D’, namely ‘(f d1 d2)’
      In the expression: D (f d1 d2)
  |
4 | calculate f (D d1) (D d2) = D (f d1 d2)
  |                                  ^^

tmp/example.hs:4:37: error:
    • Couldn't match expected type ‘Integer’ with actual type ‘Double’
    • In the second argument of ‘f’, namely ‘d2’
      In the first argument of ‘D’, namely ‘(f d1 d2)’
      In the expression: D (f d1 d2)
  |
4 | calculate f (D d1) (D d2) = D (f d1 d2)
  |                                     ^^

Я не могу обернуть голову вокруг этого.У меня два вопроса:

  1. Почему этой программе не удается проверить тип?
  2. Как я могу правильно реализовать calculate?

Ятолько смутно знакомы с универсально определенными типами, поэтому, если это является частью проблемы, пожалуйста, объясните осторожно.

1 Ответ

0 голосов
/ 05 июня 2018

Вы правильно определили, что вам нужно универсальное количественное определение .Фактически, у вас уже есть универсальное количественное определение - ваша подпись, как и любая полиморфная подпись, в основном является сокращением для 

{-# LANGUAGE ExplicitForall, UnicodeSyntax #-}
calculate :: ∀ a . Num a => (a -> a -> a) -> Val -> Val -> Val

, означающим: всякий раз, когда кто-то хочет использовать эту функцию, он выбирает какой-либо тип для вставки вa аванс.Например, они могут выбрать Int, тогда функция станет специализированной для 

calculate :: (Int -> Int -> Int) -> Val -> Val -> Val

, и тогда она будет использоваться во время выполнения.

Но это бесполезно для вас, потому что вынеобходимо использовать эту функцию для различных числовых типов.Ни одна специализация не охватит их всех.

Решение: отложить выбор типа.Это достигается путем помещения универсального квантора ∀ (вы также можете написать его forall) внутри функции сигнатуры с функцией комбинатора: 

{-# LANGUAGE Rank2Types #-}
calculate :: (∀ a . Num a => a -> a -> a) -> Val -> Val -> Val

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

Т.е. ей необходимо передать дополнительный аргумент функции: «словарь», содержащий класс Numметоды.Базовая реализация, сгенерированная GHC, выглядит примерно так: 

data NumDict a = NumDict {
        addition :: a -> a -> a
      , subtraction :: a -> a -> a
      , multiplication :: a -> a -> a
      , abs :: a -> a
      ...
      }

calculate' :: (∀ a . NumDict a -> a -> a -> a) -> Val -> Val -> Val
calculate' f (I i1) (I i2) = I (f ndict i1 i2)
 where ndict = NumDict ((+) :: Integer -> Integer -> Integer)
                       ((-) :: Integer -> Integer -> Integer)
                       ...
...