Bases de haskell

-- Fichier fonctions.hs
carre n = n*n

-- | f(0) = 0
-- | f(n) = n + f(n-1)
f 0 = 0
f n = n + f (n-1)

main = do
        putStrLn (show (carre 3))
        putStrLn (show (f 5))

• Interpréter avec la ligne de commande ghci fonctions.hs, puis, tester les fonctions :

  GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
  [1 of 1] Compiling Main             ( fonctions.hs, interpreted )
  Ok, one module loaded.
  *Main> carre 4
  16
  *Main> :t carre
  carre :: Num a => a -> a
  *Main>

  *Main> est le prompt. Il me dit donc que carre 4 vaut 16. :t permet de connaître le type d’un élément. La fonction carré est de type a -> a où est a doit être un type numérique.

• Ou compiler avec la ligne de commande ghc fonctions.hs, puis exécuter avec la ligne ./fonctions. Il va exécuter les instructions dans le main.

Note : Dans ghci, le i veut dire interactif, c’est un interpréteur similaire à celui de lua.

Note : Si on n’a pas ghc installé, on peut utiliser https://replit.com/languages/haskell.

Exercices

1. Écrire la fonction puissance.

2. En utilisant puissance, écrire la fonction exponentielle binaire (n \mapsto 2^n)

3. Écrire la fonction factorielle.

4. Écrire la fonction sommielle.

5. Écrire une fonction qui calcule le n-ième terme de la suite de Fibonacci.

   1. La tester sur l’entrée 30 (on devrait trouver 832040)
   2. La tester sur les valeurs suivantes. Mesurer le temps utilisé.
   3. Réfléchir à une version plus efficace.

6. Écrire des fonctions pair et impair qui testent si un nombre est pair ou impair.

7. Écrire une fonction combinaison qui calcule les combinaisons de k éléments parmi n en utilisant une identité connue du triangle de Pascal.

8. Écrire la fonction d’Ackermann.

   \left\{ \begin{array}{l} A(0, n) = n+1\\ A(m, 0) = A(m-1, 1)\\ A(m,n) = A(m-1, A(m, n-1))\end{array}\right.

   1. La tester sur l’entrée (3,0)
   2. La tester sur l’entrée (3,6)
   3. La tester sur l’entrée (3,7)
   4. La tester sur l’entrée (4,0)
   5. La tester sur l’entrée (4,1)