\chapterimage{PureFun}
\chaptertext{}

\chapter{Let's have some fun}


\section{C'est quoi une fonction?}

Langage  fonctionnel,  fonction? Est-ce  que  vous  savez vraiment  ce
qu'est une fonction?


%\begin{figure}
\begin{center}
  \includegraphics[width = 0.5\linewidth]{Dysfunctional.jpg}
\end{center}
%\end{figure}


Pour définir  une fonction,  il faut  un ensemble  de départ  (un type
quoi)  et un  ensemble  d'arrivée  (le même  type  ou  un autre).  Une
fonction associe à chaque élément du type de départ AU PLUS UN ÉLÉMENT
du type d'arrivée.

En fait, une fonction c'est une \textit{flèche} entre deux types 


\begin{exemple}[Un exemple de fonction]

  
%\begin{figure}
\begin{center}
  \includegraphics[height=6cm]{robin}
\end{center}
%\end{figure}
\end{exemple}

Prenons un autre exemple: la fonction \lstinline{not} qui a un booléen
associe l'autre.

Comme toute chose en Haskell, \lstinline{not} a un type:

\begin{lstlisting}
λ> :t not
not :: Bool -> Bool
\end{lstlisting}

\lstinline{not} a pour  type \lstinline{Bool} flèche \lstinline{Bool}:
c'est une fonction qui a un booléen associe un autre booléen.

Pour les fonctions, on dit plutôt  que \lstinline{Bool -> Bool} est la
\textit{signature} de type de la fonction \lstinline{not}. 

On ne sait pas encore comment elle  calcule les images mais ça ne doit
pas être compliqué:

\begin{lstlisting}
λ> not False
True
λ> not True
False
\end{lstlisting}

Alors on va essayer de le  faire nous-mêmes:  pourquoi toujours
parler anglais!

\begin{lstlisting}
data Booleen = Faux | Vrai

non :: Booleen  -> Booleen
non    Vrai     =  Faux
non    Faux     =  Vrai
\end{lstlisting}

On  donne l'image  de chaque  élément  du type  de départ.   Il n'y  a
qu'une seule image appartenant au type d'arrivée. 

Bon, c'est  un peu  limité comme fonction  mais nous  l'avons fabriqué
entièrement: son  ensemble de  départ, son  ensemble d'arrivée  et son
\textit{graphe}.

\begin{definition}[Graphe d'une fonction]

Le graphe d'une fonction est l'ensemble de tous les couples:

$\langle$ élément du départ, son image dans l'arrivée $\rangle$

ou si vous préférez:

$$\GR(f) = \bigl\{\langle x,f(x)\rangle \mid x ∈ \text{départ} \bigr\}$$
  
\end{definition}

et voilà notre fonction bien définie. En maths on écrirait:

$$f=\Big\langle Booleen, Booleen, \bigl\{\langle Vrai,Faux\rangle, \langle
Faux, Vrai \rangle\bigr\}\Big\rangle$$

\begin{NB}
Une fonction est donc un triplet $ \langle$ Départ, Arrivée, Graphe$ \rangle$
\end{NB}

\begin{DANGER}[Ne pas oublier!]
  Une fonction est donc un {\LARGE TRIPLET} $ \langle$ Départ, Arrivée, Graphe$ \rangle$
\end{DANGER}

\begin{DANGER}[Ne pas oublier!]
  Le graphe ne suffit  pas à définir une fonction: il faut  préciser son type de
  départ et son type d'arrivée.
\end{DANGER}



%\begin{figure}
\begin{center}
  \includegraphics[height=8cm]{compris}
\end{center}
%\end{figure}


\section{Une fonction c'est more fun}

Bon, OK, maintenant, que se passe-t-il si j'ai plusieurs arguments? Par exemple,
le \og et\fg{} logique qu'on appelle plutôt \textit{conjonction}.

On réfléchit  d'abord sans clavier.  Le premier  booléen et le  deuxième booléen
sont vrais si,  et seulement si, ils  sont vrais tous les deux,  ce qui signifie
que si l'on appelle \og \lstinline{et}\fg{} notre fonction, alors 
\begin{quote}
et x y vaut:

si x = Vrai et y = Vrai alors Vrai

dans tous les autres cas Faux
\end{quote}

ce qui s'écrit plus joliment en Haskell:

\begin{lstlisting}
et :: Booleen -> Booleen -> Booleen
et    Vrai       Vrai    =  Vrai
et    _          _       =  Faux
\end{lstlisting}

Le \lstinline{_} signifiant: \og n'importe quelle valeur autre que celle(s) déjà
étudiée(s)\fg{}. 

Vraiment n'importe laquelle?  Non, comme on a signé la  fonction, on doit rester
dans les types annoncés.

On   dit  qu'on   a  défini   la  fonction   par  \textit{filtrage   par  motif}
(\textit{pattern matching in anglais of spécialité}.)

On teste ça dans GHCi:

\begin{lstlisting}
λ> :l ./introHs
[1 of 1] Compiling Main             ( introHs.hs, interpreted )
Ok, modules loaded: Main.
λ> et Vrai Faux

<interactive>:16:1-12:
    No instance for (Show Booleen) arising from a use of `print'
    Possible fix: add an instance declaration for (Show Booleen)
    In a stmt of an interactive GHCi command: print it
\end{lstlisting}

Hein? Bon, on  a pas encore étudié les  classes de types mais on  comprend à peu
près que  Haskell ne sait  pas comment  afficher nos \lstinline{Booleen}.  On va
juste  lui   dire  de  les  afficher   tels  quels  à  l'aide   de  la  fonction
\lstinline{deriving} que nous étudierons plus en détail plus tard.

On ajoute juste une ligne à notre fichier hs:

\begin{lstlisting}
data Booleen = Faux | Vrai
             deriving Show
\end{lstlisting}

on sauve et on recharge dans GHCi:

\begin{lstlisting}
λ> :r
[1 of 1] Compiling Main             ( introHs.hs, interpreted )
Ok, modules loaded: Main.
λ> et Vrai Faux
Faux
\end{lstlisting}

On  aurait   pu  remarquer  une  autre   chose:  si  le  premier   argument  est
\lstinline{Vrai} alors \lstinline{et  Vrai x = x} et si  le premier argument est
\lstinline{Faux}, alors \lstinline{et Faux x = Faux}.

On peut donc définir également notre fonction ainsi:

\begin{lstlisting}
et' :: Booleen -> Booleen -> Booleen
et'    Vrai       x       =  x
et'    Faux       x       =  Faux 
\end{lstlisting}



Ces fonctions sont-elles bien égales? Mais  ça veut dire quoi que deux fonctions
sont égales? ({\itshape répondez vite ou bien j'appelle Conan}).


Il faut  regarder leurs  types de départ  et d'arrivée...mais !??  Il y  a trois
types et deux flèches!!!

\subsection*{Curryfication}

Calmons-nous. N'oubliez pas:  la difficulté en informatique vient  souvent de la
surabondance de solutions  à nos problèmes. Il  y a le plus  souvent beaucoup de
manières de modéliser une situation. Il faut faire un (parfois le) bon choix.


%\begin{figure}
\begin{center}
  \includegraphics[height=4cm]{roma}
\end{center}
%\end{figure}
Un habitué de C, Java ou Python pourrait définir la
fonction \og \lstinline{et} \fg{} à l'aide de ce code spaghetti:

\begin{algo}
\FUNC{et}{\pfarg{x,y}{booléens}}{booléen}
\BEGIN
\IF{x == Vrai}
\RETURN{y}
\ELSE
\RETURN{Faux}
\ENDIF
\END
\end{algo}

On a donc une fonction de deux  variables. Un mathématicien obtus ou un adepte
des bases de données pourrait
alors définir sa  fonction de la même  manière (car il se souvient  de la notion
de \textit{produit cartésien} défini au chapitre précédent):

$$
{\rm et}\colon 
\begin{array}{rll}
 \mathtt{Booleen × Booleen} & → & \mathtt{Booleen}\\
 (x,y)& \mapsto &
 \begin{cases}
   \text{si } x == {\rm Vrai} \text{ alors } y\\
   \text{sinon Faux} 
 \end{cases}
\end{array}
$$

Bref, la fonction \og et\fg{} serait une fonction de 2 variables. Mais il y a un
problème en  Haskell  ...

\begin{NB}
  Sur  Haskell  , toutes les fonctions sont d'UNE SEULE VARIABLE!
\end{NB}



Ouvrez bien les yeux! La fonction définie  juste avant a UNE seule flèche: c'est
donc bien UNΕ fonction.

Les fonctions  définies sur   Haskell   comportaient DEUX  flèches dans  leur signature
donc derrière ces fonctions  se cachent en fait DEUX fonctions  car une flèche =
une fonction.

C'est qu'en fait, la signature de notre fonction \og et2\fg{} peut aussi s'écrire



\begin{lstlisting}
et2 :: Booleen -> (Booleen -> Booleen)
et2    Vrai       x       =  x
et2    Faux       x       =  Faux 
\end{lstlisting}

Ainsi \og \lstinline{et2} \fg{} est en fait UNE fonction qui à un \lstinline{Booleen} associe
UNE AUTRΕ fonction. GHCi nous le confirme:

\begin{lstlisting}
λ> :t et2 Vrai
et2 Vrai :: Booleen -> Booleen
\end{lstlisting}

\og \lstinline{et2 Vrai}\fg{} est une fonction qui à un \lstinline{Booleen} associe un autre
\lstinline{Booleen}.

On omet le plus  souvent les parenthèses de la signature car  par défaut, la $→$
de la signature est \textit{associative à droite} sur  Haskell  .

On pourrait donc créer deux fonction intermédiaires et une fonction principale:


\begin{lstlisting}
idem :: Booleen -> Booleen
idem    x       =  x

tjsFaux :: Booleen -> Booleen
tjsFaux    x        = Faux
         
et4 :: Booleen -> Booleen -> Booleen
et4    Vrai    =  idem
et4    Faux    =  tjsFaux
\end{lstlisting}

Cela  nous  permet  d'utiliser   \lstinline{idem}  ou  \lstinline{tjsFaux}  dans
d'autres contextes.


\subsection*{Toujours plus fort: les lambda-expressions}



Nous allons enfin découvrir pourquoi le symbole de  Haskell   contient un $λ$.....


%\begin{figure}
\begin{center}
  \includegraphics[height=3cm]{logoHS}
\end{center}
%\end{figure}

Une fonction est une flèche. Elle n'a  pas forcément besoin de porter un nom. On
peut  définir  une fonction  sans  la  nommer  à  l'aide de  \lstinline{\}  (qui
  ressemble à un $ \lambda$...)


  \begin{lstlisting}
λ> ((\ x -> 2*x) :: (Int -> Int)) 5
10
  \end{lstlisting}

ou plus simplement:

  \begin{lstlisting}
λ> (\ x -> 2*x) 5
10
  \end{lstlisting}

  \begin{aparte}[Petite histoire du $λ$]
En 1936, Alan \textsc{Turing} et  Alonzo \textsc{Church} écrivent les fondements
de ce qui deviendra l'informatique.  \textsc{Church} introduit une notation pour
définir des  fonctions qui était au  départ une sorte d'accent  circonflexe qui,
après  le passage  de  plusieurs  typographes s'est  transformé  en $Λ$  (lambda
majuscule) puis en $λ$. 
  \end{aparte}

Cette possibilité est reprise par exemple en python:

\pythonc

\begin{lstlisting}
In [1]: (lambda x: 2*x)(5)
Out[1]: 10
\end{lstlisting}
\haskell

Pour notre problème initial, cela nous permet d'écrire aussi:


\begin{lstlisting}
et4 :: Booleen -> Booleen -> Booleen
et4    Vrai    =  \ x -> x
et4    Faux    =  \ x -> Faux
\end{lstlisting}



\subsection*{Gardes ou expressions conditionnelles?}

OK, on  a plein de possibilités,  mais est-ce qu'on peut  quand même implémenter
tel quel l'algo spaghetti à la mode C/Java/Python \& Co?


\begin{lstlisting}
et5 :: Booleen -> Booleen -> Booleen
et5 y x = if y == Vrai
          then x
          else Faux
\end{lstlisting}

Une petite remarque  sur le \lstinline{if ... then ...  else}: comme toute chose
en  programmation  fonctionnelle,  il  s'agit d'une  expression  qui  doit  donc
retourner une valeur.

Il ne faut donc  surtout pas oublier le \lstinline{else} comme  on peut le faire
dans les langages impératifs. C'est une sécurité supplémentaire...

\og  Si  j'ai  un  parachute  alors   je  peux  sauter  de  l'avion\fg{}:  c'est
raisonnable, mais  que se passe-t-il  si je n'ai  pas de  parachute: je
saute quand même?  Je tue le(a) pilote? J'appelle Superman?  Je séduis l'hôtesse de
l'air (ou le steward)?

On évitera cependant  au maximum le recours aux  expressions conditionnelles car
elles peuvent ralentir l'évaluation répétée  de ceratines fonctions mais nous en
reparlerons plus tard.

Il   existe   une   syntaxe   alternative  plus   fonctionnelle:   l'emploi   de
\textit{gardes}  qui permet  de calculer  une  image selon  qu'une ou  plusieurs
valeurs  vérifie  une  certaine  propriété.  Cela  ressemble  à  une  expression
conditionnelle mais permet d'enchaîner autant de conditions que désirées.

Ça s'appelle un garde car ça garde l'évaluation: il faut montrer patte blanche.

Par exemple:

\begin{lstlisting}
placeDeCinema :: Int -> String
placeDeCinema age
    | age < 0   = "Euh, t'as bu quoi au petit déjeuner?"
    | age < 12  = "Pour toi c'est 2 euros et viens prendre un bonbon"
    | age < 18  = "Pour toi c'est 8 euros"
    | otherwise = "T'es pas un peu vieux pour aller voir Petit Poney?"
\end{lstlisting}

Le compilateur visite les gardes de haut en bas.

En ce qui concerne notre problème, c'est assez simple:

\begin{lstlisting}
et6 :: Booleen -> Booleen -> Booleen
et6 x y
    |x == Vrai = x
    |otherwise = Faux
\end{lstlisting}

En fait, \lstinline{otherwise} est un synonyme de \lstinline{True} mais facilite
la  lecture. C'est    un  garde qui  laisse  passer tout  le monde  c'est
pourquoi on le laisse pour la fin...


\section{En résumé, comment construire nos fonctions?}

Peu importe la syntaxe, voici les étapes importantes à suivre:


\begin{description}
\item[SPÉCIFIER] la  fonction: c'est-à-dire parfois (on  peut effectivement s'en
  passer au besoin) la nommer, donner son \textit{type}, i.e. son domaine et son
  codomaine: on parle de \textit{signature de type} et on explique ce qu'elle fait. Par
  exemple pour le double d'un entier sur  Haskell  :

  \begin{lstlisting}
double :: Int -> Int
-- calcule le double d'un entier : le résultat est un entier
  \end{lstlisting}

Sur  Haskell  , donner la signature  est optionnel car le compilateur l'\textit{infère}
mais c'est une bonne pratique de l'annoncer à l'avance pour plus de sécurité. Si
le type inféré par le compilateur est différent de celui spécifié, c'est qu'il
faut revoir sa copie...Cela rend de plus le code plus lisible.

On peut obtenir le type d'une expression avec la commande \verb+:t+:

\begin{lstlisting}
λ> :t double
double :: Int -> Int
\end{lstlisting}

\item[RÉALISER]  la  fonction  c'est  associer   à  la  fonction  spécifiée  une
  expression.  Dans notre  exemple, il  s'agit  de multiplier  l'argument de  la
  fonction par 2. Pour cela, on utilise des \textit{paramètres formels} qui font
  \textit{abstraction}  de  la  valeur  particulière  du  nombre  dont  on  veut
  connaître le double. Ici:

  \begin{lstlisting}
double n = 2 * n
  \end{lstlisting}

\item[UTILISER]   la  fonction   dans  une   expression  en   lui  donnant   des
  \textit{paramètres effectifs} (arguments), c'est-à-dire liés à l'application particulière
  de la fonction:

  \begin{lstlisting}
λ> double 3 + double 7
20
  \end{lstlisting}

\end{description}




Il  faut bien  noter que  les  étapes de  réalisation et  d'utilisation sont  en
quelque sorte indépendantes, contrairement au paradigme impératif.  

La
réalisation  \textit{fait abstraction}  de  l'utilisation: l'expression  fournie
réalisera la spécification quelque soit le contexte.

L'utilisation  \textit{fait  abstraction}  de  la réalisation:  si  on  suit  la
spécification, on aura ce qu'on veut dans tous les cas.





\section{Fonction récursives: première approche}


\subsection*{Les mains dans le cambouis}

Nous  allons étudier  le plus  classique des  problèmes: il  s'agit de
calculer la somme des entiers de 1 à un entier naturel $ n$ non nul donné.

La  \textit{spécification}  est immédiate:  on  crée  une fonction  ayant  pour
argument  l'entier   naturet  $  n$  et   renvoyant  l'entier  naturel
correspondant à la somme des entiers de 1 à $ n$.

Il reste à s'occuper de la \textit{réalisation}.

Appelons  $  S(n)$  la  somme  des  entiers   de  1  à  $  n$  avec  $
n\in\bbn\setminus \bigl\{0\bigr\}$.

On a $ S(1)=1$ et $ S(n) = n + S(n-1)$.
\begin{lstlisting}
s1 :: Int -> Int
s1 n
    | n == 1    = 1
    | otherwise = n + s1 (n -1)
\end{lstlisting}

Et  si n  est négatif?  Le type  de départ  ne l'empêche  pas. Nous  devons donc
inclure une précaution supplémentaire:

\begin{lstlisting}
s1 :: Int -> Int
s1 n
    | n <= 0    = error "l'argument doit être un entier naturel non nul"
    | n == 1    = 1
    | otherwise = n + s1 (n -1)
\end{lstlisting}

Un  dernier détail:  à chaque  étape, on  testera si  n est  négatif ce  qui est
inutile car n ne peut être négatif que la première fois.


\begin{lstlisting}
s1 :: Integer -> Integer
s1 n | n <= 0    = error "l'argument doit être un entier naturel non nul"
     |otherwise  = aux n
     where aux 1 = 1
           aux n = n + aux (n - 1)
\end{lstlisting}


Que  se passe-t-il  quand  on calcule  \texttt{s1(5)}?  On utilise  le
modèle de \textit{substitution}:



{\ttfamily
s1(5)\\
5 + s1(4)\\
5 + (4 + s1(3))\\
5 + (4 + (3 + s1(2)))\\
5 + (4 + (3 + (2 + s1(1))))\\
5 + (4 + (3 + (2 + 1)))\\
5 + (4 + (3 + 3))\\
5 + (4 + 6)\\
5 + 10\\
15
}


On commence par quatre expansions suivies de cinq réductions.

La  \textit{procédure} est  récursive  car syntaxiquement  \texttt{s1}
apparaît dans sa propre définition (\lstinline{n + s1 (n - 1)}).

Le  \textit{processus} est  également récursif:  les évaluations  sont
retardées.  Intuitivement, cela  est le  cas car  on progresse  du cas
compliqué vers le cas simple: on \og descend\fg{} ici de $ n$ vers 1.
Le compilateur doit \textit{empiler} les résultats des expansions tant
qu'il ne peut pas les réduire.
La taille de  la pile nécessaire étant proportionnelle  à l'argument $
n$, on dit qu'il s'agit d'un processus linéairement récursif.


Essayons de calculer la somme des entiers de 1 à \num{1000000}:

\begin{lstlisting}
main = print (s1 1000000)
\end{lstlisting}


\shell

\begin{lstlisting}
$ ghc ./introHs.hs -o som1

$ time ./som1
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

real	0m0.067s
user	0m0.063s
sys	0m0.004s
\end{lstlisting}

 \haskell


Le problème, c'est que l'opérateur est  strict sur ses deux arguments: cela veut
dire  que les  deux arguments  doivent être  évalués avant  que la  somme puisse
renvoyer une valeur.

L'idée est d'obtenir:

\texttt{(((1 + 2) + 3) + 4) + 5}

qui peut être évalué immédiatement au lieu de: 

\texttt{5 + (4 + (3 + (2 + 1)))}


qui en fait empile 5, 4, 3 et 2 avant de commencé à réduire.


Il s'agit de partir du cas simple et de \og monter\fg{}
vers  le   cas  compliqué  (on   parle  dans  ce   cas  habituellement
d'\textit{induction}).

Ici, la somme vaut  0 puis on ajoute 1, puis on  ajoute au résultat 2,
puis on ajoute au résultat 3, etc jusqu'à atteindre $ n$.

Techniquement, on  entretient un  \textit{accumulateur} de  termes qui
évolue et un compteur qui va évoluer de 1 jusque $ n$.

L'accumulateur et le compteur évoluent selon la règle:

\begin{algo}
  accumulateur \recoit{} accumulateur + compteur\\
  compteur \recoit{} compteur + 1
\end{algo}

la  somme  cherchée  étant  la valeur  de  l'accumulateur  lorsque  le
compteur a dépassé $ n$.



On essaie ça sur Haskell:

\begin{lstlisting}
s2 :: Integer -> Integer
s2 n =
    let sIter acc compt
            | compt <= 0 = acc
            | otherwise  = sIter (acc + compt) (compt -1)
    in sIter 0 n
\end{lstlisting}

Ça va marcher:

\shell

\begin{lstlisting}
$ time ./som2
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

real	0m0.177s
user	0m0.149s
sys	0m0.028s
\end{lstlisting}

Arghh!

Cela aurait  dû marcher avec  la plupart des  langages fonctionnels ou  du moins
optimisant  ce qu'on  appelle la  \textit{récursion terminale}  (tail recursion)
C'est d'ailleurs ce que fait OCaml:

\caml

\begin{lstlisting}
let rec suma = function
      |1 -> 1
      |n -> n + (suma (n - 1));;

let sumb n =
  let rec siter acc compt =
    if compt <= 0 then acc
    else siter (acc + compt) (compt - 1)
  in siter 0 n;;
\end{lstlisting}

qui donne:

\begin{lstlisting}
utop[1]> suma 1_000_000;;
Stack overflow during evaluation (looping recursion?).
utop[2]> sumb 100_000_000;;
- : int = 5000000050000000
\end{lstlisting}


\haskell
Sur Ocaml par exemple, la procédure \texttt{siter} est syntaxiquement récursive car elle
est  définie  à  partir  d'elle-même  mais  le  processus  n'est  plus
récursif! les évaluations ne sont plus retardées:

{\ttfamily
sumb 5\\
siter 0  1\\
siter 1  2\\
siter 3  3\\
siter 6  4\\
siter 10 5\\
siter 15 6\\
15
}

Cette fois-ci, il  n'y a plus de phase d'expansion  suivie d'une phase
de réduction. À chaque étape, il  suffit de garder une trace des états
de  \texttt{acc}  et  \texttt{compt}.  On  parle  alors  de  processus
\textit{itératif}. 
 
\vspace{1cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{gastonHs}
%\caption{Stephen \textsc{Kleene}}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5cm}
\begin{minipage}[t]{\linewidth}
\end{minipage}


Mais Haskell a une autre particularité: il \textit{évalue paresseusement}. C'est
une notion un peu compliquée. Disons  que le compilateur n'évalue une expression
que quand  il est  \og forcé\fg{}  de le  faire. Nous  en reparlerons  plus tard
éventuellement.

Il existe  un moyen  de forcer  le compilateur à  travailler: c'est  la fonction
\lstinline{seq}.  Mais elle  est dangereuse  en Haskell  pour des  raisons assez
complexes... En gros,  \lstinline{seq x f(x)} va forcer l'évaluation  de x avant
de s'occuper de f(x).

Ici:

\begin{lstlisting}
s3 n =
    let sIter acc 0     = acc
        sIter acc compt =
            let newAcc = compt + acc
            in seq newAcc (sIter newAcc (compt - 1))
    in sIter 0 n
\end{lstlisting}


Alors:

\shell

\begin{lstlisting}
$ time ./som3
500000500000

real	0m0.078s
user	0m0.075s
sys	0m0.004s
\end{lstlisting}

\haskell
\subsection*{Restons propres}

Un peu technique hein? Bon, nous allons dans un premier temps ne pas tenir compte de
toutes ces subtilités.  

On se contentera de créer des fonctions de ce type:

\begin{lstlisting}
s1 :: Int -> Int
s1 n
    | n <= 0    = error "l'argument doit être un entier naturel non nul"
    | n == 1    = 1
    | otherwise = n + s1 (n -1)
\end{lstlisting}


ou mieux:

\begin{lstlisting}
s4 n = sum [1 .. n]
\end{lstlisting}

ou à la rigueur:

\begin{lstlisting}
s5 n = foldl (+) 0 [1 .. n]
\end{lstlisting}

mais cette fonction \lstinline{foldl} est  encore mystérieuse et sera étudiée en
temps voulu. 

Mais  vous aurez  noté  l'emploi de  listes  pour régler  ce  problème de  somme
d'entiers. C'est que la structure de  base de la programmation fonctionnelle est
justement la liste.
























\section{Une première approche des listes sur Haskell}

\subsection*{Définition récursive d'un type}



On  ne dispose  souvent  que  de quelques  types  de  base: entiers,  flottants,
caractères, booléens.

On a pourtant besoin de types plus sophistiqués.

Par  exemple, qu'est-ce  qu'un  mot? Disons  que  c'est soit  le  vide, soit  un
caractère suivi d'un mot. Cela nous  donne une règle de \textit{construction} de
proche en proche:  on ajoute une à une  dans l'ordre les lettres du  mot pour le
construire. 

La structure attachée est celle d'un arbre. Voici celui correspondant au mot \og glop\fg{}.

\vspace{1cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{glop}
%\caption{Stephen \textsc{Kleene}}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5cm}
\begin{minipage}[t]{\linewidth}
\end{minipage}

\begin{center}
\begin{tikzpicture}[sibling distance=50pt% , every internal node/.style={circle,fill=white,draw=black,text=black}
  ]
\Tree [.:+ g
         [.:+ l
             [.:+ o
                 [.:+ p
                    Vide ] ] ] ];
\end{tikzpicture}
\end{center}

On choisit un  \textit{opérateur infixe} \verb|:+| pour  noter le \textit{constructeur}
par ajout d'un caractère à gauche. 

Comme  il faut  bien partir  de  quelque chose,  on crée  aussi le  constructeur
\verb+Vide+ qui construit un mot vide.



Sur  Haskell  , ce genre  de type se crée simplement avec  \verb+data+ après avoir créé
un opérateur infixe avec la fonction \verb+infixr+:

\begin{lstlisting}
infixr 1 :+

data Mot = 
  Vide 
  | Char :+ Mot 
\end{lstlisting}


Le  \og r\fg{}  après  \verb+infix+  indique que  l'opérateur  est associatif  à
droite:

\verb|'a' :+ ('b' :+ ('c' :+ Vide)) == 'a' :+ 'b' :+ 'c' :+ Vide|


Le \verb+1+ indique  le niveau de priorité  sur les autres opérateurs.  Par exemple, le
niveau de \verb+*+ est 7 alors que celui de \verb|+| est 6.

Le \verb+|+ indique l'alternative.

On va rajouter un  petit sucre dont on reparlera plus  tard: la dérivation. Pour
pouvoir afficher nos objets dans l'interpréteur, nous allons faire en sorte que notre type
\verb+Mot+ fasse partie de la classe \verb+Show+:

\begin{lstlisting}
data Mot = 
  Vide 
  | Char :+ Mot 
  deriving (Show)
\end{lstlisting}

On peut maintenant créer un mot:

\begin{lstlisting}
λ> let m = 'a' :+ 'b' :+ Vide
λ> m
'a' :+ ('b' :+ Vide)
λ> :t m
m :: Mot
\end{lstlisting}

Pour pouvoir travailler  sur ces \og Mots\fg{}, en plus  des constructeurs, on a
besoin de  \textit{sélecteurs} qui vont  permettre de désigner les  éléments qui
ont  permis  de  construire  le  mot.  Les  sélecteurs  permettent  en  fait  de
\textit{découper} les objets construits.

Ici, on construit des  arbres par la gauche: nous avons  besoin de distinguer la
\textit{tête} du mot qui est son premier caractère, de sa \textit{queue} qui est
le mot privé de sa tête. Attention! Un mot vide n'a ni queue ni tête...


Par exemple, pour la tête:

\begin{lstlisting}
tete :: Mot -> Char
-- renvoie le premier caractère d'un mot avec un filtrage par motif
tete Vide = error "Mot vide !"
-- un mot vide n'a pas de tête
tete (t :+ q) = t
\end{lstlisting}

\begin{recherche}
Déterminez une fonction \verb+queue :: Mot -> Mot+ qui renvoie la queue d'un mot.
\end{recherche}


Par exemple:

\begin{lstlisting}
λ> tete m
'a'
\end{lstlisting}

On pourrait avoir besoin de \textit{testeurs}  qui nous permet de savoir comment
a été  construit l'objet. Ici,  ce serait un  test \verb+estVide+ mais  on peut
s'en passer grâce au \textit{filtrage par motif}.


En ce qui concerne  Haskell  , on peut donc avoir à comparer un mot au mot \verb+Vide+:
il faut donc dériver notre type de la classe \verb+Eq+:

\begin{lstlisting}
data Mot = 
  Vide 
  | Char :+ Mot 
  deriving (Show,Eq)

estVide :: Mot -> Bool
estVide m = m == Vide

λ> estVide Vide
True

λ> estVide m
False
\end{lstlisting}

Sélecteurs et testeurs sont alors liés par la relation:

$$
  \lnot  (\text{estVide }  m) \lequiv  \big(m  = (\text{tete  } m)  \text{ :+  }
  (\text{queue } m) \big)
$$



Cherchons maintenant à définir une fonction sur ce type \verb+Mot+. Par exemple,
on voudrait compter le nombre de \og a\fg{} dans un mot.

Commençons par la signature:

\begin{lstlisting}
nba :: Mot -> Int
-- calcule le nombre de 'a' dans un mot
\end{lstlisting}

Nous allons étudier ensuite tous les cas de construction d'un mot. Il y en a deux.

\begin{itemize}
\item Si le mot est vide, alors son nombre de 'a' est 0.
\item Sinon, le mot est construit par \verb|t :+ q|.  

Si  $\mathtt{t}  =
  \mathtt{'a'}$, alors $\mathtt{nba\ mot} = 1 + \mathtt{nba\ q}$, sinon, $\mathtt{nba\ mot} = \mathtt{nba\ q}$.
\end{itemize}


Il n'y a plus qu'à transcrire cela en  Haskell  :

\begin{lstlisting}
nba Vide     = 0
nba (t :+ q) = (nba q) + (if t == 'a' then 1 else 0)
\end{lstlisting}

Autre syntaxe possible en filtrant sur le motif de \verb+t+::

\begin{lstlisting}
nba2 Vide = 0
nba2 (t :+ q) 
  | t == 'a' = (nba2 q) + 1
  |otherwise =  nba2 q
\end{lstlisting}


Une manière  plus fonctionnelle  de procéder  est d'utiliser  un pliage  mais la
fonction \verb+foldl+ est de signature 
 \verb+foldl :: (a -> b -> a) -> a -> [b] -> a+ donc ne peut plier que des
listes. 

Il faudrait soit créer  une fonction de pliage de mots.

Comme je  suis très gentil,  je vous propose une  solution pour le  pliage (pour
vous aider d'ailleurs à mieux comprendre le pliage gauche...):

\begin{lstlisting}
pliage :: (a -> Char -> a) -> a -> Mot -> a
-- adapte foldl aux mots
pliage fonc ini Vide     = ini
pliage fonc ini (t :+ q) = pliage fonc (fonc ini t) q


nba4 :: Mot -> Int
-- calcule le nombre de 'a' dans un mot par pliage
nba4 mot =
  pliage (\accu t -> accu + (if t == 'a' then 1 else 0)) 0 mot 
\end{lstlisting}
 
En fait,  il faut penser à  un immeuble qui s'écroule,  une lunette télescopique
qu'on...replie, etc.

\begin{center}
\begin{multicols}{2}
\begin{tikzpicture}[sibling distance=20pt% , every internal node/.style={circle,fill=white,draw=black,text=black}
  ]
\Tree [.: g
         [.: l
             [.: o
                 [.: p
                    Vide ] ] ] ];
\end{tikzpicture}
\begin{tikzpicture}[sibling distance=20pt% , every internal node/.style={circle,fill=white,draw=black,text=black}
  ]
\Tree [.f [.f [.f [.f ini g ] l ] o ] p ];
\end{tikzpicture}
\end{multicols}
\end{center}

avec ici \lstinline{f = \ acc lettre -> acc + (if lettre == 'a' then 1 else 0)} et \lstinline{ini=0} 




\subsection*{Zoom sur les listes}


Vous  étudierez en  algo2 les  listes  d'un point  de vue  \og bas  niveau\fg{},
c'est-à-dire en mettant les mains dans le cambouis de la machine.

En mathématique,  nous restons propres  et proches de  la nature. Les  listes ne
seront pas des  parties d'un moteur polluant  mais de beaux arbres  bons pour la
planète.  Malgré tout,  ce seront  des  arbres un  peu spéciaux  car ils  seront
plats...

Ce  type pré-existe  bien  sûr en   Haskell  .  Dans un  but  pédagogique, nous  allons
cependant le reconstruire à la main.

\subsubsection*{Le constructeur liste}

Bon, nous avons vu les mots dans la section précédente donc vous devriez pouvoir
créer sans souci  un type \verb+Liste+...il faudrait juste préciser  ce que nous
entendons par liste!

C'est un ensemble d'éléments de  \textit{même type} placés dans un \textit{ordre
  donné}.

Conventionnellement, on note les listes en plaçant leurs élément séparés par des
virgules   entre   crochets.   Par   exemple,   voici   une   liste   d'entiers:
$[1,6,45,-7,0]$.

Nos mots étaient  en fait des listes  de caractères, mais on  veut aussi pouvoir
créer des listes d'entiers, de booléens, de schmurx, etc.

Nous allons donc créer un type \textit{polymorphe}...


%\begin{figure}
\begin{center}
  \includegraphics[height=5cm]{frankenstein}
\end{center}
%\end{figure}


\begin{lstlisting}
infixr 1 :-

data Liste a = 
  Nil 
  | a :- (Liste a) 
  deriving (Show,Eq,Ord)
\end{lstlisting}


Nous choisissons cependant de choisir nos éléments dans un ensemble ordonné pour
rendre nos listes plus riches (...et surtout \og triables\fg{}).

Par exemple:

\begin{lstlisting}
λ> let l1 = 1 :- 6 :- 45 :- (-7) :- 0 :- Nil
λ> l1
1 :- (6 :- (45 :- (-7 :- (0 :- Nil))))
λ> :t l1
l1 :: Liste Integer
\end{lstlisting}

La machine (et vous...) voit en fait ça:


\begin{center}
\begin{tikzpicture}[sibling distance=50pt% , every internal node/.style={circle,fill=white,draw=black,text=black}
  ]
\Tree [.:- 1
         [.:- 6
             [.:- 45
                 [.:- $-7$
                    [.:- 0
                    Nil ] ] ] ] ];
\end{tikzpicture}
\end{center}

On peut créer des listes de booléens si ça nous chante:

\begin{lstlisting}
λ> let l2 = True :- False :- True :- True :- Nil
λ> :t l2
l2 :: Liste Bool
\end{lstlisting}


et même des listes de listes !

\begin{lstlisting}
λ> let a1 = 1 :- 2 :- Nil
λ> let a2 = 3 :- 4 :- Nil
λ> let a3 = 5 :- 6 :- Nil
λ> let bigA = a1 :- a2 :- a3 :- Nil
λ> :t bigA
bigA :: Liste (Liste Integer)
\end{lstlisting}










\section{Application, composition et priorité des fonctions}

\subsection*{La fonction map}
 
La   fonction   \lstinline{map}   est   extrêmement   utile   en   programmation
fonctionnelle.

Son  type est  le suivant:  \lstinline{map ::  (a  -> b)  -> [a]  -> [b]}.  Elle
consiste à \textit{appliquer} (map en anglais of spécialité) une fonction à tous
les éléments d'une liste.

Par exemple, pour ajouter 3 à tous les éléments d'une liste d'entiers:

\begin{lstlisting}
λ> map (\ x -> x + 3) [1..10]
[4,5,6,7,8,9,10,11,12,13]
\end{lstlisting}

ou plus simplement:

\begin{lstlisting}
λ> map (+ 3) [1..10]
[4,5,6,7,8,9,10,11,12,13]
\end{lstlisting}

\subsection*{Priorité et opérateur \$}

Nous avons  également vu des  règles de  priorité. Par exemple  l'application de
fonction est prioritaire sur les opérateurs:

\begin{lstlisting}
λ> abs 3 - abs 5
-2
λ> (abs 3) - (abs 5)
-2
λ> abs (3 - abs 5)
2
\end{lstlisting}



Nous  avons également  vu que  l'application des  fonctions était  associative à
gauche, ce qui signifie que \lstinline{f x y z} est équivalent à
 \lstinline{((f x) y) z}.

Cela oblige parfois à avoir recours aux parenthèse. Par exemple, si nous voulons
calculer la racine carrée de la somme des carrés des entiers de 1 à 10:


\begin{lstlisting}
λ> sqrt (sum (map (^2) [1..10]))
19.621416870348583
\end{lstlisting}

Si on ne met pas de parenthèses:

\begin{lstlisting}
λ> sqrt sum map (^2) [1..10]

<interactive>:26:10-12:
    Couldn't match expected type `[(a1 -> a1) -> [t1] -> t0]'
                with actual type `(a0 -> b0) -> [a0] -> [b0]'
    In the second argument of `sqrt', namely `map'
    In the expression: sqrt sum map (^ 2) [1 .. 10]
    In an equation for `it': it = sqrt sum map (^ 2) [1 .. 10]
\end{lstlisting}


Mais toutes ces parenthèses, c'est un peu pénible. Pour aérer un peu le code, il
existe un opérateur un peu spécial, \lstinline{$} %$ 
qui est juste là pour appliquer l'opérande de gauche à l'opérande de droite:

\begin{lstlisting}
infixr 0 $
($) :: (a -> b) -> a -> b
f $ x = f x
\end{lstlisting}

ouais bof...Mais attention, le niveau de priorité de \lstinline{$}%$ 
est le  plus bas qui  soit. Il agit donc  comme un retardateur  d'application ou
plus techniquement, il  transforme l'associativité à gauche  de l'application en
associativité à droite: \lstinline{f $ g $ h x= f (g (h x))}.


Pour en revenir à notre racine carrée de somme de carrés, on aurait pu écrire:

\begin{lstlisting}
λ> sqrt $ sum $ map (^2) [1..10]
19.621416870348583
\end{lstlisting}

Concrètement, le \lstinline{$} %$
revient à ouvrir une parenthèse et à la fermer à la fin de l'expression.

\begin{recherche}
  Quelle est la valeur de:

  \begin{lstlisting}
map ($ 4) [(5 -), (^ 2), (div 17)]
  \end{lstlisting}
\end{recherche}


En résumé:

\begin{NB}
  \lstinline{$}{}\ %$ 
appelle son argument de gauche (qui est une fonction) sur son argument de droite
(qui est une valeur)

\end{NB}


\subsection*{Composition de fonctions}

Vous avez vu au lycée l'opérateur de composition des fonctions:

Avec $ g\colon A \to B$ et $ f\colon B \to C$.

$$ f \circ g~\colon x\mapsto f \bigl( g(x) \bigr)$$

Sur Haskell, c'est pareil:

\begin{lstlisting}
infixr 9 .
(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)
\end{lstlisting}

\begin{DANGER}
Il faut faire très attention à la signature de type des fonctions à composer!
\end{DANGER}


Par exemple,  la fonction \lstinline{words}  appliquée sur une  chaîne contenant
des espaces renvoie la liste des chaînes découpées selon les espaces:

\begin{lstlisting}
λ> words "vos beaux yeux d'amour belle mourir me font Marquise"
["vos","beaux","yeux","d'amour","belle","mourir","me","font","Marquise"]
\end{lstlisting}

On voudrait connaître la longueur du mot le plus long de cette liste.


On dispose des fonctions  \lstinline{length} et \lstinline{maximum} qui calculent
la longueur et l'élément maximum d'une liste d'éléments \og ordonables\fg{}.

On vérifie bien les types:

\begin{lstlisting}
λ> :t words
words :: String -> [String]
λ> :t length
length :: [a] -> Int
λ> :t maximum
maximum :: Ord a => [a] -> a
\end{lstlisting}


Ce qui donne point de vue type:

$$\mathtt{String}         \xrightarrow{\mathtt{words}}         \mathtt{[String]}
\xrightarrow{\mathtt{map\ length}} \mathtt{[Int]} \xrightarrow{\mathtt{maximum}} \mathtt{Int}$$

Point de vue expressions:

$$\mathtt{s} \xrightarrow{\mathtt{words}} \mathtt{words\ s}
\xrightarrow{\mathtt{map\    length}}    \mathtt{map\     length\    (words\    s)}
\xrightarrow{\mathtt{maximum}} \mathtt{maximum\ (map\ length\ (words\ s))}$$


En compressant:

$$\mathtt{String}   \xrightarrow{\mathtt{words \,  . \,  (map\  length\,   .\,   maximum)}}
\mathtt{Int}$$

ou plus simplement, sachant que la compression est associative à droite:


$$\mathtt{String}   \xrightarrow{\mathtt{words \,  . \,  map\  length\,   .\,   maximum}}
\mathtt{Int}$$



\begin{lstlisting}
λ> let longMotPlusLong = maximum . map length . words
λ> :t longMotPlusLong
longMotPlusLong :: String -> Int
λ> longMotPlusLong "Vos beaux yeux d'amour mourir me font"
7
\end{lstlisting}

Les trois expressions suivantes désignent la même fonction:

\lstinline{maximum . map length . words} 

\lstinline{\s -> maximum (map length (words s))} 

\lstinline{\s -> maximum $ map length $ words s} 

\section{Raisonnement par récurrence}


Souvenez-vous du test vu dans une section précédente: \og si $n$ est
pair alors son successeur est premier\fg{}.

Pourquoi a-t-on rajouté  les nombres impairs à  l'ensemble des entiers
rendant cette proposition vraie?

Parce que $A\limp B$ est toujours vraie sauf dans le cas $A$ est vraie et
$B$ est fausse. En particulier $A\limp B$ reste vraie quand $A$ est
fausse.


Ceci  est   primordial  dans  la  démonstration   par  récurrence,  en
particulier dans le preuve de l'hérédité.

Soit $P_n$ une proposition dépendant d'un entier $n$.

On démontre l'hérédité $P_n\limp P_{n+1}$  en utilisant le théorème de
la déduction mais  le fait que $P_n\limp P_{n+1}$  soit vraie n'assure
pas que $P_n$ le soit.

Il faut de plus s'assurer que la propriété est vraie au moins une fois.

Ce type de raisonnement n'est  donc pas une escroquerie comme certains
élèves le pensent trop souvent: \og  ah oui, on suppose que c'est vrai
au rang $n$ et on en déduit que c'est vrai au rang $n$...\fg{}.


\subsection*{Récursion, récurrence, induction}



...des mots  qui tournent autour du même
thème mais qu'il faut savoir distinguer.

L'\textit{induction}  consiste   à  conclure  à   partir  d'observations
préalables: cela correspond à  la démarche expérimentale classique. Sans
précautions, cela peut conduire  à certaines contre-vérités. Par exemple
3, 5 et 7 sont premiers  donc on pourrait en déduire, par induction, que
tous les nombres impairs à partir de 3 sont premiers et pourtant...


L'\textit{induction    mathématique}    ou   \textit{raisonnement    par
récurrence} corrige  ce défaut. On  part toujours d'un  résultat observé
mais on  \textit{démontre} qu'il  est vrai pour  tous les  éléments d'un
ensemble donné,  éventuellement infini. C'est  l'induction expérimentale
corrigée par la rigueur du raisonnement mathématique.

En  informatique, une  \textit{fonction récursive}  (ou  un \textit{type
récursif})  est  une  fonction  (ou   un  type)  qui  fait  référence  à
elle(lui)-même  dans sa définition.  Ce mécanisme  est très  puissant et
permet de condenser l'écriture d'un programme.


\smallskip

C'est  l'induction mathématique  qui
nous   intéresse    ici.   Rappelons
quelques principes.


Pour prouver qu'une  propriété $\PR_n$  dépendant uniquement
d'un paramètre $n$ est vraie pour tout $n \geqslant n_0$, il faut
vérifier que:

\begin{itemize}
\item $\PR_{n_0}$ est vraie (on parle parfois d'initialisation);
\item  pour tout  $n \geqslant  n_0$, $\PR_n  \limp \PR_{n+1}$
  (on parle parfois d'hérédité).
\end{itemize}


Quand on a  besoin de supposer que non seulement  la propriété est vraie
pour  un certain  $n$ mais  aussi  pour tous  les entiers  qui lui  sont
inférieurs (pas  seulement le  père mais aussi  tous les  ascendants) on
parle alors de \textit{récurrence forte}.



\subsection*{Un jeu}



\pro L'été dernier, lors de la visite d'un musée, j'ai, pour une fois, impressionné mes
enfants en résolvant devant eux très rapidement le problème suivant:


%\begin{figure}
\begin{center}
  \includegraphics[angle=-1,scale=2]{hanoi3}
\end{center}
%\end{figure}


Ce casse-tête a été posé  par le  mathématicien
français Édouard \textsc{Lucas} en 1883.

Le  jeu  consiste  en  une  plaquette  de bois  où  sont  plantés  trois
piquets. Au  début du jeu, 4  disques de diamètres croissant  de bas en
haut sont placés  sur le piquet de  gauche. Le but du jeu  est de mettre
ces disques dans le même ordre sur le piquet de droite en respectant les
règles suivantes:

\begin{itemize}
\item on ne déplace qu'un disque à la fois;
\item on ne peut poser un disque que sur un disque de diamètre supérieur.
\end{itemize}

Je vous propose donc de jouer vous aussi avec moi...

\iutxap{pauvres enfants,  passer des  vacances avec  un prof  de maths,  vois le
  cauchemar} Oh, comme je suis content!

\pro Essayez d'abord avec 2 puis 3 disques.


\iutx  Bon, avec  deux, je  mets  le disque  là puis  l'autre là-bas  et
ensuite celui-ci ici. Ça marche.  Avec trois, je bouge celui-là, et puis
l'autre, celui-ci ici,  l'autre là, puis celui-là là  et l'autre là puis
le  dernier ici.  Ah,  c'est pas  le bon  piquet  mais ça  marche à  peu
près. Facile votre jeu.


\pro Alors essayez avec quatre, cinq, autant de disques que vous voulez.

\medskip

{\itshape Quelques minutes plus tard}

\iutx Pénible votre jeu!

\pro Les  choses se compliquent.  Il est temps  de parler de  la légende
rapportée par \textsc{ Lucas} dans ses \og \textit{récréations mathématiques}\fg{}:

\begin{quote}
  \textit{N. Claus de Siam a vu, dans ses voyages pour la publication des écrits
de  l'illustre  Fer-Fer-Tam-Tam,  dans   le  grand  temple  de  Bénarès,
au-dessous du  dôme qui  marque le centre  du monde, trois  aiguilles de
diamant,  plantées  dans une  dalle  d'airain,  hautes  d'une coudée  et
grosses comme  le corps  d'une abeille. Sur  une de ces  aiguilles, Dieu
enfila au commencement  des siècles, 64 disques d'or  pur, le plus large
reposant  sur  l'airain,  et  les  autres,  de  plus  en  plus  étroits,
superposés  jusqu'au sommet.  C'est la  tour sacrée  du Brahmâ.  Nuit et
jour, les  prêtres se  succèdent sur les  marches de l'autel,  occupés à
transporter  la tour  de la  première  aiguille sur  la troisième,  sans
s'écarter des  règles fixes que nous  venons d'indiquer, et  qui ont été
imposées  par Brahma.  Quand  tout sera  fini,  la tour  et les  brahmes
tomberont, et ce sera la fin des mondes !}
\end{quote}



C'est un problème  posé par un mathématicien mais  nous allons l'étudier
en \emph{informathicien}. Nous voudrions répondre à plusieurs questions:
\begin{itemize}
\item peut-on résoudre le problème des 64 disques?
\item si oui, en combien de mouvements?
\item peut-on trouver une tactique la plus efficace possible?
\item est-ce que la fin du monde est pour bientôt?
\end{itemize}

Au lieu  d'étudier des  cas séparés, nous  allons généraliser un  peu et
considérer une  tour avec $n$ disques,  $n$ étant un  entier naturel non
nul.


\iutx Cela va compliquer les choses. Pourquoi ne pas s'en tenir à un cas
précis? C'est une perversion de mathématicien.

\pro Détrompez-vous!  Au lieu d'étudier un  à un des cas  isolés, il est
bon pour  un informaticien  aussi de voir  qu'un programme  plus général
pourra traiter tous les cas.  Cependant, il sera utile d'étudier des cas
simples d'abord pour se donner une idée. 

Après une rapide exploration avec papier et crayon, il est temps pour un
\emph{informathicien} d'introduire des notations adéquates. 

Notons  $M_n$  le  nombre  minimum  de mouvements  pour  transférer  $n$
disques. Pouvez-vous donner les premières valeurs de $M_n$?

\iutx Bon, s'il  n'y a qu'un disque, on ne pourra  pas faire mieux qu'un
déplacement: $M_1=1$. Avec deux disques, hop, hop, hop: trois mouvements;
$M_2=3$. Pour  trois, j'avais trouvé  sept déplacements mais je  ne suis
pas sûr que ça soit la meilleure solution.

\pro  C'est  ce  que nous  allons  prouver  mais  tout d'abord,  en  bon
mathématicien, rajoutons un cas extrême: s'il y a zéro disque, il faudra
zéro mouvement.

\iutx C'est un peu tiré par les cheveux.

\pro  Mais  considérer les  cas  les  plus  triviaux permet  souvent  de
simplifier le cas général. Il est temps d'ailleurs de voir grand mais il
nous  faudrait une  idée. Essayons  de  trouver des  points communs  aux
déplacements de deux et trois disques respectivement. 

\iutx Ben, je mets le petit sur  le piquet du milieu, le grand sur celui
d'arrivée puis le petit sur ce même piquet d'arrivée.

\pro  Pour trois  c'est pareil:  je mets  les deux  petits sur  celui du
milieu, le grand sur celui d'arrivée  puis les deux petits par dessus le
grand.

\iutx Vous trichez! Vous avez bougé deux disques en même temps.

\pro En fait, j'ai vu que  je savais bouger deux disques d'un piquet vers
un autre. Cela me demande trois étapes qui se cachent derrière le \og\textit{je mets  les deux  petits sur  celui du
milieu} \fg{}.

Cela nous  donne en  fait la  solution: avec $n+1$  disques, je  bouge les
$n$ plus petits sur le piquet du milieu ($M_{n}$ mouvements), je bouge le plus grand sur le
piquet d'arrivée (1 mouvement) puis je redéplace les $n$ petits sur le
grand ($M_{n}$ mouvements). Ainsi:

$$M_{n+1} \leqslant 2M_n+1$$

\iutx Pourquoi avoir utilisé $\leqslant $ et non pas $=$? Et puis, on ne
connaît pas $M_n$.

\pro Vous touchez du doigt deux problèmes essentiels qui vont guider bon
nombre de nos raisonnements. 

Pour  le $\leqslant $,  il est  essentiel de  comprendre que  nous avons
prouvé que $2M_n+1$ mouvements  étaient \textbf{suffisants} mais nous ne
savons    toujours    pas    si    ces    $2M_n+1$    mouvements    sont
\textbf{nécessaires}. C'est très important de comprendre la différence.

Par exemple, pour acheter un chocolat chaud à la cafétéria et l'offrir à
son professeur adoré, il est \textbf{suffisant} d'avoir 10 euros dans sa
poche   mais   ce   n'est   pas   nécessaire.    Inversement,   il   est
\textbf{nécessaire}  d'avoir   au  moins  20  centimes   mais  ce  n'est
malheureusement pas suffisant.

Nous avons étudié cela en détail dans un précédent chapitre sur la logique.

\begin{NB}
On  considère P  et Q  deux propositions  (des énoncés,  des  faits, des
formules).

\begin{itemize}
\item Q est une \textbf{condition nécessaire} pour avoir P si, dès que P
  est  vraie,  alors nécessairement,  forcément,  obligatoirement, Q  est
  vraie. On note souvent $P \limp Q$.
\item Q est  une \textbf{condition suffisante} pour avoir  P s'il suffit
  que  Q  soit  vraie  pour  que  P soit  vraie.   On  note  souvent  $P
  \limp Q$.
\item  Lorsque  P  est  à  la fois  condition  nécessaire  et  condition
  suffisante de Q, on dit  que P est une \textbf{condition nécessaire et
    suffisante} de Q ou encore  que P est vraie \textbf{si, et seulement
    si,} Q est vraie. On note souvent $P \lequiv Q$.
\end{itemize}

Lorsque qu'une \og affirmation\fg{} du  type $P \lequiv Q$ ou $P
\lequiv Q$ est vraie, on dit que c'est un \textbf{théorème}.
\end{NB}

Nous avons développé des méthodes de preuve dans un chapitre précédent.

Revenons tout d'abord à nos disques. Peut-on faire mieux que la solution
proposée?

À un moment donné, il \textit{faut}  bien bouger le plus grand disque puisqu'il
est sur le mauvais piquet. Il \textit{faut}  donc qu'il soit tout seul et il \textit{faut}
donc avoir  bougé auparavant  les $n$ autres  disques plus  petits. Cela
\textit{nécessite} \textit{au minimum}  $M_n$ mouvements. Après cela, on
peut bouger  le grand disque  autant de fois  qu'on le désire mais  à un
moment donné,  il \textit{faudra} le  placer sur le piquet  d'arrivée et
déplacer  les  $n$  autres  disques  sur  le  piquet  d'arrivée  ce  qui
\textit{nécessite} à nouveau $M_n$ mouvements. 

Ainsi, il \textit{faudra au minimum} effectuer $2M_n+1$ mouvements.

On a donc prouvé que:

$$M_{n+1}\geqslant 2M_n+1$$

Il  est donc  \textbf{nécessaire} d'effectuer  $2M_n+1$  mouvements pour
déplacer  les $n+1$  disques. Or  nous avons  montré auparavant  que ces
$2M_n+1$ mouvements étaient \textbf{suffisants}. On en déduit donc que:


$$
\begin{cases}
  M_0=0\\
  M_{n}=2M_{n-1}+1 \text{ pour tout } n>0
\end{cases}
$$


Est-ce que cette formule marche bien avec nos premiers exemples?

\iutx  $M_1=2\cdot 0+1=1$:  OK. $M_2=2\cdot  1+1=3$:  OK. $M_3=2\cdot
3+1=7$: OK.

\pro Ça ne prouve pas grand  chose mais ça nous rassure. De toute façon,
nous avons prouvé que cette formule est bonne. Que vaut $M_{64}$?

\iutx  Ben $M_{64}=2M_{63}+1$.  Le problème,  c'est qu'on  ne  connaît pas
$M_{63}$.

\pro  Et   oui:  on  définit  la  \textit{suite}   \textbf{M}  à  partir
d'elle-même, ce qui  n'est pas très pratique. On dit  qu'on a définit la
suite par \textbf{récurrence}.  Vous  verrez cette année en informatique
que  ce mode  de  calcul n'est  pas  réservé aux  suites  que vous  avez
peut-être  étudiées  au  lycée.  Par  exemple,  en  langage  formel,  on
travaille avec les  lettres d'un alphabet. On peut  alors définir un mot
comme étant soit le vide, soit une lettre suivi d'un mot.

\iutx C'est un peu  idiot: en fait, vous me dites que  pour savoir si un
truc est un mot, faut déjà savoir si c'est un mot.

\pro Vous n'êtes  pas assez précis. Prenons notre  alphabet et la chaîne
de caractères \og math\fg{}.  C'est le vide suivi de la chaîne \og math\fg{} qui
est la lettre \og m\fg{} suivie de la
chaîne \og ath\fg{} qui est la lettre \og a\fg{} suivie de la chaîne \og
th\fg{} qui est la lettre \og  t\fg{} suivie de la lettre \og h\fg{} qui
est un  mot puisque c'est une  lettre. En remontant, on  obtient que \og
th\fg{} est  un mot puis que  \og ath\fg{} aussi et  enfin \og math\fg{}
est donc un mot.

\iutxap{Ben  on le savait  avant. Si  c'est ça  c'qu'on apprend  à l'IUT
  d'info, il est peut-être encore temps de m'inscrire en GEA.}
Fabuleux! Math est un mot! J'aurais pas cru, comme ça, a priori.

\pro Ah, comme quoi ce que nous faisons est utile.

\iutxap{Complètement gâteux le gars} Je n'en doute pas.

\pro  Et la  fin du  monde  dans tout  ça? Pour  connaître $M_{64}$,  il
semblerait qu'il faille connaître tous les $M_k$ précédents.

Voyons voir, calculez jusqu'à $M_6$.

\iutx Si vous voulez:
\begin{itemize}
\item $M_3=2\cdot 3+1=7$;
\item $M_4=2\cdot 7+1=15$;
\item $M_5=2\cdot 15+1=31$;
\item $M_6=2\cdot 31+1=63$;
\end{itemize}

Ouais, bof. Je ne vois pas trop où ça nous mène.


\pro  \og  \textit{Ils ont  des  yeux et  ils  ne  voient pas}\fg{}.  Et
pourtant, quand  j'étais jeune, un enfant  de six ans  aurait reconnu la
suite:

$$2^3-1,\ 2^4-1,\ 2^5-1, \ 2^6-1,...$$

\iutxa{Ben  tiens!  Les   puissances  à  6  ans  et   pourquoi  pas  les
  logarithmes à 7.}


\pro Vous dites? 

\iutx Je réfléchissais.

\pro Ah. Alors, vous avez sûrement envie de dire que tout prête à croire
que:

$$M_n=2^n-1, \text{ pour tout entier strictement positif } n$$

\iutx Ben oui,  c'est vrai au début donc  y a pas de raison  pour que ça
s'arrête.

\pro  Encore  faudrait-il  le   prouver.  Par  exemple,  est-ce  que  la
proposition suivante est un théorème: 

\begin{center}
  \textit{Les entiers impairs supérieurs à 3 sont tous des nombres premiers.}
\end{center}

\iutx 3 est premier, 5 est premier, 7 est premier...

\pro...donc c'est vrai! 

\iutx Ben  non. 9  est impair mais  n'est pas premier...Ouais,  OK, j'ai
compris.

\pro  \og Vrai  pour  les premiers,  vrai  pour tous\fg{}  n'est pas  un
théorème! Vous retiendrez également que...


\begin{NB}

 Pour prouver qu'une proposition
n'est pas un théorème, il suffit d'exhiber un \textbf{contre-exemple}.
\end{NB}

Nous en avons déjà parlé.  Revenons à notre récurrence ou
induction.  


\begin{NB}
Pour prouver qu'une  propriété $\PR_n$  dépendant uniquement
d'un paramètre $n$ est vraie pour tout $n \geqslant n_0$, il faut
vérifier que:

\begin{itemize}
\item $\PR_{n_0}$ est vraie (on parle parfois d'initialisation);
\item  pour tout  $n \geqslant  n_0$, $\PR_n  \limp \PR_{n+1}$
  (on parle parfois d'hérédité).
\end{itemize}
\end{NB}

Cela peut  par exemple se  prouver en \textit{raisonnant  par l'absurde}
comme nous l'avons déjà vu.

Ici,  pour  tout   entier  naturel  non  nul  $n$,   notons  $\PR_n$  la
proposition: $M_n=2^n-1$.

Cette proposition est vraie pour $n=1$ puisque $M_1=1=2^1-1$.


Il existe  donc au moins un entier  naturel non nul $k$  tel que $\PR_k$
soit vraie. 

Alors $M_{k+1}=2M_k+1=2(2^k-1)+1=2\cdot 2^k-2+1=2^{k+1}-1$.

Ainsi $\PR_k \limp \PR_{k+1}$ pour tout entier naturel non nul
$k$.

Le tour est joué. On peut donc affirmer que $M_n=2^n-1$ pour tout entier
naturel non nul $n$. 

\iutx       Donc       $M_{64}=2^{64}-1$.        Je      prends       ma
calculatrice...$M_{64}=\numprint{18446744073709551615}$. Ça ne m'arrange
pas tellement pour connaître la date de la fin du monde.

\pro  C'est  pourtant simple.  Disons  que  les  moines sont  très  bien
entraînés et se relaient efficacement. Ils déplacent alors un disque par
seconde. Cela nous donne une durée de jeu de...


\iutx              Ah,              ça             je              sais:
$\numprint{18446744073709551615}/\numprint{3600}/24/365,25/100$ ce qui fait en gros
$\numprint{5.8}$ milliards de siècles...

\pro  Et  comme  l'Univers  a   grosso  modo  140  millions  de  siècles
d'existence, cela nous laisse de la marge.

\iutx  Ouf! Mais  cela ne  nous indique  pas comment  déplacer  les huit
disques du  jeu initial. On sait  juste qu'en étant  aussi efficaces que
les moines, cela nous
prendra $M_8=2^8-1=255$ secondes.

\pro Je vous laisse donc cinq minutes pour le faire.

\medskip

\textit{Cinq minutes plus tard}

\medskip

\iutx Il  faut se  rendre à l'évidence:  je ne  suis pas fait  pour être
moine. Faut le faire pour chaque  $n$ jusqu'à 8 en fait et noter comment
on a fait. Pfff... C'est pénible.

\pro Et quand  un informathicien a bien réfléchi sur  le papier, il peut
laisser faire  le sale boulot  à la machine.  On a en effet  une méthode
qu'on sait être correcte. Mais il est très difficile de l'appliquer pour
un grand $n$ donné.  On sait que ça marche mais on  ne sait pas vraiment
comment ça marche. Et c'est  là qu'une programmation bien pensée devient
merveilleusement  efficace.  Si on  a  à  notre  disposition un  langage
sachant traiter  la récursion,  il va suffire  de lui donner  un minimum
d'instruction.

Rappelons ici notre méthode:  avec $n+1$  disques, je  bouge les
$n$ plus petits sur le piquet du milieu ($M_{n}$ mouvements), je bouge le plus grand sur le
piquet d'arrivée (1 mouvement) puis je redéplace les $n$ petits sur le
grand ($M_{n}$ mouvements). 


Illustrons notre propos avec le langage  Haskell   qui aime les récursions.

L'opérateur \verb|++| concatène  des listes donc aussi des chaînes  qui sont des
listes de caractères:

\begin{lstlisting}
*Main> :t (++)
(++) :: [a] -> [a] -> [a]
*Main> [1,2,3] ++ [4]
[1,2,3,4]
*Main> "Raahhh" ++ " lovely"
"Raahhh lovely"
\end{lstlisting}


On traite les deux cas, un ou $n$ disques:

\begin{lstlisting}
hanoi ::  String -> String -> String -> Int -> String
-- On nomme les trois piquets sous forme de chaînes. 
-- On obtient la liste des mouvements sous forme d'une chaîne.
-- On déplace n disques de dep vers but en se servant de piv comme pivot.
hanoi dep but piv 1 = 
  -- 1 disque : renvoie la chaîne décrivant le mvt de dep vers but
  "De " ++ dep ++ " vers " ++ but ++ "\n"
hanoi dep but piv n = 
  -- n disques :
  (hanoi dep piv but (n - 1)) ++ --  on bouge n-1 disques de dep vers piv
  (hanoi dep but piv 1) ++ -- on bouge le gros disque de dep vers but
  (hanoi piv but dep (n - 1)) -- on bouge le n-1 disques du piv vers but
\end{lstlisting}


On affiche joliment le résultat:

\begin{lstlisting}
-- on affiche le résultat 
tours_hanoi :: Int -> IO ()
tours_hanoi n = putStrLn ( hanoi "Tige 1" "Tige 2" "Tige 3" n)
\end{lstlisting}


Ce qui donne pour trois disques:

\begin{lstlisting}
λ> tours_hanoi 3
De Tige 1 vers Tige 2
De Tige 1 vers Tige 3
De Tige 2 vers Tige 3
De Tige 1 vers Tige 2
De Tige 3 vers Tige 1
De Tige 3 vers Tige 2
De Tige 1 vers Tige 2
\end{lstlisting}


et  si l'on  veut  obtenir le  nombre  de mouvements  pour déplacer  de  1 à  20
disques, on change un peu le code:

\begin{lstlisting}
nb_hanoi :: Int -> Int
nb_hanoi 1 = 1
nb_hanoi n = 2 * (nb_hanoi (n-1)) + 1

λ> [nb_hanoi k | k <- [1..20]]
[1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535,131071,262143,
 524287,1048575]
\end{lstlisting}


\iutx Waouh! Ça je préfère.

\pro Je  n'en doute pas,  mais pour y  arriver, il faudra passer  par le
stade \og réflexion mathématiquement assistée avec papier-crayon\fg{}

\section{Prouver que deux fonctions sont équivalentes}

Deux fonctions sont  équivalentes si elles ont  le même type de  départ, le même
type d'arrivée  et le même graphe,  i.e. si, appliquées au  même argument, elles
donnent la même valeur.

Considérons deux fonctions simples:

\begin{lstlisting}
f1 :: [Int] -> [Int]
f1    []     = []
f1    (k:ks) = abs k : f1 ks

f2 :: [Int] -> [Int]
f2 = map abs
\end{lstlisting}

Sont-ce les mêmes fonctions?

Regardons   la    définition   de    \lstinline{map}   dans    la   bibliothèque
\lstinline{Data.List}:

\begin{lstlisting}[caption={Extrait de Data.List}]
-- map f xs is the list obtained by applying f to each element of xs, i.e.,
-- map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn]
-- map f [x1, x2, ...] == [f x1, f x2, ...]
map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs
\end{lstlisting}


Nous allons démontrer  ce résultat par récurrence (ou induction:  du simple vers
le compliqué).

On commence par traiter le cas simple: l'argument est la liste vide.

{\ttfamily
f1 []
 
=> []         {définition de f1}

=> map abs [] {définition de map}

=> f2 []      {défintion de f2}
}

Nous pouvons donc supposer que \lstinline{f1 ks  = f2 ks} pour une certaine liste
\lstinline{ks} et nous allons essayer de démontrer que 
\lstinline{f1 (k:ks) = f2 (k:ks)} pour n'importe quel entier \lstinline{k}.

f1 (k:ks)

{\ttfamily
f1 (k:ks)

=> abs k : f1 ks      {définition de f1}

=> abs k : f2 ks      {hypothèse de récurrence}

=> abs k : map abs ks {définition de f2}

=> map abs (k:ks)     {définition de map}

=> f2 (k:ks)          {définition de f2}
}

Et voilà...
 




\vfill
\eject
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\modeexercice
\section{RECHERCHES}


\begin{exercice}[Ensembles à partir de fonctions]
On définit des ensembles par compréhension:

\begin{lstlisting}
module EnsembleCompréhension where

    type Element  = Int
    type Predicat = Element -> Bool
    data Ensemble = Ens (Predicat)
\end{lstlisting}
  
On utilisera un  petit \textit{truc} pour afficher joliment les  listes et faire
un teste de vacuité:

\begin{lstlisting}
  mini,maxi  :: Element
 (mini,maxi) = (-128,127)
 
 listeUnivers :: [Element]
 listeUnivers =  [mini .. maxi]
 
 listeVersEns :: Ensemble -> [Element]
 listeVersEns    (Ens f)  =  [x | x <- listeUnivers, f x]
 
 instance  Show Ensemble where
    show = show . listeVersEns
\end{lstlisting}


Pour le reste, c'est à vous de jouer:

\begin{lstlisting}
contient :: Ensemble -> Element -> Bool
 
univers :: Ensemble
    
insere :: Element -> Ensemble -> Ensemble
    
union ::  Ensemble -> Ensemble -> Ensemble
    
inter ::  Ensemble -> Ensemble -> Ensemble
    
filtre :: Predicat -> Ensemble -> Ensemble
    
complementaire :: Ensemble -> Ensemble
   
difference :: Ensemble -> Ensemble -> Ensemble
                          
estInclus :: Ensemble -> Ensemble -> Bool
    
estEgal :: Ensemble -> Ensemble -> Bool
        
pourTous :: Predicat -> Ensemble -> Bool
   
ilExiste :: Predicat -> Ensemble -> Bool
\end{lstlisting}

\end{exercice}




\begin{exercice}[Puissance]
  Écrivez la fonction carré d'au moins quatre façons différentes.
\end{exercice}

\begin{exercice}[Double]
  
Définissez une  fonction qui  prend une  fonction d'un  argument en  argument et
retourne une focntion qui applique l'argument deux fois. (N'oubliez pas les signatures!)

Par exemple,  si \lstinline{suiv} est  la fonction qui  a un entier  associe son
successeur, alors \lstinline{double suiv} sera la  fonction qui à un entier $ x$
associe $x+2$.



Quelle est la valeur retournée par \lstinline{(double (double double)) suiv 5}? 




\end{exercice}

\begin{exercice}[Composition itérée]
  
Déterminez une fonction qui prend une fonction f et un naturel n en argument et
retourne composée n fois de f.
o
Vous obtiendrez par exemple:

\begin{lstlisting}
λ> (compRep suiv 0) 5
5
λ> (compRep (^2) 2) 5
625
\end{lstlisting}
\end{exercice}


\begin{exercice}[Comparatif]
  
Écrivez une fonction qui, étant donnée une liste d'entiers, calcule la somme des
nombres  pairs de  cette liste,  puis une  autre calculant  la somme  des carrés
pairs. (Une demi-ligne devrait suffire).

En C on pourrait faire ça:

\ce

\begin{lstlisting}
int evenSum(int *list) {
    return accumSum(0,list);
}

int accumSum(int n, int *list) {
    int x;
    int *xs;l
    if (*list == 0) {
        return n;
    } else {
        x = list[0]; 
        xs = list + 1; 
        if ( 0 == (x%2) ) { 
            return accumSum(n+x, xs);
        } else {
            return accumSum(n, xs);
        }
    }
}
\end{lstlisting}

\haskell

\end{exercice}

\begin{exercice}[Opérateurs logiques]
Nous allons  reprendre notre travail  sur les  opérateurs logiques (qui  sont la
base de l'architecture  de la machine). Nous allons cette  fois utiliser le type
\lstinline{Bool} primitif afin de pouvoir profiter des diverses constructions de
fonctions vues en cours.

\begin{enumerate}
\item Commencer  par construire des  fonctions \og  et\fg{}, \og ou\fg{}  et \og
  non\fg{}. 

Comme  nous  allons  créer  pas  mal d'opérateurs  binaires  booléens,  on  peut
commencer par créer un synonyme pour clarifier le code:


\begin{lstlisting}
module Logique where

    -- type : crée un type synonyme pour rendre le code plus clair à lire 
    type OpBinaire = (Bool -> Bool -> Bool)
\end{lstlisting}

  Enseuite, par exemple, pour reprendre ce qui a été fait en cours:

  \begin{lstlisting}
    -- ET logique
    et :: OpBinaire
    et    True = \ x   -> x
    et    _    = \ _   -> False
  \end{lstlisting}

\item   Créez   de   même   le  ou   exclusif   \lstinline{ouex},   l'implication
  \lstinline{==>} et l'équivalence \lstinline{<==>}.



\item Qu'est-ce que c'est?

  \begin{lstlisting}
    lesBool :: [Bool]
    lesBool = [False, True]
    
    tabVer :: OpBinaire -> [Bool]
    tabVer op = [ [ op x y | x <- lesBool] |  y <- lesBool ]
  \end{lstlisting}

  Comment définiriez-vous l'égalité de deux opérateurs logiques?

\item  Vérifiez à  l'aide de  ces  fonctions, que  pour tout  couple $(x,y)$  de
  booléens:
  \begin{enumerate}
  \item \lstinline{non (x `et` y) = (non x)  `ou`  (non y)}
  \item \lstinline{non (x `ou` y) = (non x) `et` (non y)}
  \end{enumerate}
  On appelle ces résultats les \textit{lois de \textsc{De Morgan}}.

\item  Exprimez   tous  les  opérateurs   précédents  (ou , ouex, \lstinline{==>}, \lstinline{<==>}) uniquement  à   l'aide  de
  \lstinline{et} et \lstinline{non}. 

  On note habituellement \og nand\fg{} l'opérateur vérifiant:

  \begin{lstlisting}
λ> tabVer nand
[[True,True],[True,False]]
  \end{lstlisting}

Pourquoi pourriez-vous  construire l'unité arithmétique d'un  ordinateur avec un
lot de circuits \og nand\fg{}?

\item Est-ce que l'implication est associative?


\end{enumerate}

\end{exercice}








\begin{exercice}[Moyenne olympique]
  \begin{enumerate}
  \item  Décrire une fonction qui étant donnés quatre flottants leur associe la moyenne
  des deux  nombres parmi les  quatre qui ne  sont ni le  plus grand ni  le plus
  petit. Par exemple, la moyenne olympique de 10, 8, 12 et 14 est 11 et celle de
  12, 12, 12 et 12 est 12.
\item  Décrire une fonction qui étant donnée une liste d'au moins quatre nombres leur associe la moyenne
  des nombres parmi ceux de la liste qui ne sont ni le plus grand ni le plus
  petit. Par exemple, la moyenne olympique de 15, 7, 10, 8, 12 et 14 est 11.
  \end{enumerate}
\end{exercice}


\begin{exercice}[Machine polonaise]
  Étudiez avec la plus grande attention ce tutoriel:

  \href{http://lyah.haskell.fr/resoudre-des-problemes-fonctionnellement\#calculatrice-de-notation-polonaise-inverse}{http://lyah.haskell.fr/resoudre-des-problemes-fonctionnellement\#calculatrice-de-notation-polonaise-inverse}


Puis  créez une  fonction qui  lit  une expression  infixe et  la transforme  en
expression NPI et inversement.
\end{exercice}




\begin{exercice}[dérivateur formel]

Vous avez passé des  mois à dériver des fonctions au  lycée. Nous allons essayer
de créer  un dérivateur formel  (suffisant du point  de vue calul  mais basique
point de vue affichage).

On part de ça:

\begin{lstlisting}
module Derivation where

type Nombre   = Float
    
data Fonction   =
    Const Nombre
        | Id        String
        | Add       Fonction Fonction 
        | Mul       Fonction Fonction 
        | Inv       Fonction  
        | Pow Float Fonction  
        | Racine    Fonction  
        | Ln        Fonction  
        | Exp       Fonction  
        | Cos       Fonction  
        | Sin       Fonction  
    deriving (Eq)

montre :: Fonction -> String
montre (Const x)    = show x
montre (Id x)       = x
montre (Add f1 f2)  = "( " ++ (montre f1) ++ " + " ++ (montre f2) ++ " )" 
montre (Mul f1 f2)  = "( " ++ (montre f1) ++ " * " ++ (montre f2) ++ " )"
montre (Inv f)      = "( 1 / " ++ (montre f) ++ " )"
montre (Pow k f)    = "( " ++ (montre f) ++ " )^" ++ (show k)
montre (Racine f)   = "Rac( " ++ (montre f) ++ " )"
montre (Ln f)       = "Ln( " ++ (montre f) ++ " )"
montre (Exp f)      = "Exp( " ++ (montre f) ++ " )"
montre (Cos f)      = "Cos( " ++ (montre f) ++ " )"
montre (Sin f)      = "Sin( " ++ (montre f) ++ " )"

instance Show Fonction where
              show = montre

eval :: Fonction   -> Nombre -> Nombre
eval    (Const x)     _      =  x
eval    (Id _)        n      =  n
eval    (Add f1 f2)   n      = (eval f1 n) + (eval f2 n)
eval    (Mul f1 f2)   n      = (eval f1 n) * (eval f2 n)
eval    (Inv f)       n      = 1 / (eval f n)
eval    (Pow k f)     n      = (eval f n)**k
eval    (Racine f)    n      = sqrt (eval f n)
eval    (Ln f)        n      = log (eval f n)
eval    (Exp f)       n      = exp (eval f n)
eval    (Cos f)       n      = cos (eval f n)
eval    (Sin f)       n      = sin (eval f n)
\end{lstlisting}

Complétez alors les lignes suivantes:

\begin{lstlisting}
derive :: Fonction -> Fonction -> Fonction
derive    (Const _)   _        = ?
derive    (Id x)      v        = ?
derive    (Add f1 f2) v        = ?
derive    (Mul f1 f2) v        = ?
derive    (Inv f)     v        = ?
derive    (Pow k f)   v        = ?
derive    (Racine f)  v        = ?
derive    (Ln f)      v        = ?
derive    (Exp f)     v        = ?
derive    (Cos f)     v        = ?
derive    (Sin f)     v        = ?
\end{lstlisting}


Alors par exemple:

\begin{lstlisting}
λ> derive (Pow 2 x) x
( 1.0 * ( 2.0 * ( x )^1.0 ) )
λ> derive (Pow 3 x) x
( 1.0 * ( 3.0 * ( x )^2.0 ) )
λ> derive (Pow 2 (Racine x)) x
( ( 1.0 * ( 1 / ( 2.0 * Rac( x ) ) ) ) * ( 2.0 * ( Rac( x ) )^1.0 ) )
λ> derive (Ln (Ln (Ln x))) x
( ( ( 1.0 * ( 1 / x ) ) * ( 1 / Ln( x ) ) ) * ( 1 / Ln( Ln( x ) ) ) )
λ> derive (Ln (Cos x)) x
( ( -1.0 * ( 1.0 * Sin( x ) ) ) * ( 1 / Cos( x ) ) )
\end{lstlisting}
\end{exercice}



\begin{exercice}[Jeu de Mots]
\begin{enumerate}
\item Déterminez une fonction  \verb+longueur :: Mot -> Int+ qui  renvoie le nombre de
caractères constituant un mot.

\item Déterminez une fonction \verb+renverse :: Mot -> Mot+ qui inverse l'ordre d'un mot.

\item Déterminez une  fonction \verb+colle ::  Mot -> Mot  -> Mot+ qui  concatène deux
mots.

\item Déterminez  une fonction  \verb+liste_of_Mot  :: Mot  -> [Char]+  qui  à un  mot
associe la liste de ses caractères.

\end{enumerate}
\end{exercice}





\begin{exercice}[Liste de fonctions sur les listes]

Voici les  outils minimums  tels qu'ils  sont décrits  dans la  documentation du
module  \verb+Data.List+  de   Haskell  .  Adaptez-les à  notre  type  \verb+Liste+  et
donnez-leur un nom français pour éviter les conflits avec les fonctions de  Haskell  .

\begin{lstlisting}[caption={Extrait de la documentation de Data.List}]
  (++) :: [a] -> [a] -> [a]	 
Append two lists, i.e.,
 [x1, ..., xm] ++ [y1, ..., yn] == [x1, ..., xm, y1, ..., yn]
 [x1, ..., xm] ++ [y1, ...] == [x1, ..., xm, y1, ...]
If the first list is not finite, the result is the first list.

head :: [a] -> a	 
Extract the first element of a list, which must be non-empty.

last :: [a] -> a	 
Extract the last element of a list, which must be finite and non-empty.

tail :: [a] -> [a]	 
Extract the elements after the head of a list, which must be non-empty.

init :: [a] -> [a]	 
Return all the elements of a list except the last one. The list must be non-empty.

null :: [a] -> Bool	 
Test whether a list is empty.

length :: [a] -> Int	 
length returns the length of a finite list as an Int. It is an instance of the more general Data.List.genericLength, the result type of which may be any kind of number.

map :: (a -> b) -> [a] -> [b]	
map f xs is the list obtained by applying f to each element of xs, i.e.,
 map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn]
 map f [x1, x2, ...] == [f x1, f x2, ...]

reverse :: [a] -> [a]	
reverse xs returns the elements of xs in reverse order. xs must be finite. 

foldl :: (a -> b -> a) -> a -> [b] -> a	
foldl, applied to a binary operator, a starting value (typically the left-identity of the operator), and a list, reduces the list using the binary operator, from left to right:
 foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
The list must be finite. 

any :: (a -> Bool) -> [a] -> Bool	
Applied to a predicate and a list, any determines if any element of the list satisfies the predicate.

all :: (a -> Bool) -> [a] -> Bool	
Applied to a predicate and a list, all determines if all elements of the list satisfy the predicate.

sum :: Num a => [a] -> a	
The sum function computes the sum of a finite list of numbers.

product :: Num a => [a] -> a	
The product function computes the product of a finite list of numbers.

maximum :: Ord a => [a] -> a	
maximum returns the maximum value from a list, which must be non-empty, finite, and of an ordered type. It is a special case of maximumBy, which allows the programmer to supply their own comparison function.

minimum :: Ord a => [a] -> a	
minimum returns the minimum value from a list, which must be non-empty, finite, and of an ordered type. It is a special case of minimumBy, which allows the programmer to supply their own comparison function. 

takeWhile :: (a -> Bool) -> [a] -> [a]	
takeWhile, applied to a predicate p and a list xs, returns the longest prefix (possibly empty) of xs of elements that satisfy p:
 takeWhile (< 3) [1,2,3,4,1,2,3,4] == [1,2]
 takeWhile (< 9) [1,2,3] == [1,2,3]
 takeWhile (< 0) [1,2,3] == []

elem :: Eq a => a -> [a] -> Bool	
elem is the list membership predicate, usually written in infix form, e.g., x `elem` xs. 

find :: (a -> Bool) -> [a] -> Maybe a	
The find function takes a predicate and a list and returns the first element in the list matching the predicate, or Nothing if there is no such element.

filter :: (a -> Bool) -> [a] -> [a]	
filter, applied to a predicate and a list, returns the list of those elements that satisfy the predicate; i.e.,
 filter p xs = [ x | x <- xs, p x]

partition :: (a -> Bool) -> [a] -> ([a], [a])	
The partition function takes a predicate a list and returns the pair of lists of elements which do and do not satisfy the predicate, respectively; i.e.,
 partition p xs == (filter p xs, filter (not . p) xs)

zip :: [a] -> [b] -> [(a, b)]	
zip takes two lists and returns a list of corresponding pairs. If one input list is short, excess elements of the longer list are discarded. 
\end{lstlisting}

\end{exercice}


\begin{exercice}[Ensembles à partir de listes]
  Créez  un type  \lstinline{Ens}  qui  implémente les  ensembles  à partir  des
  listes.

Il faudra prévoir les principales  fonctionnalités comme un test d'appartenance,
d'inclusion, des opération d'union, d'intersection, de différence.

Vous partirez de ça:

\begin{lstlisting}
module EnsembleListe where

type Element  = Int
type Predicat = Element -> Bool
data Ensemble = Ens ([Element])
              
-- Partie qui utilise les listes
              
instance Show Ensemble where
    show (Ens liste) = show liste

estVide :: Ensemble    -> Bool
estVide    (Ens liste) =  liste == []
                
contient :: Ensemble -> Element -> Bool
contient    (Ens liste) e       =  e `elem` liste

insere ::  Element -> Ensemble       -> Ensemble
insere     e          (Ens liste)
           | (Ens liste) `contient` e = Ens liste
           | otherwise                = Ens (e:liste)

-- Partie indépendante des listes

union ::  Ensemble   -> Ensemble  -> Ensemble

inter :: Ensemble -> Ensemble -> Ensemble

pourTous :: Predicat -> Ensemble     -> Bool

ilExiste :: Predicat -> Ensemble     -> Bool

estInclus :: Ensemble -> Ensemble -> Bool

estEgal :: Ensemble -> Ensemble -> Bool

filtre :: Predicat -> Ensemble -> Ensemble

cardinal :: Ensemble -> Int
\end{lstlisting}

\end{exercice}





\begin{exercice}
  
On se propose de d\'{e}montrer que tous les \'{e}tudiants d'\textsc{Iut}
ont le m\^{e}me \^{a}ge et, pour cela, on note $P\left( n\right) $
l'affirmation%



\og \textit{si \ on choisit $n$ \'{e}tudiants  $\left( n\in \mathbb{N}%
^{\ast }\right) $, il est s\^{u}r qu'ils ont tous le m\^{e}me \^{a}ge}\fg{}%



Il est clair que $P\left( 1\right) $ est vraie. 

D\'{e}montrons que $P\left(
n\right) \limp P\left( n+1\right)$. Pour cela nous supposons que $%
P\left( n\right) $ est vraie (c'est l'hypoth\`{e}se de r\'{e}currence) et
nous choisissons un groupe quelconque de $n+1$ \'{e}tudiants que nous
ordonnons par ordre alphab\'{e}tique (pourquoi pas). D'apr\`{e}s l'hypoth%
\`{e}se de r\'{e}currence, les $n$ premiers de l'ordre alphab\'{e}tique ont
tous le m\^{e}me \^{a}ge ainsi que les $n$ derniers. Comme ces deux groupes
de $n$ \'{e}tudiants ont au moins un \'{e}tudiant en commun, on en d\'{e}%
duit qu'ils ont tous le m\^{e}me \^{a}ge.%

Nous venons de d\'{e}montrer que $P\left( n\right) \limp P\left(
n+1\right) $ pour tout $n\geq 1$ et, comme $P\left( 1\right) $ est vrai, $%
P\left(  n\right) $  est toujours  vrai pour  tout $n\geqslant  1.$ \textbf{Y
  a-t-il une erreur dans le raisonnement ?}
\end{exercice}



\begin{exercice}[Javanais for dummies]
On va simplifier le javanais habituel  sans tenir compte de la découpe
selon les syllabes.
On  introduit  les lettres  \og  av\fg{}  devant la  première  voyelle
rencontrée dans le mot en partant de la gauche.
Créez une foncton \texttt{javanais(mot)}:

\begin{lstlisting}
λ> javanais "chrome"
"chravome"

λ> javanais "air"
"avair"
\end{lstlisting}
  
\end{exercice}



\begin{exercice}[Preuve]

Prouvez par induction les propriétés suivantes:

\begin{lstlisting}
map (f . g)  = map f . map g
map f . tail = tail . map f
map f . concat = concat . concat (map f)
f . head = head . map f
take m . take n = take (min m n)
drop m . drop n = drop (m + n)
last (reverse xs) = head xs
\end{lstlisting}
  
\end{exercice}

\begin{exercice}[Subtilité: fonction stricte ]

Considérons la fonction \lstinline{bolos = bolos}: c'est une expression qui a pour valeur $\bot$. 


Une fonction est dite stricte si, et seulement si, appliquée à  \lstinline{bolos}, elles renvoie $ \bot$. Est-ce que toutes les fonctions sont strictes sur  Haskell?

  
\end{exercice}


\begin{exercice}[Exponentiation]
  \begin{enumerate}
  \item Voici une définition très classique de la puissance entière d'un entier:
    $ x^0=1$ et $ x^n=x×x^{n-1}$

Cela donne:

\begin{lstlisting}
(°) :: Integer -> Integer -> Integer
(°)    x          0       =  1
(°)    x          n       =  x*x°(n-1)
\end{lstlisting}

Démontrez  alors   que  pour  tous  entiers   naturels  $  x$,  $n$   et  $  m$,
\lstinline{x°(n + m) = x°n * x°m}

Attention, il y a un piège...

\item Démontrez ensuite, toujours par induction, que \lstinline{x°n * x°n = (x*x)°n}. 


\item Mais il y  a mieux à faire en remarquant que, quand  n est pair, $x^n=(x ×
  x)^{n/2}$:  quel est  l'intérêt, algorithmiquement  parlant? Comment  en tirer
  parti?

  Vous  pourrez avoir  besoin de  la  fonction \lstinline{div}  qui retourne  le
  quotient de la division euclidienne de deux entiers.

  Vous noterez par exemple \lstinline{^!} ce nouvel opérateur.


Souvenez-vous de  vos cours de  6\up{eme}. Effectuer la division  euclidienne de
deux entiers $ a$ et $ b$, $ b$ étant non nul, c'est déterminer les entiers $ q$
et $ r$ tels que:

$$a = b×q+r\qquad{0 \leqslant r < |b| } $$

Comparez le  nombre d'étapes  nécessaires pour calculer  $3^{25}$ avec  l'une et
l'autre méthode.  Nous essaierons  de généraliser tout  à l'heure  mais revenons
d'abord à nos moutons.

\item Il  s'agit maintenant  de démontrer que  les fonctions  \lstinline{(°)} et
  \lstinline{^!} sont équivalentes.

Le cas $ n$ impair est assez direct. Pour le cas pair, il y a plus de travail...

\item Moralité?  Parmi ces  deux codes, un  est simple à  lire et  peu efficace,
  l'autre est compliqué à lire et efficace: faut-il malgré tout jeter le premier
  à la poubelle?

\item  Peut-on avoir  un ordre  de grandeur  du nombre  d'étapes nécessaires  au
  calcul  de $  x^n$?  Cela peut  avoir une  importance  capitale, notamment  en
  cryptographie  où on  calcule régulièrement  des  entiers à  la puissance  des
  nombres d'une centaine de chiffres.

  Faisons  pour   cela  un  petit   rappel  sur  une  fonction   primordiale  en
  informatique.  Nous  voudrions  savoir  combien de  bits  sont  nécessaires  à
  l'écriture   d'un  entier...Menez   l'enquête.  Peut-être   aurez-vous  besoin
  d'introduire le logarithme de base 2:

$$\log_2(x)=\frac{\ln x}{\ln 2} $$




  \end{enumerate}
\end{exercice}


\begin{exercice}[Factorielle]

La factorielle d'un entier positif, vous connaissez:

$$0! = 1\qquad n! = n×(n-1)!$$

Proposez une définition récursive directe  et une version avec accumulateur puis
prouvez par induction qu'elles sont équivalentes.
  
\end{exercice}




\begin{exercice}[CCP MP 2015]
{\itshape Non, non, ce n'est pas un extrait d'un livre de seconde, c'est un sujet 0
proposé pour l'épreuve de Math du concours CCP...}
  \begin{enumerate}
  \item Écrire une fonction factorielle qui  prend en argument un entier naturel
    $ n$ et renvoie $ n!$ (on n'accepetra pas bien sûr de réponse utilisant la
    propre fonction factorielle du module math de Python ou Scilab).
  \item Écrire une fonction  \lstinline{seuil} qui prend en argument un  entier $ M$ et renvoie
    le plus petit entier naturel $ n$ tel que $ n!>M$.
  \item Écrire une fonction booléenne nommée \lstinline{est_divisible}, qui pend
    en argument un entier naturel $ n$  et renvoie \lstinline{True} si $ n!$ est
    divisible par $ n+1$ et \lstinline{False} sinon.
  \item On considère la fonction suivante nommée \lstinline{mystere}:
    \begin{PY}
def mystere(n):
    s = 0
    for k in range(1,n+1):
        s = s + factorielle(k)
    return s
    \end{PY}
    \begin{enumerate}
    \item Quelle valeur renvoie \lstinline{mystere(4)}?
    \item Déterminer    le     nombre    de    multiplications    qu'effectue
      \lstinline{mystere(n)}.
    \item Proposer une amélioration du script de la fonction \lstinline{mystere}
      afin d'obtenir une complexité linéaire.
    \end{enumerate}
  \end{enumerate}
\end{exercice}



% \begin{exercice}[Calcul de la racine carrée par la méthode de \textsc{Newton}]
  

% Il y a presque 4000 ans, les  petits Babyloniens calculaient la racine carrée de
% 2 avec 6 bonnes décimales en utilisant l'algorithme inscrit sur cette tablette:


% %\begin{figure}
% \begin{center}
%   \includegraphics{YBC7289blanc}
% \end{center}
% %\end{figure}

% Cette  idée à  été reprise  plus tard  par \textsc{Héron}  d'Alexandrie quelques
% années avant la naissance du petit  Jésus et c'est pourquoi cet algorithme porte
% son nom. Il est repris aujourd'hui  par les ordinateurs modernes pour déterminer
% une approximation des racines carrés.



% \end{exercice}




\begin{exercice}[Nombres premiers]
 
\subsubsection{Définition}
Quoi de plus simple qu'un nombre premier :


\setindent{\indentationcours}
\begin{definition}
 Un entier naturel  est dit premier s'il est  supérieur ( i.e. supérieur
 ou égal ) à 2 et n'est 
divisible que par 1 et lui-même. 
\end{definition}
\setindent{0cm}

et pourtant, ils renferment tant de mystères que les plus grands esprits depuis 
des siècles n'ont toujours pas réussi à en percer tous
les secrets et ce malgré les énormes progrès technologiques et les  
investissements colossaux consentis par les pouvoirs tant civils que
militaires pour assurer ou percer la confidentialité des transmissions de toutes 
natures qui continuent de dépendre d'une meilleure
connaissance des nombres premiers, ce que nous verrons un peu plus loin. Qui 
sont-ils ? Combien sont-ils ? Où sont-ils ? À quoi
servent-ils ? Nous essaierons de donner quelques éléments de réponses à ces 
questions.


Mais tout d'abord, pourquoi jouent-ils un rôle si important ? Fondamentalement, 
il existe deux manières d'engendrer $\bbn$ : 
\begin{itemize}
\item si on veut engendrer $\bbn$ en utilisant l'addition, on s'aperçoit que le nombre 1 nous suffit : on <<~fabrique~>> 2  en additionnant 1 avec lui-même; 3 en additionnant 1 avec
2, etc.
\item si on veut engendrer $\bbn$ en utilisant la multiplication, là, les choses se compliquent. Pour <<~fabriquer~>> 2, il 
faut le créer; même problème pour  3. On fabrique  4 en multipliant  2
avec lui-même, mais il faut créer 5. On fabrique  6 en multipliant 3 avec 2. On crée 7. On fabrique 8 à partir de 2. On fabrique 9 à partir de 3. On fabrique 10 à partir de 2 et 5, etc.

 Les 
nombres que l'on est obligés de créer sont les briques nécessaires à
fabriquer tous les autres. C'est bien plus compliqué que l'addition me 
direz-vous, mais la multiplication est plus <<~puissante~>> et
nous permet d'aller bien plus vite et plus loin. 
\end{itemize}

\sm

Les nombres premiers sont donc ces éléments qui nous permettent de fabriquer tous 
les autres. Un des premiers problèmes étudiés à été de
savoir s'ils peuvent tenir dans une boîte. 
Euclide à répondu à cette question il y a vingt-trois siècles
et la réponse est non.

Pour le prouver, nous aurons besoin d'un résultat intermédiaire:

\setindent{\indentationcours}
\begin{theoreme}\label{infinite}
  Tout entier naturel admet au moins un diviseur premier.
\end{theoreme}
\setindent{0cm}



Si ce nombre, appelons-le $n$, est premier, tout va bien.

Sinon, l'ensemble de ses diviseurs étant non vide ( $n$ est dedans ) et borné ( 
par 1 et lui-même), il admet un plus petit élément $p\neq 1$.
Ce nombre n'est pas divisible par un autre, sinon ce nombre plus petit que $p$ 
divisant $p$ diviserait $n$ et alors $p$ ne serait plus le
plus petit diviseur de $n$. Le nombre $p$ est donc premier et voilà.

\setindent{\indentationcours}
\begin{theoreme}
  Il y a une infinité de nombres premiers.
\end{theoreme}
\setindent{0cm}




 \emph{Raisonnons par l'absurde} et 
supposons qu'il existe exactement $n$ nombres premiers qu'on
nommera $p_1$, $p_2,\cdots,\ p_n$ et appelons $N$ le nombre  \[N=p_1p_2\cdots 
p_n+1\]
%\footnote{Ce style de nombre réapparaîtra souvent}. 
Il
est plus grand que tous les $p_i$, donc il n'est pas premier d'après notre 
hypothèse, donc il admet un diviseur  premier $p$ qui est donc
un des $p_i$, puisqu'il n'y a qu'eux. Soit $i_0$ tel que $p=p_{i_0}$. Alors $p$ 
divise $p_1p_2\cdots p_n$. Or il divise $N$, donc il
divise leur différence $N-p_1p_2\cdots p_n$, c'est à dire 1, donc $p=1$ ce qui 
est absurde puisqu'il est premier. Ainsi, il n'existe pas
de plus grand nombre premier.


\sm


Il y en a donc une infinité et l'aventure ne fait que commencer. 



\subsubsection{Comment vérifier qu'un nombre est premier?} 


\paragraph*{Force brute}

Créez une fonction \lstinline{divise k n} qui teste si l'entier $ k$ divise $ n$.

\begin{HS}
λ> divise 7 91
True
λ> 7 `divise`91
True
\end{HS}

Créez une fonction \lstinline{lesDiviseurs :: Int -> [Int]} qui renvoie la liste
des diviseurs de $n$:

\begin{HS}
λ> lesDiviseurs 100
[100,1,2,4,5,10,20,25,50]
\end{HS}

Déduisez-en un test \lstinline{estPremier' :: Int -> Bool}

\begin{HS}
λ> estPremier (2^10 - 1)
False
\end{HS}


On peut alors tirer profit de la fonction \lstinline{Data.List.find}:


\begin{lstlisting}[caption=Doc Haskell]
find :: (a -> Bool) -> [a] -> Maybe a	
The find function takes a predicate and a list and returns the first element in the list matching the predicate, or Nothing if there is no such element.
\end{lstlisting}

pour déterminer  une fonction \lstinline{prochainPremier} qui  calcule le nombre
premier qui suit l'argument:

\begin{HS}
λ> prochainPremier' (2^10 - 1)
Just 1031
\end{HS}


Cependant,  l'efficacité de  cette fonction  laisse à  désirer...Comment peut-on
améliorer \lstinline{lesDiviseurs}?

Mais si on ne cherche que les nombres premiers, a-t-on besoin de tous les diviseurs?


\paragraph*{Étudions le problème pour être plus efficaces}


 Observons les diviseurs de 1321 par exemple: si aucune des 1319 divisions ne 
<<~tombe juste~>>, alors on pourra dire que 1321 premier.
Et puis d'abord, il est impair, il ne semble pas être divisible par 3, alors 
pourquoi pas...



\begin{center}
\footnotesize{ {\setlength{\tabcolsep}{0.1cm}
\begin{tabular}{IcIccccccccccccI}
\whline
 diviseur& 2& 3& 4& 5& 6&  7&8&9&10&11&12&13\\ \hline
  quotient&660,5&440,3&330,3&264,2
&220,2&188,7&165,1&146,8&132,1& 120,1& 110,1&101,6\\ \whline
 diviseur &14&15&16&17&18&19&20&21&22&23&24&25\\ \hline
quotient &94,36&88,07&82,56&77,71&73,39&69,53 &66,05&62,90&60,05&57,43
&55,04&52,84\\ \whline diviseur&26&27&28&29&30&31&32&33&34&35&36&37 \\ \hline
  quotient&50,81&48,93&47,18& 45,55& 44,03&42,61&41,28&40,03&38,85&37,74 &36,69& 
35,70\\ \whline

\end{tabular}}
}
\end{center}


Le tableau est incomplet: il reste encore à essayer les quotients de 38 à 1320, 
mais cela aurait été mauvais pour la planète.


 Tout d'abord,  nous n'avons pas trouvé  de quotient entier  en ce début
 d'enquête.  
Nous observons de plus que si la suite des diviseurs
 est  croissante,  celle  des  quotients  est  décroissante.  Vous  avez
 sûrement remarqué qu'à partir de 37, 
 les  quotients sont  inférieurs aux  diviseurs donc  nous  pouvons nous
 arrêter là: 
si pour un diviseur supérieur à 37, on trouvait un
 quotient entier $q$, alors en  divisant 1321 par $q$, qui est inférieur
 à 37, on devrait se trouver au début de notre liste de diviseurs et 
  ce diviseur serait entier. Le problème, c'est qu'aucune division par un 
entier inférieur à 37 n'a donné de quotient entier donc on
  peut s'épargner les 1283 divisions restantes.


\bigskip

  Mine de rien, nous venons de franchir un grand pas dans la théorie des
  nombres: pour tester si l'entier 1321 est premier, il nous a
  suffit  d'effectuer 36 divisions\footnote{Et  encore, nous  aurions pu
    faire mieux 
comme nous allons le voir tout de suite après.}. Deux
  problèmes se posent maintenant: pourquoi 36 et pouvons-nous généraliser ce 
résultat aux autres entiers? 

Un petit Joker : $\sqrt{1321}\simeq 36,3$...

Reprenons la  propriété \vref{infinite}. Tout naturel $n$  admet un plus
petit diviseur $p$ 
qui est premier. \'Ecartons le cas où $n$ est premier et
donnons un nom aux nombres qui restent :

\setindent{\indentationcours}
\begin{definition}
  Un entier naturel \emph{autre que 1} qui n'est pas premier est dit 
\textbf{composé}.
\end{definition}
\setindent{0cm}



L'entier $n$ étant  composé, il s'écrit donc $n=pq$,  avec $q$ un entier
supérieur 
à $p$ (car $p$ est le plus petit diviseur). Ainsi $$
p \leqslant q\ \text{ et donc }\ p^2 \leqslant  pq=n\ \text{ c'est à dire }\
p \leqslant \sqrt{n}$$ 

Nous pouvons donc généraliser l'observation précédente

\setindent{\indentationcours}
\begin{theoreme}
  Si un entier est composé, alors il admet un diviseur premier 
inférieur à sa racine carrée.
\end{theoreme}
\setindent{0cm}

Inspirez-vous de ce résultat pour encore améliorer les fonctions précédentes.

Vous  pourrez  utiliser  par  exemple  les  fonctions  \lstinline{takeWhile}  et
\lstinline{filter}.

Par  exemple, il  faut 3  secondes pour  déterminer le  nombre premier  qui suit
$2^{50}$:

\begin{HS}
main = print (prochainPremier (2^50))
\end{HS}

\begin{SH}
$ ghc premHs.hs -o premHs
$ time ./premHs 
Just 1125899906842679

real	0m3.053s
user	0m3.048s
sys	0m0.008s
\end{SH}

Vous pouvez  ensuite vous lancer dans  l'écriture d'une fonction qui  renvoie la
décomposition  d'un entier  en produit  de  facteurs premiers  sachant que  nous
admettrons le  théorème suivant (mais rien  ne vous empêche de  vous lancer dans
une démonstration...):

\setindent{\indentationcours}
\begin{theoreme}
  Tout entier $n$ supérieur à 2 admet une et une seule (à l'ordre près 
des termes) décomposition en produit fini de nombres
premiers
\end{theoreme}
\setindent{0cm}



\end{exercice}



\modenormal




%%% Local Variables: 
%%% mode: LaTeX
%%% TeX-master: "PolyMD1_14"
%%% End: 
