Início / coding / Perguntas / 78378607
Accepted
F. Zer
Asked: 2024-04-24 20:52:25 +0800 CST

As correspondências de padrões não são exaustivas na função `gcd`

  • 772

Para fins de aprendizagem, estou definindo gcd'função em termos de subtração repetida:

gcd' :: Integer -> Integer -> Integer
gcd' x y 
    | x == y = x
    | x < y = gcd' x (y - x)
    | y < x = gcd' (x - y) y

(Função gcd do Prelude )

O problema é que o GHC reclama disso:

As correspondências de padrões não são exaustivas. Em uma equação para 'mdc'':

Padrões do tipo 'Inteiro', 'Inteiro' não correspondidos: _ _

Eu vi uma lei matemática relativa aos números que dizia:

Para todos os números 𝑥 e 𝑦, é verdade que 𝑥 é menor que 𝑦, ou 𝑦 é menor que 𝑥, ou 𝑥 é igual a 𝑦.

Nesse sentido, esses três guardas cobrem todos os cenários possíveis. Porque é que o GHC está preocupado com esta definição?

haskell

2 respostas

  1. Como explicou Willem, isso ocorre porque o GHC não sabe que </ >/ ==são uma coleção exaustiva de possibilidades. Na verdade, ele nunca sabe disso para qualquer verificação com valor booleano.

    Haskell, entretanto, tem uma alternativa onde o GHC é capaz de deduzir a exaustividade: correspondência de padrões em tipos de soma. E isso também pode ser usado para tomar decisões com base em pedidos. Seu algoritmo ficaria assim:

    gcd' x y = case compare x y of
   EQ -> x
   LT -> gcd' x (y - x)
   GT -> gcd' (x - y) y

    Eu diria que isso é realmente melhor que a versão com otherwise.

    • 9
  2. Best Answer

    As correspondências de padrões não são exaustivas. Em uma equação para ' gcd'':

    O problema é que Haskell não é tão inteligente para saber isso para dois itens xe y, ele sempre vale isso x < y, x > you x == y, e na verdade nem vale. Na verdade, para a NaN, não é válido:

    ghci> nan = 0/0
ghci> nan
NaN
ghci> nan == nan
False
ghci> nan > nan
False
ghci> nan < nan
False

    É melhor trabalhar com uma condição que seja sempre verdadeira: otherwise, que é um alias para True:

    gcd' :: Integer -> Integer -> Integer
gcd' x y 
    | x == y = x
    | x < y = gcd' x (y - x)
    | otherwise = gcd' (x - y) y

    Observe que uma implementação mais rápida gcd'é:

    gcd' :: Integral a => a -> a -> a
gcd' a b
  | b == 0 = a
  | otherwise = gcd' b (a `mod` b)
    • 2

relate perguntas