Fonction factorielle intégrée à Haskell
je sais que cela ressemble à une question stupide, mais la voici: Est-ce qu'il y a un factoriel intégré à Haskell?
Google me donne des tutoriels sur Haskell expliquant comment je peux l'implémenter moi-même, et je n'ai rien trouvé sur Hoogle. Je ne veux pas réécrire à chaque fois que j'en ai besoin.
je peux utiliser product [1..n] comme un remplacement, mais est-il vrai Int -> Int factorielle fonction intégrée?
7 réponses
même si elle est couramment utilisée pour des exemples, la fonction factorielle n'est pas très utile dans la pratique. Les nombres croissent très rapidement, et la plupart des problèmes qui incluent la fonction factorielle peuvent (et devraient) être calculés de manière plus efficace.
un exemple trivial est le calcul des coefficients binomiaux. Alors qu'il est possible de les définir comme
choose n k = factorial n `div` (factorial k * factorial (n-k))
il est beaucoup plus efficace de ne pas utiliser les factorielles:
choose n 0 = 1
choose 0 k = 0
choose n k = choose (n-1) (k-1) * n `div` k
Donc, non, il n'est pas inclus dans le prélude standard. Ni L'ordre de Fibonacci, la fonction Ackermann, ou de nombreuses autres fonctions qui, bien que théoriquement intéressant ne sont pas utilisés assez souvent dans la pratique pour justifier une place dans les bibliothèques standard.
cela étant dit, il y a de nombreuses bibliothèques de mathématiques disponibles sur Hackage.
Non, mais vous pouvez facilement écrire. Si vous êtes soucieux d'avoir à réécrire la fonction à chaque fois que vous en avez besoin, vous pouvez toujours l'écrire comme partie d'un module ou d'une bibliothèque (selon la distance que vous voulez prendre cette fonction, le nombre d'autres fonctions similaires que vous avez). De cette façon, vous avez seulement besoin de l'écrire une fois, et peut rapidement tirer à d'autres projets quand vous en avez besoin.
la meilleure implémentation de factorielle que je connaisse dans Hackage est Math.Combinatorics.Exact.Factorial.factorial dans le exact-combinatorics paquet. Il utilise un algorithme asymptotiquement plus rapide que product [1..n].
Essayez Hayoo! rechercher (lien sur le haut de hackage); il est venu avec ceci, par exemple
Vous avez product fonction qui est dans le prélude standard. Combiné avec des gammes, vous pouvez obtenir une fonction factorielle avec un effort minimal.
factorial n = product [n, n-1 .. 1]
nCr n r = n' `div` r'
where
-- unroll just what you need and nothing more
n' = product [n, n-1 .. n-r+1]
r' = factorial r
si vous cherchez une expression lambda, alors vous pouvez toujours utiliser le classique fix (\f x -> if x == 0 then 1 else x * (f (x - 1))).