GCF/LCM in Haskell

Question

Sono estremamente nuovo per Haskell.

C'è un modo semplice per trovare il GCF o LCM (Minimo comune multiplo) in Haskell?

Answer 1

Non sono sicuro di cosa sia l'LCF ma GCF è un preferito di Haskell. Usando l'Algroithm euclideo puoi davvero capire come funziona Haskell. http://en.wikipedia.org/wiki/Euclidean_algorithm C'è una grande spiegazione di come l'algoritmo è impostato qui http://en.literateprograms.org/Euclidean_algorithm_(Haskell).

Questo tipo di ricorsione è comune in Haskell e mostra quanto può essere espressiva la lingua.

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

Questo utilizza pattern matching sugli argomenti a dire il massimo fattore comune di qualsiasi numero e 0 è il primo numero. Se i numeri sono entrambi diversi da zero, cerca il massimo fattore comune del secondo e il primo del secondo. Alla fine questo raggiungerà 0 nel secondo argomento. Questo attiverà il primo pattern e restituirà il primo argomento che è la risposta.

[EDIT]

La funzione deve essere effettivamente:

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

Questo forzerà la valutazione dello step ricorsione precedente (mod b) e impedirà un enorme thunk essendo costruito in memoria se , ad esempio, si sta utilizzando GCDing 1243235452 e 6095689787662. Seq impone l'argomento nella sua "Forma normale debole della testa" o valuta la struttura più esterna dell'argomento.

Answer 2

Con GCF intendi il più grande fattore comune o massimo comune divisore? Questo è gcd, disponibile dal preludio, come lo è lcm, il minimo comune multiplo.

Answer 3

gcd viene importato nel preludio. Ciò significa che puoi usarlo quando vuoi senza andare. Erik Hinton mostra una versione semplice dell'algoritmo euclideo, se sei interessato a implementare il tuo. Una cosa però: / viene utilizzato solo per la divisione in virgola mobile, utilizzare div e mod per trovare il quoziente e il resto quando si desidera eseguire la "divisione integer". Il preludio definisce anche una funzione lcm per il minimo comune multiplo.

Answer 4

Oppure si potrebbe anche fare

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