Comment écrire une fonction factorielle récursive dans un haskell sans sinon stattion

Question

fac n = if n < 2 then 1 else n * fac (n-1) 

main = do 

    putStrLn "Enter a number: " 
    number <- getLine 
    print $ number >>= fac 

Je ne sais pas comment écrire une fonction factorielle récursive sans instructions if. Notre professeur a dit quelque chose au sujet du lambda-calcul.

Answer 1

L'appariement de motifs et les protections sont deux moyens particulièrement simples. Les gardes sont essentiellement une autre syntaxe pour if-then-else; ils ressemblent à ceci:

fac n | n < 2  = 1 
     | otherwise = n * fac (n-1) 

Contrairement à if-then-else, ils supportent proprement plusieurs conditions; on pourrait aussi écrire, par exemple,

fac n | n < 0 = error "nah" 
     | n == 0 = 1 
     | n == 1 = 1 
     | n > 1 = n * fac (n-1) 

ce qui serait beaucoup moins joli sous forme de si-alors-autre.

avec correspondance de motif, on en général écrire plusieurs équations définissant:

fac 0 = 1 
fac 1 = 1 
fac n = n * fac (n-1) 

Pour connaître les numéros en particulier, ce desugars aussi essentiellement un if-then-else; mais pour les types de données avec moins d'intégration au compilateur, il est souvent impossible d'émuler avec if-then-else, et cela conduit souvent à un code très naturel.

Une autre très bonne approche serait de pousser votre récursion dans les fonctions Prelude existantes; plus vous pouvez repérer de motifs d'itération en pratique, plus vous pouvez éviter de bugs en ne réimplantant pas les mêmes boucles encore et encore. Pour celui-ci, vous pouvez utiliser product et la syntaxe d'énumération spéciale:

fac n = product [1..n] 

Un plus avancé (et bien pire) technique serait de définir un nouveau type de nombre; par exemple. Les chiffres d'église permettent au producteur du nombre de conduire la récursion, et le consommateur (ici, fac) de fournir simplement des cas de base. Dans ce style, vous pouvez voir quelque chose comme ceci:

fac n = fst (n (1,1) (\(prod, sum) -> (prod*sum, sum+1))) 

(Mais notez bien que cela exige un genre très spécial de numéro - certainement le type de fac ne fait pas partie d'une fonction qui pourrait accepter Int ou Integer !) Cette blague est pris à sa conclusion logique et horrifiant dans The Evolution of a Haskell Programmer.

Answer 2

Si/alors/else et les gardes ne sont en fait que du sucre syntaxique pour l'appariement de formes.

if b 
    then c 
    else d 

desugars à

case b of 
    True -> c 
    False -> d 

De même,

f x 
    | b = c 
    | d = e 
f x = g 

desugars à

f x = case b of 
     True -> c 
     False -> case d of 
      True -> e 
      False = g 

Alors vous pouvez toujours utiliser directement case. Cependant, il existe une optimisation plutôt simple que vous pouvez effectuer manuellement.Si vous voyez

case x == p of 
    True -> a 
    False -> b 

où p est faite des constructeurs et littéraux, vous pouvez remplacer le tout avec

case x of 
    p -> a 
    _ -> b 

Answer 3

essayez ceci:

factorial 0 = 1 
factorial n = n * factorial (n - 1) 

---

En utilisant la récursivité queue:

factorial n = f n 1 

f 0 acc = acc 
f n acc = f (n-1) (acc*n) 

main = print $ factorial 5 

sortie:

120