Ошибки типа Haskell

Question

Первый день изучения haskell, и, исходя из фона Python, у меня действительно возникают проблемы с отладкой, когда дело доходит до типа;В настоящее время я работаю над простой функцией, чтобы увидеть, является ли число простым;

prime p = if p == 1 then False else if p == 2 then True else if maximum ([if p `mod` x == 0 then x else -1 | x<-[2..(floor(p**0.5))]]) > 0 then False else True

. Это работает, когда у меня есть конкретное число вместо общего P, но независимо от того, что я пытаюсь (и яЯ много пробовал, в том числе просто переходил к различным проблемам) Я всегда получаю какую-то ошибку относительно типа.Для этой текущей итерации я получаю сообщение об ошибке

<interactive>:149:1: error:
* Ambiguous type variable `a0' arising from a use of `prime'
  prevents the constraint `(RealFrac a0)' from being solved.
  Probable fix: use a type annotation to specify what `a0' should be.
  These potential instances exist:
    instance RealFrac Double -- Defined in `GHC.Float'
    instance RealFrac Float -- Defined in `GHC.Float'
    ...plus one instance involving out-of-scope types
    (use -fprint-potential-instances to see them all)
* In the expression: prime 2
  In an equation for `it': it = prime 2

<interactive>:149:7: error:
* Ambiguous type variable `a0' arising from the literal `2'
  prevents the constraint `(Num a0)' from being solved.
  Probable fix: use a type annotation to specify what `a0' should be.
  These potential instances exist:
    instance Num Integer -- Defined in `GHC.Num'
    instance Num Double -- Defined in `GHC.Float'
    instance Num Float -- Defined in `GHC.Float'
    ...plus two others
    ...plus one instance involving out-of-scope types
    (use -fprint-potential-instances to see them all)
* In the first argument of `prime', namely `2'
  In the expression: prime 2
  In an equation for `it': it = prime 2

Если кто-то может, а также отладить эту конкретную программу, подскажите мне, как думать о типах haskell, я был бы невероятнопризнательна.Я пытался взглянуть на learnyouahaskell, но пока мне не повезло, применяя это.

Answer 1

Ваш код может быть упрощен как

prime p = if p == 1 then False else 
          if p == 2 then True else 
          if maximum ([if p `mod` x == 0 then x else -1 | x<-[2..(floor(p**0.5))]]) > 0 
             then False else True
=
prime p = if p == 1 then False else 
          if p == 2 then True else 
          not (maximum [if p `mod` x == 0 then x else -1 | x<-[2..floor(p**0.5)]] > 0 )
=
prime p = not ( p == 1 ) && 
          ( p == 2 ||
            maximum [if p `mod` x == 0 then x else -1 | x<-[2..floor(p**0.5)]] <= 0 )
=
prime p = p /= 1   && 
          ( p == 2 ||
            maximum [if p `mod` x == 0 then x else -1 | x<-[2..floor(p**0.5)]] == -1 )
=~
prime p = p == 2 || p > 2 && null [x | x <- [2..floor(p**0.5)], p `mod` x == 0] 

(убедитесь в правильности каждого преобразования).

Это все равно дает нам ошибку типа, потому что (**) :: Floating a => a -> a -> a и mod :: Integral a => a -> a -> a конфликтуют. Чтобы противостоять этому, просто добавьте туда fromIntegral:

isPrime :: Integral a => a -> Bool
isPrime p = p == 2 || 
            p > 2 && null [x | x <- [2..floor(fromIntegral p**0.5)], p `mod` x == 0] 

и он работает:

~> filter isPrime [1..100]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

Answer 2

Короче говоря : используя mod, floor и (**) все одновременно, вы сильно ограничиваете тип p, и Haskell не может найти числовой набрать для звонка prime.

Основная проблема здесь заключается в итерации вашего списка:

[2..(floor(p**0.5))]

Здесь вы вызываете p ** 0.5, но поскольку (**) имеет тип (**) :: Floating a => a -> a -> a, это означает, что p должен быть экземпляром типа, который экземпляр класса типов Floating, например Float. Я думаю, вы этого не хотите.

Ваш floor :: (RealFrac a, Integral b) => a -> b даже усугубляет ситуацию, поскольку теперь p также должен иметь тип, который является экземпляром класса типов RealFrac.

С другой стороны, вы используете mod :: Integral a => a -> a -> a, так что это означает, что ваш p должен быть Floating, а также Integral, которые скорее два дизъюнктивных набора: хотя, строго говоря, мы можем определить такой тип, довольно странно, что число одновременно равно Integral и Floating в одном и том же типе. Float - это, например, число Floating, но не Integral, а Int - это Integral, но не тип Floating.

Мы должны найти способ ослабить ограничения, наложенные на p. Так как обычно числа, отличные от Integral, вообще не являются простыми числами, нам лучше выбросить floor и (**). Однако оптимизация для итерации до квадратного корня из p является хорошей идеей, но нам нужно будет найти другие средства для обеспечения этого.

Один из способов сделать это - использовать takeWhile :: (a -> Bool) -> [a] -> [a], где мы берем элементы, пока квадрат чисел не станет больше p, поэтому мы можем переписать [2..(floor(p**0.5))] до:

takeWhile (\x -> x * x <= p) [2..]

Мы даже можем работать только с нечетными элементами и 2, записав его как:

takeWhile (\x -> x * x <= p) (2:[3, 5..])

Если мы проверим это с p, например, равным 99, мы получим:

Prelude> takeWhile (\x -> x * x <= 99) (2:[3, 5..])
[2,3,5,7,9]

Если мы подключим это, мы ослабим тип:

prime p = if p == 1 then False else if p == 2 then True else if maximum ([if p `mod` x == 0 then x else -1 | x <- takeWhile (\x -> x * x <= p) (2:[3, 5..])]) > 0 then False else True

мы на самом деле достаточно расслабились:

Prelude> :t prime
prime :: Integral a => a -> Bool

и мы получаем:

Prelude> prime 23
True

Но код очень безобразный и скорее un-Haskell . Прежде всего, вы здесь используете maximum как трюк, чтобы проверить, удовлетворяют ли все элементы предикату. Но нет смысла делать это таким образом: с того момента, как один из элементов делится, мы знаем, что число не простое. Таким образом, мы можем лучше использовать функцию all :: (a -> Bool) -> [a] -> Bool. Кроме того, условия обычно проверяются с помощью сопоставления с шаблоном и защитных элементов, поэтому мы можем записать это как:

prime :: Integral a => a -> Bool
prime n | n < 2 = False
        | otherwise = all ((/=) 0 . mod n) divisors
    where divisors = takeWhile (\x -> x * x <= n) (2:[3, 5..])