Борьба с системой типов Haskell - PullRequest
Новая
       9

Борьба с системой типов Haskell

0 голосов
/ 02 июля 2018

Я пытаюсь выучить некоторый Haskell, выполняя базовые задачи в конкретном случае. Я пытаюсь реализовать некоторую базовую функцию для проверки простоты, но я действительно могу выяснить типы, мой код 

isPrime :: (Num a) => a -> Bool
isPrime n
    | n <= 1 = False
    | otherwise = not $ 0 `elem` map (mod n) [2..m] where m = floor $ sqrt n

Я попытался вместо (Num a) => a использовать разные типы чисел или sqrt с fromIntegral, но я все еще получаю сообщения об ошибках, например: 

*Could not deduce (Floating a) arising from a use of `sqrt'
  from the context: Num a
    bound by the type signature for:
               isPrime :: forall a. Num a => a -> Bool
    at Helpers.hs:5:1-31
  Possible fix:
    add (Floating a) to the context of
      the type signature for:
        isPrime :: forall a. Num a => a -> Bool
* In the second argument of `($)', namely `sqrt n'
  In the expression: floor $ sqrt n
  In an equation for `m': m = floor $ sqrt n
| otherwise = not $ 0 `elem` map (mod n) [2..m] where m = floor $ sqrt n

Я действительно могу использовать некоторую помощь здесь, заранее спасибо.

Ответы [ 3 ]

0 голосов
/ 03 июля 2018

Как уже упоминалось, использование mod требует a, чтобы быть Integral, а использование sqrt требует a, чтобы быть Floating. Судя по названию вашей функции, я предполагаю, что вы хотите использовать ее для целочисленных типов. Таким образом, вы можете исправить это, изменив свою подпись на isPrime :: (Integral a) => a -> Bool, а затем предварительно составив sqrt с fromIntegral. Вы могли бы сделать что-то вроде 

where m = floor . sqrt . fromIntegral $ n

Другим вариантом было бы заменить [1..m] чем-то вроде takeWhile (\x -> x * x <= n) [1..], чтобы избежать необходимости в Floating.

0 голосов
/ 03 июля 2018

Проблема, которую описывает компилятор, заключается в том, что вы применяете несовместимые операции к одному и тому же типу: mod требует Integral a, sqrt требует Floating a, и ни один тип не удовлетворяет обоим. Вы можете обойти это, используя преобразования типов, такие как fromIntegral и ceiling, но вы должны быть осторожны, чтобы избежать ошибок округления. Для теста я удалил ограничение типа и использовал m = ceiling $ sqrt $ fromIntegral n, что привело к выводу типа isPrimeSqrt :: Integral a => a -> Bool.

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

Как оказалось, хотя деление стоит дорого, оно часто дает два результата: частное и остаток. С mod вы ищете последнее, но у нас есть divMod и quotRem, которые производят оба. Так что, возможно, стоит попробовать, если это заметно медленнее, чем простой mod тест ( результаты теста , по сравнению [2..] против [2..m]). 

isPrime n = (n > 1) && null (filter isFactor (takeWhile notTooHigh divisors))
  where notTooHigh (divisor,quotient,_) = divisor <= quotient
        isFactor (_,_,remainder) = remainder == 0
        divisors = [(divisor,quotient,remainder) |
                    divisor <- 2:[3,5..],
                    let (quotient,remainder) = quotRem n divisor]
0 голосов
/ 02 июля 2018

В вашем коде две проблемы:

  1. Несовместимые типы.

Вызов sqrt n и (mod n) требует, чтобы n были одновременно Floating и Integral.

  1. Недостаточный контекст. Требование только (Num a) не разрешает ни одну из операций.

Возможное исправление: а) сузить контекст типа до гораздо более краткого (Integral a); б) добавить fromIntegral к аргументу sqrt: 

isPrime :: Integral a => a -> Bool
isPrime n
    | n <= 1 = False
    | otherwise = not $ 0 `elem` map (mod n) [2..m] where m = floor $ sqrt $fromIntegral n
...