GCF/LCM en Haskell

Question

Soy extremadamente nuevo en Haskell.

¿Hay una manera simple de encontrar el GCF o el LCM (mínimo común múltiple) en Haskell?

Answer 1

No estoy seguro de lo que es el LCF, pero el GCF es un favorito de Haskell. Usando el Algroitmo Euclidiano realmente puedes tener una idea de cómo funciona Haskell. http://en.wikipedia.org/wiki/Euclidean_algorithm Hay una gran explicación de cómo se configura el algoritmo aquí http://en.literateprograms.org/Euclidean_algorithm_(Haskell).

Este tipo de recursión es común en Haskell y muestra cuán expresivo puede ser el lenguaje.

gcd a 0 = a 
gcd a b = gcd b (a `mod` b) 

Este utiliza la coincidencia de patrones en los argumentos para decir el máximo común divisor de cualquier número y 0 es el primer número. Si los números son ambos diferentes de cero, busque el mayor factor común del segundo y el primer mod el segundo. Eventualmente esto alcanzará 0 en el segundo argumento. Esto desencadenará el primer patrón y devolverá el primer argumento que es la respuesta.

[EDIT]

La función debe ser en realidad:

gcd a 0 = a 
gcd a b = b `seq` gcd b (a `mod` b) where 

Esto obligará a la evaluación de la etapa recursividad anterior (un mod b) y evitará que un gran golpe seco que se construye en la memoria si , por ejemplo, está GCDing 1243235452 y 6095689787662. Seq fuerza el argumento a su "Forma normal de cabeza débil" o evalúa la estructura de datos más externa del argumento.

Answer 2

Por GCF, ¿te refieres al mayor factor común, o al máximo común divisor? Eso es gcd, disponible desde el preludio, como es lcm, el mínimo común múltiplo.

Answer 3

gcd se importa en el preludio. Eso significa que puede usarlo siempre que quiera sin ir a ninguna parte. Erik Hinton muestra una versión simple del algoritmo euclidiano, si está interesado en implementar la suya propia. Sólo una cosa: / se utiliza sólo para la división de punto flotante, utilice div y mod para encontrar el cociente y el resto cuando se quiere hacer "división entera." El preludio también define una función lcm para el mínimo común múltiplo.

Answer 4

O también se podría hacer

euclid(n,m) = 
    if n == m then n 
    else if n < m then euclid(n, m-n) 
    else euclid(n-m, m)