Блог

Главная - Вопросы по программированию - ошибка типа при создании списка из интегрального типа

ошибка типа при создании списка из интегрального типа

#haskell #integer

#haskell #целое

Вопрос:

Я пытаюсь реализовать простую функцию: totient :

 coprime :: Integral a => a -> a -> Bool
coprime a b = gcd a b == 1

totient :: Integral a => a -> a
totient m = length $ filter (coprime m) [1..m-1]

ghci> :load 99problems.hs
[1 of 1] Compiling Main             ( 99problems.hs, interpreted )

99problems.hs:250:13: error:
    • Couldn't match expected type ‘a’ with actual type ‘Int’
      ‘a’ is a rigid type variable bound by
        the type signature for:
          totient :: forall a. Integral a => a -> a
        at 99problems.hs:249:12
    • In the expression: length $ filter (coprime m) [1 .. m - 1]
      In an equation for ‘totient’:
          totient m = length $ filter (coprime m) [1 .. m - 1]
    • Relevant bindings include
        m :: a (bound at 99problems.hs:250:9)
        totient :: a -> a (bound at 99problems.hs:250:1)
Failed, modules loaded: none.

Я пытался использовать такие вещи, как fromIntegral или toInteger на (m-1) , но ничего из этого не сработало. Я не уверен, чего мне здесь не хватает … кажется, что Int должен быть тип Integral a => a . Что происходит не так?

Комментарии:

1. тип length является length :: Foldable t => t a -> Int . Но вы явно говорите, что это totient должно возвращать Integral a .

2. Как объясняется в ответе, fromIntegral (Num b, Integral a) => A -> b означает, что вызывающий ( length функция) должен предоставить ему любой Integral a . Int является Integral , так что это проверяется. Затем fromIntegral возвращает Num b , и пользователь ( totient функция) выбирает тип этого. В этом случае вы выбираете, чтобы это было Integral в вашем объявлении типа.

3. Обратите внимание, что когда вы «выбираете» возвращаемый тип, вам не нужно его ограничивать, в этом случае вы могли бы вернуть Num b , и он все равно был бы действительным.

4. Вы также могли бы исправить это, используя genericLength (from Data.List ) вместо length . Может быть довольно раздражающим, что length является мономорфным по возвращаемому типу, это похоже на ошибку в первоначальном дизайне стандартной библиотеки, которая, мы можем надеяться, будет изменена в будущей версии.

5. Но fromIntegral возвращает общий Num тип, а затем вы выбираете, каким вы хотите, чтобы это было. Вы можете оставить как есть, или вы можете «преобразовать это» в Integral , как вы делаете

Ответ №1:

Тип Integral a => a -> a гласит:

  1. Вызывающий получает возможность выбрать тип a .
  2. Вызывающий должен доказать, что a является экземпляром Integral .
  3. Вызывающий должен предоставить значение типа a .
  4. Разработчик выдает другое значение типа a .

Однако в этом случае разработчик выдал Int . Каждый раз, когда вызывающий объект выбирает a экземпляр, Integral которым не является Int , это не будет соответствовать типу вызывающего объекта.