\chapterimage{salt-n-pepa}
\chaptertext{Notre  exploration  de   la  programmation  fonctionnelle
  continue avec l'exploration  des \textbf{type} mais cette notion est
  tellement  riche et  importante qu'elle  mérite un  chapitre à  elle
  seule qui  ne sera d'ailleurs  qu'une introduction. Nous  allons par
  la  même occasion  découvrir son  lien avec  la notion  fondamentale
  d'\textbf{ensemble} pour mieux la comprendre.}

\chapter{Let's talk about Sets}

\section{C'est quoi ce Type?}

\haskell


%\vspace{-1.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=2.8cm]{Cantor}
\caption{Georg \textsc{Cantor}} %\\(1845 - 1918)}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5cm}
\begin{minipage}[t]{\linewidth}

Vous avez  (ou allez)  étudier les  types du langage  C: en  gros, ils
indiquent comment vos objets sont représentés sur machine.

\end{minipage}

Les types  en Haskell ont un  rôle bien plus riche.  Notre exploration
des types se fera tout au  long de l'année. Nous allons nous contenter
d'une première approche.

Chaque expression (et  donc chaque valeur) est associée à  un type, ou
plutôt \textit{appartient} à un type.

Pensez à  un type  comme à un  \textit{ensemble} d'expressions  (ou de
valeurs) qui ont des choses en commun. C'est d'ailleurs cette idée qui
a été proposée par Georg \textsc{Cantor} (1845 - 1918) à la fin du XIX\up{e} siècle:

\begin{definition}[Principe de compréhension]
Un ensemble est  une collection d'objets tous  distincts qu'on appelle
ses éléments et qui partagent une \og propriété\fg{}.
\end{definition}


Par  exemple \og  être  un  garçon\fg{} est  une  propriété  vérifiable si  l'on
considère l'amas d'étudiant(e)s d'INFO  1: on peut répondre par oui  ou non à la
question \og truc est un garçon\fg{}.

 
On peut  alors former l'ensemble G  des garçons d'INFO 1:  ses \textit{éléments}
sont ceux qui vérifient la propriété. On peut noter alors: 


$$G = \bigl\{\text{  étudiant} \mid \text{ (étudiant est  en INFO1) ET
  (étudiant est un garçon)}\bigr\}$$ 

On notera  indistinctement \og  Albert appartient  à G\fg{},  \og Albert  est un
élément de G\fg{}, \og G contient Albert\fg{}, \og Albert $\in G$\fg{}, \og $G \owns$ Albert\fg{}.

\begin{notation}
   La  notation $\in$  est  due   au  mathématicien   anglais  Bertrand
    \textsc{Russel} en 1903 qui reprenait l'epsilon $\varepsilon$ de l'italien
    Giuseppe  \textsc{Peano}  en 1889  mais  en \og  l'arrondissant\fg{}
    compte-tenu des  contraintes typographiques anglaises  sous la forme
    $\epsilon$ qui a donné $\in$.

\smallskip

Un ensemble qui ne contient rien s'appelle l'\textit{ensemble vide} et
se note $\emptyset$ ou $\{\}$.


\end{notation}

\begin{NB}
  En Haskell  TOUT A UN  TYPE AVANT LA  COMPILATION. On parle  de type
  \textit{statique}. C'est très important et très utile:

  \begin{itemize}
  \item cela impose  de bien clarifier sa pensée, de  bien penser à la
    structure   du   programme.   Avant   de   programmer,   il   faut
    \textit{écrire}   le  type   des  expressions   que  nous   allons
    utiliser.  Ce  n'est pas  toujours  simple  mais  cela a  un  rôle
    important pour...
  \item  ... bien  documenter  le  code: en  regardant  les types,  on
    comprend mieux ce que feront vos fonctions.
  \item  ...permettre de  découvrir  de nombreux  bugs avant  l'exécution
    (\textit{run-time  errors})  car  elles deviennt  des  erreurs  de
    compilation. Ainsi,  il vaut mieux  découvrir une erreur  quand on
    tente de  compiler un programme  que quand on lance  son exécution
    (par exemple un logiciel de pilotage automatique d'avion :-) ). On
    ne  soigne pas  tout  à  la compilation  mais  le typage  statique
    permet de découvrir énormément d'erreurs.
  \end{itemize}

\end{NB}

\begin{definition}[Axiome d'extensionalité]
Deux ensembles  A et B sont  égaux si, et seulement  si, ils contiennent
les mêmes éléments. On écrit alors $A= B$.
\end{definition}


Ça  paraît  idiot    mais  cela  permet  de bien  cerner  le
problème: c'est la notion d'appartenance  d'un élément à un ensemble qui
est primordiale.

\smallskip

Il existe  des types primitifs  (déjà définis dans  l'environnement de
base) et si vous chargez  une nouvelle bibliothèque, de nouveaux types
seront  définis.  Nous apprendrons  également  à  définir nos  propres
types.

Par exemple,  \lstinline{Integer} est l'ensemble de  tous les entiers,
\lstinline{Char}    est   l'ensemble    de   tous    les   caractères,
\lstinline{Bool} est l'ensemble des booléens,...

GHCi propose la touche magique  \lstinline{:t} qui donne le type d'une
expression. Et oui, Haskell devine le  type de vos expressions même si
vous ne l'avez pas précisé: il fait de l'\textit{inférence de type}.

\begin{lstlisting}
λ> :t 'a'
'a' :: Char
λ> :t 2 + 2 == 4
2 + 2 == 4 :: Bool
\end{lstlisting}

\begin{NB}
  \lstinline{::} se lit \og ...a pour type...\fg{}
\end{NB}


OK, pas de problème. Bon, je suppose que 3 est un entier:

\begin{lstlisting}
λ> :t 3
3 :: Num a => a
\end{lstlisting}

Ouh la...


\begin{lstlisting}
λ> :t 3.5
3.5 :: Fractional a => a
\end{lstlisting}

Ouh la la la la....


\vspace{-.8cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3.25cm}
\begin{figure}
  \includegraphics[width=3.25cm]{zorglub}
%\caption{Georg \textsc{Cantor}} %\\(1845 - 1918)}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5cm}
\begin{minipage}[t]{\linewidth}
\end{minipage}


\subsection*{Ensembles de nombres}

Vous  avez  appris au  collège  qu'il  y  avait des  entiers  positifs
(naturels) qu'on regroupe dans un ensemble appelé $ℕ$ et un plus grand
ensemble, $ℤ$ qui regroupe tous les zentiers, positifs comme négatifs.


Tous les éléments de  $ ℕ$ sont des éléments de $ ℤ$:  on dit que $ ℕ$
\textit{est inclus} dans $ ℤ$ ou que $ ℤ$ \textit{contient} $ ℕ$.




\begin{definition}[inclusion]
  L'ensemble  $X$ est  inclus dans  l'ensemble  $Y$ si,  et seulement  si, tous  les
  éléments de $X$ sont des éléments de $Y$.
Cela se note 
$$(X \subseteq Y) \lequiv ((z \in X) \limp (z\in Y))$$
On  dira  indifféremment  \og  \textit{$X$   est  contenu  dans  $Y$}\fg{},  \og
\textit{$Y$  contient  $X$}\fg{},  \og   \textit{$X$  est  un  sous-ensemble  de
  $Y$}\fg{}, \og \textit{$X$ est une partie de $Y$}\fg{}.
\end{definition}




\begin{DANGER}[Notations]
Il faudra bien distinguer $\subset$, $\subseteq$ et $\nsubseteq$.
$
B\varsubsetneq A\text{ signifie }\left( B\subseteq A\text{ et }B\neq
A\right) 
$.

Il ne faut pas confondre avec $B$ $\nsubseteq A$ qui exprime que $B$
n'est pas inclus dans $A.$ On dit que $B$ est une partie propre de $A$ si,
et seulement si, $B\subseteq A$ avec $B\neq A$ et $B\neq \emptyset \ $(il
est nécessaire que $A$ ne soit pas vide et ne soit pas un singleton).
\end{DANGER}


La notion d'inclusion va nous permettre de réécrire l'axiome d'extensionalité:



\begin{theoreme}[Axiome d'extensionalité version II]

$$(\forall X)(\forall Y)(((X \subseteq Y) \land (Y \subseteq X)) \limp (X=Y))$$
  
\end{theoreme}

Ouh la, c'est quoi ces signes cabalistiques?!!



\subsection*{Kit   de   survie   en    logique   des   prédicats:   les
  quantificateurs}

Par exemple \og \textit{est un entier pair}\fg{} est une propriété définie sur
l'ensemble  $ℕ$  des entiers  naturels  que  nous  noterons $P$.  Alors
2 vérifie $P$ mais 3 non.


Ces notions s'introduiront naturellement sur  notre ami  Haskell  :

\begin{lstlisting}
naturels         = [0..]
pairs            = [n | n <- naturels, mod n 2 == 0]
petits_pairs     = [n | n <- [0..15], mod n 2 == 0]
petits_pairs_bis = [2*k | k <- [0..7]]
\end{lstlisting}

Alors on obtient par exemple:

\begin{lstlisting}
λ> petits_pairs
[0,2,4,6,8,10,12,14]
\end{lstlisting}

On notera aussi $2\in\mathtt{pairs}$ ou encore $2\in \bigl\{x | (x\in\bbn) \land
P(x)\bigr\}$ ou
encore $2\in \bigl\{t | (t\in\bbn) \land P(t)\bigr\}$ ou
encore $P(2)$ ou encore $2\in  \bigl\{x| x\text{ est un entier naturel
  et } x \text{ est pair} \bigr\}$. 

Ainsi $P(x)$ signifie que l'objet $x$ vérifie la propriété P. Pour signifier que
$x$ ne vérifie pas P, on notera $\lnot P(x)$ (\og non P de $x$\fg{}).

On notera donc aussi $3\not\in\mathtt{pairs}$ ou encore $3\in \bigl\{x
| (x\in\bbn) \land \lnot P(x)\bigr\}$ ou 
encore   $3\not\in   \bigl\{t   |    (t\in\bbn)   \land   P(t)\bigr\}$   (est-ce
équivalent :-) ? ) ou 
encore $\lnot P(3)$. 


\medskip

Considérons une autre propriété R: un nombre  $x$ vérifie R si, et seulement si,
son carré vaut 2.


Quelque soit l'entier $x$, on a $x² ≠ 2$.  On notera cette propriété
par $$ ∀ x(x ∈ ℕ ∧ ¬R(x))$$ 




$\forall$  est  un  \textit{quantificateur  universel}  (c'est  un  A  à
l'envers, car  en allemand, ce symbole  se lit \textit{für Alle}  et a été
introduit en 1934 par Gerhard \textsc{Gentzel}...).





\medskip


Considérons une autre propriété S: un nombre  $x$ vérifie S si, et seulement si,
son carré vaut 4.


Il existe au moins un entier qui vérifie S: il s'agit de
2.
On note alors $$∃ x(x ∈ ℕ ∧ S(x))$$ 



$∃$ est l'autre quantificateur universel introduit par Giuseppe
\textsc{Peano} en 1897 (un E à l'envers comme dans \textit{Esiste almeno uno}).


On  peut même  préciser que  cet entier  est \textit{unique}  en faisant
suivre le quantificateur d'un point d'exclamation:
$∃ ! x(x ∈ ℕ ∧ S(x))$

Avec  Haskell  :

\begin{lstlisting}
s = \ x -> x^2 == 4
\end{lstlisting}

donne

\begin{lstlisting}
λ> s 2
True
λ> s 2.0
True
λ> s 3
False
λ> any s [0..]
True
λ> find s [0..]
Just 2
λ> filter s [0..100]
[2]
\end{lstlisting}

Mmmmmm... On a encore beaucoup de choses à découvrir.


\subsection*{Types numériques: découverte}

Comprendre comment  fonctionnent les  types numériques sur  Haskell va
nous occuper  pas mal de  temps. Nous allons  juste ici en  dresser un
rapide petit catalogue.


\subsubsection*{Integer}

\lstinline{Integer}  désigne un
nombre \textit{entier} en anglais de spécialité.

Donc \lstinline{Integer} correspond à $ℤ$. 

\begin{lstlisting}
λ> 2^1000
107150860718626732094842504906000181056140481170553360744375038837035105112493612249319
837881569585812759467291755314682518714528569231404359845775746985748039345677748242309
854210746050623711418779541821530464749835819412673987675591655439460770629145711964776
86542167660429831652624386837205668069376
\end{lstlisting}

\subsubsection*{Int}


\lstinline{Int} est  une partie  d'\lstinline{Integer}.

Et bien sur  Haskell   c'est  pareil: \lstinline{Int} regroupe une partie des
entiers, à savoir ceux qui sont compris entre $-2^{63}$ et $2^{63}-1$.

Par exemple, prenons ce fameux grand entier:

\begin{lstlisting}
λ> let n = 2^63 - 1 :: Int
λ> n
9223372036854775807
\end{lstlisting}


Mais là où ça devient bizarre:


\begin{lstlisting}
λ> n * 2
-2
\end{lstlisting}


euh... Y a quelque chose qui cloche là-dedans...On va étudier ça en
détail un peu plus tard (cf \vref{exo::comp2})

Si  vous faites  votre stage  dans une  banque et  que vous  codez vos
entiers avec  \lstinline{Int}, ça  peut poser  des problèmes  pour les
gens très très riches.

En    fait,    l'\lstinline{Int}    maximum   n'est    pas    toujours
\num{9223372036854775807}: ça dépend des processeurs, des OS.

Pour  le savoir,  il  existe des  expressions \lstinline{maxBound}  et
\lstinline{minBound}   qui  renvoient   les   bornes  inférieures   et
supérieures d'un type...borné (nous en  reparlerons plus tard), ce qui
est le cas de \lstinline{Int}:

\begin{lstlisting}
λ> maxBound :: Int
9223372036854775807
λ> minBound :: Int
-9223372036854775808
\end{lstlisting}

On peut quand même travailler sur 8, 16 ou 32 bits si on le désire:

\begin{lstlisting}
λ> :m Data.Int
λ> minBound :: Int8
-128
λ> minBound :: Int16
-32768
λ> minBound :: Int32
-2147483648
\end{lstlisting}


On  obtient  très  facilement  la   liste  de  tous  les  éléments  de
\lstinline{Int8} par exemple:

\begin{lstlisting}
λ> [minBound :: Int8 ..]
[-128,-127,-126,-125,-124,-123,-122,-121,-120,-119,-118,-117,-116,-115,-114,-113,-112,
-111,-110,-109,-108,-107,-106,-105,-104,-103,-102,-101,-100,-99,-98,-97,-96,-95,-94,
-93,-92,-91,-90,-89,-88,-87,-86,-85,-84,-83,-82,-81,-80,-79,-78,-77,-76,-75,-74,-73,
-72,-71,-70,-69,-68,-67,-66,-65,-64,-63,-62,-61,-60,-59,-58,-57,-56,-55,-54,-53,-52,
-51,-50,-49,-48,-47,-46,-45,-44,-43,-42,-41,-40,-39,-38,-37,-36,-35,-34,-33,-32,-31,
-30,-29,-28,-27,-26,-25,-24,-23,-22,-21,-20,-19,-18,-17,-16,-15,-14,-13,-12,-11,-10,
-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,
23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,
52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,
81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,
107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127]
\end{lstlisting}


\subsubsection*{Float et Double}

\vspace{.8cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3.25cm}
\begin{figure}
  \includegraphics[width=3.25cm]{gosling}
\caption{James \textsc{Gosling}} %\\(1845 - 1918)}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5cm}
\begin{minipage}[t]{\linewidth}
\end{minipage}


Alors  là, ça  devient très  compliqué, tellement  compliqué que  nous
consacrerons deux  mois à l'étude  des nombres à virgule  flottante au
printemps...

\begin{quote}
  {\itshape
    95 \% of the folks out there are completely clueless about floating-point
}
\begin{flushright}
  {\small James \textsc{Gosling} (M. Java) - 28 février 1998}
\end{flushright}
\end{quote}



On  retiendra juste  qu'il  s'agit  de l'ensemble  des  nombres \og  à
virgule\fg{}. Tant  qu'ils ne sont  ni trop  gros, ni trop  petits, ni
trop proches quand  on les soustrait, tout va bien,  ils se comportent
comme s'ils étaient  des décimaux. Mais quand on les  utilise près des
zones à risque....


\begin{center}
  \includegraphics[width=0.5\textwidth]{ingenieur}
\end{center}


\subsection*{Les autres types de base}

\subsubsection*{Les booléens}

L'ensemble  des  booléens  est  assez   limité  puisqu'il  n'a  que  2
élements. Ils appartiennent au type \lstinline{Bool}. 

\begin{lstlisting}
λ> maxBound :: Bool 
True
λ> minBound :: Bool
False
λ> [False ..]
[False,True]
\end{lstlisting}

Ce  qui est  intéressant, c'est  les opérations  dans \lstinline{Bool}
mais ne vous inquiétez pas, nous allons en reparler bientôt quand nous
aurons un peu plus de maturité.

Bon, donnons quand même quelques opérations de base:

\begin{lstlisting}
λ> True && False
False
λ> False && False
False
λ> False || True
True
λ> not False
True
λ> 2 + 2 == 4
True
λ> 2 + 2 > 5
False
λ> 2 + 2 /= 5
True
λ> "Iut" == "Enfer"
False
λ> "Haskell" > "C"
True
\end{lstlisting}

\subsubsection*{Les caractères}

Ils appartiennent au type \lstinline{Char}.

Ils sont en nombre fini bien qu'assez nombreux sur Haskell:

\begin{lstlisting}
λ> minBound :: Char
'\NUL'
λ> maxBound :: Char
'\1114111'
λ> take 130 [ minBound :: Char .. ]
"\NUL\SOH\STX\ETX\EOT\ENQ\ACK\a\b\t\n\v\f\r\SO\SI\DLE\DC1\DC2\DC3\DC4\NAK\SYN\ETB\CAN
\EM\SUB\ESC\FS\GS\RS\US !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\
\]^_`abcdefghijklmnopqrstuvwxyz{|}~\DEL\128\129"
\end{lstlisting}


Une  liste de  caractère est  une chaîne  de caractères  et une  liste
c'est...  disons un  truc entre  des crochets  dont les  éléments sont
ordonnées, peuvent être répétés, peuvent s'imbriquer mais sont tous de
même type. Mais  c'est beaucoup plus que ça et  nous leur consacrerons
un chapitre.


\subsection*{Les \og Tuples\fg{}}


Bon, supposons que  nous voulions faire un joli dessin  en plaçant des
lettres de l'alphabet  sur une feuille. À chaque lettre  on associe un
couple de coordonnées entières (on est à l'école primaire). 

Par exemple, on peut vouloir informer les lecteurs de notre jeu que le
point étiqueté par A se trouve au point de coordonnées (1, 2). On
peut décider de résumer ça en écrivant:

\begin{lstlisting}
λ> let a = ('A',(1 ,2 ))
λ> a
('A',(1,2))
\end{lstlisting}

Quel est le type de a inféré par Haskell?

\begin{lstlisting}
λ> :t a
a :: (Char, (Integer, Integer))
\end{lstlisting}

On a parlé tout à l'heure de liste: pourquoi ne met-on pas de crochets
alors?

\begin{lstlisting}
λ> let a = ['A',[1 ,2 ]]

<interactive>:117:14-20:
    Couldn't match expected type `Char' with actual type `[t0]'
    In the expression: [1, 2]
    In the expression: ['A', [1, 2]]
    In an equation for `a': a = ['A', [1, 2]]
\end{lstlisting}

Regardons la définition de match:

{\itshape \small
  match n.
  \begin{enumerate}
  \item
    \begin{enumerate} 
    \item  One that is exactly like another; a counterpart.
    \item One that  is like another in one or  more specified qualities:
      He is John's match for bravery.
    \end{enumerate}
  \item  One that is able to compete equally with another: The boxer had met his match.
  \item 
    \begin{enumerate}
    \item One that closely resembles or harmonizes with another: The napkins were a nice match for the tablecloth.
    \item A  pair, each one  of which  resembles or harmonizes  with the
      other: The colors were a close match.
    \end{enumerate}
  \item Sports
    \begin{enumerate}
    \item A  game or contest in  which two or more  persons, animals, or
      teams oppose and compete with each other: a soccer match. 
    \item  A tennis  contest  won by  the  player or  side  that wins  a
      specified number of sets, usually two out of three or three out of
      five.
    \end{enumerate} 
  \item     A marriage or an arrangement of marriage: a royal match.
  \item A person viewed as a prospective marriage partner.
  \end{enumerate}
}

Bref, on ne peut pas marier dans  une même liste un caractère avec une
liste d'entiers.

Le  type communément  appelé \textit{tuple}  en anglais  de spécialité
s'appelle un  $ n$-uplet en  français. Oui, mais qu'est-ce  que c'est?

Prenons un nouvel exemple...

\subsubsection*{À table}



 Vous êtes embauché(e) dans un restaurant. Vous disposez de
trois ensembles:

\begin{itemize}
\item l'ensemble des entrées: $$E=\bigl\{\text{Cuisses de sauterelles panées}, \text{ \oe uf mou},
  \text{ huîtres de l'Erdre}\bigr\}$$
\item  l'ensemble  des   plats  de  résistance:  $$P=\bigl\{\text{Turbot  à
    l'huile  de  ricin},  \text{  Chien  à  l'andalouse},  \text{  Soupe
    d'orties}\bigr\}$$
\item l'ensemble des desserts: $$D=\bigl\{\text{Pomme}, \text{Banane}, \text{Noix}\bigr\}$$
\end{itemize}


Vous  avez  envie   de  créer  un  nouvel  ensemble,   celui  des  menus
possibles. Une première idée consiste à regrouper tout le monde en
prenant $E\cup P \cup D$.

  Je  sais   bien  que  la  gastronomie  n'est   pas  la  principale
préoccupation des jeunes au  palet perverti par les tristes fastefoudes
mais en général  on commande UNE entrée SUIVIE  D'UN plat de résistance
SUIVI D'UN dessert (et pas une pizza et une bière) or la simple union que vous avez proposée peut vous
faire choisir un menu 
totalement  différent: cinq  desserts et  vingt entrées,  dans n'importe
quel ordre, par exemple. 

Nous  avons  besoin  de  créer   un  \og  objet\fg{}  ordonné  de  trois
composantes, chacune étant choisie respectivement dans $E$, $P$ et $D$.

Par exemple, (\oe uf mou, chien à l'andalouse, pomme) est un menu. C'est
un  triplet, à  ne pas  confondre avec  l'ensemble $\bigl\{$\oe  uf mou,
chien à l'andalouse, pomme $\bigr\}$ qui n'est pas ordonné.

On peut avoir une vision de tous les menus possibles avec un arbre:


\tikzstyle{lien}=[->,>=stealth,rounded corners=5pt,thick]
\tikzset{individu/.style={draw,thick,fill=#1!25},
individu/.default={green}}

{\footnotesize

\begin{tikzpicture}
[level 1/.style={sibling distance=5.15cm},
level 2/.style={sibling distance=1.75cm},
level 3/.style={sibling distance=0.5cm}]
\node [individu=gray] {Menus}
child{ node [individu=blue]{Cuisses}
       child{ node [individu=red]{Turbot}
            child{ node [individu=green]{P}
                 }
            child{ node [individu=green]{B}
                 }
            child{ node [individu=green]{N}
                 }
            }
       child{ node [individu=red]{Chien}
            child{ node [individu=green]{P}
                 }
            child{ node [individu=green]{B}
                 }
            child{ node [individu=green]{N}
                 }
            }
       child{ node [individu=red]{Soupe}
            child{ node [individu=green]{P}
                 }
            child{ node [individu=green]{B}
                 }
            child{ node [individu=green]{N}
                 }
            }
     }
child{ node [individu=blue]{\OE uf}
       child{ node [individu=red]{Turbot}
            child{ node [individu=green]{P}
                 }
            child{ node [individu=green]{B}
                 }
            child{ node [individu=green]{N}
                 }
            }
       child{ node [individu=red]{Chien}
            child{ node [individu=green]{P}
                 }
            child{ node [individu=green]{B}
                 }
            child{ node [individu=green]{N}
                 }
            }
       child{ node [individu=red]{Soupe}
            child{ node [individu=green]{P}
                 }
            child{ node [individu=green]{B}
                 }
            child{ node [individu=green]{N}
                 }
            }
     }
child{ node [individu=blue]{Huîtres}
       child{ node [individu=red]{Turbot}
            child{ node [individu=green]{P}
                 }
            child{ node [individu=green]{B}
                 }
            child{ node [individu=green]{N}
                 }
            }
       child{ node [individu=red]{Chien}
            child{ node [individu=green]{P}
                 }
            child{ node [individu=green]{B}
                 }
            child{ node [individu=green]{N}
                 }
            }
       child{ node [individu=red]{Soupe}
            child{ node [individu=green]{P}
                 }
            child{ node [individu=green]{B}
                 }
            child{ node [individu=green]{N}
                 }
            }
     };
\end{tikzpicture}


}

Pour vous  faire plaisir nous allons  dresser la liste des  menus avec
Haskell  en introduisant  une nouvelle  arme: la  création de  nouveaux
types...


\begin{lstlisting}
data Entree  = Cuisses | Oeufs | Huitres
               deriving (Enum, Show)
data Plat    = Turbot | Chien | Soupe
               deriving (Enum, Show)
data Dessert = Pomme | Banane | Noix
               deriving (Enum, Show)

lesEntrees  = [Cuisses .. ]
lesPlats    = [Turbot .. ]
lesDesserts = [Pomme .. ]

lesMenus = [(e,p,d) | e <- lesEntrees, p <- lesPlats, d <- lesDesserts]
\end{lstlisting}

({\itshape Ici, des commentaires éclairés de votre professeur adoré.})

Et dressons la liste des menus:

\begin{lstlisting}
λ> lesMenus
[(Cuisses,Turbot,Pomme),(Cuisses,Turbot,Banane),(Cuisses,Turbot,Noix),
 (Cuisses,Chien,Pomme),(Cuisses,Chien,Banane),(Cuisses,Chien,Noix),
 (Cuisses,Soupe,Pomme),(Cuisses,Soupe,Banane),(Cuisses,Soupe,Noix),
 (Oeufs,Turbot,Pomme),(Oeufs,Turbot,Banane),(Oeufs,Turbot,Noix),
 (Oeufs,Chien,Pomme),(Oeufs,Chien,Banane),(Oeufs,Chien,Noix),
 (Oeufs,Soupe,Pomme),(Oeufs,Soupe,Banane),(Oeufs,Soupe,Noix),
 (Huitres,Turbot,Pomme),(Huitres,Turbot,Banane),(Huitres,Turbot,Noix),
 (Huitres,Chien,Pomme),(Huitres,Chien,Banane),(Huitres,Chien,Noix),
 (Huitres,Soupe,Pomme),(Huitres,Soupe,Banane),(Huitres,Soupe,Noix) ]
λ> length lesMenus
27
λ> :t lesMenus
lesMenus :: [(Entree, Plat, Dessert)]
\end{lstlisting}

({\itshape Ici, des commentaires éclairés de votre professeur adoré.})

\subsubsection*{Paire ordonnée - Produit de deux ensembles}


Comment créer de l'ordre à partir du désordre...

\begin{definition}[Paire ordonnée]
On note $\langle a,b\rangle = \bigl\{\{a\},\{a,b\}\bigr\}$
\end{definition}


On remarque tout de suite que les rôles de $a$ et $b$ ne sont pas symétriques.

L'égalité des ensembles va nous permettre  de définir une égalité des paires: ce
n'est pas la même! Un(e) informathicien(ne) doit bien s'en rendre compte...

Démontrez tout d'abord que:

\begin{theoreme}
$$(\bigl\{a,b\bigr\} =_{\text{ens}}\bigl\{x,y\bigr\}) \equiv  ((a=x \land b=y) \lor
(a=y \land b=x))$$ 
\end{theoreme}

puis que

\begin{theoreme}
  $$(\langle a,b\rangle =_{\text{paire}}\langle x,y\rangle) \equiv (a=x \land b=y)$$
\end{theoreme}

On  peut alors  définir le  produit (cartésien)  de deux  ensembles comme  étant
l'ensemble des paires formées d'éléments de ces ensembles...


\begin{definition}
 $$A\otimes B = \bigl\{(a,b)\mid (a\in A) \land (b\in B)\bigr\}$$ 
\end{definition}

Pour se repr\'{e}senter le produit cart\'{e}sien $E\otimes F$ avec $%
E=\left\{ a,b,c\right\} $ et $F=\left\{ 1,2,3,4,5\right\} ,$ on peut \'{e}%
videmment l'\'{e}crire en extension: il poss\`{e}de $3\times 5=15$ \'{e}l%
\'{e}ments (voir \`{a} ce sujet le paragraphe suivant).%


$$
E\otimes F=\bigl\{ \left( a,1\right) ,\left( a,2\right) ,\cdots ,\left(
c,5\right) \bigr\}
$$


mais il est souvent pr\'{e}f\'{e}rable de faire appel \`{a} un tableau du
type suivant :%
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$\otimes $ & $\bm{1}$ & $\bm{2}$ & $\bm{3}$ & $\bm{4}$ & $%
\bm{5}$ \\ \hline
$\bm{a}$ & $\left( a,1\right) $ & $\left( a,2\right) $ & $\left(
a,3\right) $ & $\left( a,4\right) $ & $\left( a,5\right) $ \\ \hline
$\bm{b}$ & $\left( b,2\right) $ & $\left( b,2\right) $ & $\left(
b,3\right) $ & $\left( b,4\right) $ & $\left( b,5\right) $ \\ \hline
$\bm{c}$ & $\left( c,1\right) $ & $\left( c,2\right) $ & $\left(
c,3\right) $ & $\left( c,4\right) $ & $\left( c,5\right) $ \\ \hline
\end{tabular}%
\end{center}


Avec  Haskell  :


\begin{lstlisting}
λ> [(x,y) | x <- ['a','b','c'], y <- [1,2,3,4,5]]
[('a',1),('a',2),('a',3),('a',4),('a',5),
 ('b',1),('b',2),('b',3),('b',4),('b',5),
 ('c',1),('c',2),('c',3),('c',4),('c',5)]

λ> [(x,y) | x <- ['a','b','c'], y <- [1,2,3,4,5], mod y 2 == 0]
[('a',2),('a',4),('b',2),('b',4),('c',2),('c',4)]
\end{lstlisting}




Mais comment faire avec notre menu qui a trois plats ordonnés?


\subsubsection*{n-uplets - Produit d'un nombre quelconque d'ensembles}


On peut dire qu'un menu est un couple  formé d'une entrée et d'un couple plat de
résistance-dessert...

Définissons temporairement un triplet ordonné $\langle a,b,c\rangle$ par:
$
\langle a,b,c\rangle = \langle a, \langle b,c \rangle \rangle
$.

\begin{recherche}
  


Est-ce  que c'est  licite? C'est-à-dire  est-ce que  c'est une  définition...qui
définit vraiment  un triplet  ordonné? Qu'est-ce  que ça veut  dire en  fait \og
définit vraiment un triplet ordonné\fg{}?

Comment va-t-on faire alors pour un quadruplet? Un $n$-uplet?

Qu'est-ce que c'est que ça: $
E_{1}\otimes E_{2}\otimes \cdots \otimes
E_{n}=\prod\limits_{i=1}^{n}E_{i}$?

\end{recherche}



Deux fonctions utiles:

\begin{definition}[Projections]
On note $\pi_1$ ($\pi_2$)  la fonction définie sur un produit  $E\otimes F$ qui a
un couple associe sa première (deuxième) composante 
\end{definition}

Sur  Haskell, c'est \verb+fst+ et  \verb+snd+: 

\begin{lstlisting}
λ> fst ('a','b')
'a'

λ> snd ('a','b')
'b'
\end{lstlisting}



\begin{aparte}
  Contrairement à votre  chambre, sur machine, il est beaucoup  plus compliqué de
  créer du désordre que de l'ordre.

Nous suivrons  donc le  cheminement inverse  de ce qui  vient d'être  fait: nous
partirons de $n$-uplets ordonnés et nous créerons des ensembles non ordonnés...
\end{aparte}


\section{Notion de cardinal}\label{cardinal}

  Le  cardinal  d'un  ensemble,  c'est  en gros  le  nombre  de  ses
éléments.  La notion  de cardinal  est intimement  liée à  la  notion de
fonction  et   à  l'ensemble  $\bbn$  des  entiers   naturels  que  nous
détaillerons  plus tard. Nous  nous contenterons  dans un  premier temps
d'une approche intuitive. 
 Le cardinal de $E$
est indiff\'{e}remment not\'{e}:%
$
\card\left( E\right) \text{ ou }\left\vert E\right\vert \text{ ou }%
\#E
$

Par exemple $\left\vert \emptyset \right\vert =0,$ cette notation ne devra
bien s\^{u}r pas \^{e}tre confondue avec la valeur absolue d'un r\'{e}el ou
bien le module d'un nombre complexe. Quoi qu'il en soit, le contexte
permettra g\'{e}n\'{e}ralement de lever l'ambigu\"{\i}t\'{e}.


Nous admettons les r\'{e}sulats suivants qui ne concernent que des ensembles 
\textbf{finis}: il faut  en effet savoir que les ensembles  infinis ont aussi un
cardinal, ce  qu'a introduit \textsc{Cantor}  à la fin du  XIX\eme siècle...Cela
l'a d'ailleurs rendu fou....


\begin{proprietes}
  \begin{itemize}
  \item  Si  $A\subseteq B$  alors  $\bigl|  A\bigr| \leqslant  \bigl|
    B\bigr| .$ Une cons\'{e}quence int\'{e}ressante est celle ci 
: si $A\subseteq B$ avec $\bigl| A\bigr| =\bigl| B\bigr| $ alors $A=B.$

\item $\bigl| A-B\bigr| \leqslant \bigl| A\bigr| .$

\item $\bigl| A\cup B\bigr| =\bigl| A\bigr| +%
\bigl| B\bigr| -\bigl| A\cap B\bigr| $

\item \textbf{Si on a} $E_{i}\cap E_{j}=\emptyset $ \textbf{lorsque} $i\neq
j,$ alors $\left| \bigcup\limits_{i=1}^{n}E_{i}\right|
=\sum\limits_{i=1}^{n}\bigl| E_{i}\bigr| $.

\item $\bigl| E_{1}\otimes E_{2}\bigr| =\bigl|
E_{1}\bigr| .\bigl| E_{2}\bigr| $ et 
\begin{eqnarray*}
\bigl| E_{1}\otimes E_{2}\otimes \cdots \otimes E_{n}\bigr| &=&%
\bigl| E_{1}\bigr| .\bigl| E_{2}\bigr| .\cdots
.\bigl| E_{n}\bigr| \\
\bigl| E^{n}\bigr| &=&\bigl( | E|
\bigr) ^{n}
\end{eqnarray*}

Nous la d\'{e}montrerons en exercice.
  \end{itemize}
\end{proprietes}






















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


\begin{exercice}
  Écrivez en compréhension l'ensemble $ \bbd$ des décimaux, l'ensemble
  $ ℚ$ des rationnels, l'ensemble $ ℂ$ des complexes.

  L'ensemble des réels  $ ℝ$ est un peu plus  délicat à définir malgré
  son nom...
\end{exercice}


\begin{exercice}
L'ensemble universel est $S=\bigl\{1,2,3,4,5\bigr\}$.  Pour chacune des propositions suivantes,
donnez-en la négation puis la valeur de vérité.

\begin{multicols}{2}
\begin{enumerate}
\item $(\exists x)(x + 3 = 10)$
\item $(\forall x)(x +3<10)$
\item $(\exists x )(x+3<5)$
\item $(\forall x)(x+3 \leqslant 7)$
\end{enumerate}
\end{multicols}
\end{exercice}


  \begin{exercice}
    Parmi les ensembles suivants, quels sont ceux qui sont égaux?
    \begin{multicols}{2}
\begin{enumerate}
\item $A=\bigl\{x\mid x\in \bbr \text{ et } x^2-4x+3=0\bigr\}$
\item $B=\bigl\{x\mid x\in\bbr \text{ et } x^2-3x+2=0\bigr\}$
\item $C=\bigl\{x\mid x\in\bbn \text{ et } x<3 \bigr\}$
\item $D=\bigl\{x\mid x\in\bbn  \text{ et } x<5 \text{  et }x \text{ est
      impair }\bigr\}$
\item $E=\bigl\{1,2\bigr\}$
\item $F=\bigl\{1,2,1\bigr\}$
\item $G=\bigl\{3,1\bigr\}$
\item $H=\bigl\{1,1,3\bigr\}$
\end{enumerate} 
\end{multicols}
  \end{exercice}



\begin{exercice}
$E=\left\{ 0,1,2,3,4,5,6\right\} .$ Définir en extension les ensembles
suivants :
 \begin{multicols}{3}
\begin{enumerate}
\item $A_{1}=\left\{ x\in \mathbb{N}\mid x^{2}\in E\right\} $

\item $A_{2}=\left\{ x\in \mathbb{R}\mid x^{2}\in E\right\} $

\item $A_{3}=\left\{ x\in E\mid x^{2}\in E\right\} $

\item $A_{4}=\left\{ x\in E\mid \sqrt{x}\in E\right\} $

\item $A_{5}=\left\{ x\in E\mid 2x\in E\right\} $

\item $A_{6}=\left\{ x\in E\mid \frac{x}{2}\in E\right\} $
\end{enumerate}
\end{multicols}
\end{exercice}



\begin{exercice}
$E=\left\{ 0,1,2,3,4\right\} .$ Compléter, lorsque c'est possible, par
un des symboles (il peut y avoir plusieurs solutions, mais on s'obligera 
\`{a} choisir celle qui donne le plus \og de renseignements\fg{}): 
$$
\in ,\ni ,\subseteq ,\supseteq ,=,\neq ,\varsubsetneq, \not\subseteq
,\cdots$$


\begin{multicols}{4}
\begin{enumerate}
\item $2\cdots E,$ 
\item $\left\{ 2,3\right\} \cdots E,$ 
\item $\left\{ 2\right\} \cdots E$,
\item $\left\{ 2,3,4\right\} \cdots \left\{ 4,3,2\right\} ,$ 
\item $\left\{2,3,4\right\} \cdots \left\{ 4,3,0\right\} $,
\item $\{\} \cdots E,$ 
\item $E\cdots E,$ 
\item $E\cdots \left\{ E\right\} ,$ 
\item $\{\}  \cdots \left\{ E\right\} $,
\item $E\cdots \left\{ 0,1,2,3,\ldots ,10\right\}$,
\item  $\left\{0,1,2,3,4,5\right\} \cdots E$
\end{enumerate}
\end{multicols}

\end{exercice}


  \begin{exercice}
    Soit    $A=\bigl\{1,2,...,8,9\bigr\}$,    $B=\bigl\{2,4,6,8\bigr\}$,
    $C=\bigl\{1,3,5,7,9\bigr\}$,        $D=\bigl\{3,4,5\bigr\}$,
    $E=\bigl\{3,5\bigr\}$ et $\Omega=\bigl\{A,B,C,D,E\bigr\}$.

Écrivez les ensembles suivants par compréhension  puis déterminez les éléments de $\Omega$ qui vérifient les conditions suivantes:

\begin{multicols}{4}
  \begin{enumerate}
  \item $X \cup B=\emptyset$;
  \item $X\subseteq D \land X\not\subseteq B$;
  \item $X\subseteq A \land X\not\subseteq C$;
  \item $X\subseteq C \land X\not\subseteq A$.
  \end{enumerate}
  
\end{multicols}



  \end{exercice}





  \begin{exercice}
    Trouvez des analogies  et des différences entre $\subseteq$  définie sur les
    ensembles et
    $\leqslant $ définie sur les réels.
  \end{exercice}



  \begin{exercice}
    Essayez d'expliquer ce qui se passe:

    \begin{lstlisting}
λ> elem 'Z' "Zorglub"
True
λ> 'Z' `elem` "Zorglub"
True
λ> elem 'Z' "Bulgroz"
False
λ> elem "Zor" "Zorglub"

<interactive>:46:12-20:
    Couldn't match type `Char' with `[Char]'
    Expected type: [[Char]]
      Actual type: [Char]
    In the second argument of `elem', namely `"Zorglub"'
    In the expression: elem "Zor" "Zorglub"
    In an equation for `it': it = elem "Zor" "Zorglub"
λ> all (`elem` "Zorglub") "Zorba"
False
λ> any (`elem` "Zorglub") "Zorba"
True
    \end{lstlisting}

  \end{exercice}


  \begin{exercice}[Complément à 2 puissance n]\label{exo::comp2}
    \begin{quote}
      {\itshape
Le monde se sépare en 10 catégories: ceux qui comprennent cette phrase
et les autres.
}
\begin{flushright}
  {\small Zorglub in \og Les aventures de Zorglub et Martine au Far-West\fg{}}
\end{flushright}
    \end{quote}

Nous  allons,  pour  favoriser  la  compréhension  et  simplifier  les
écritures,  travailler  sur 8  bits.  Cela  signifie que  nos  nombres
entiers peuvent être codés avec 8 chiffres égaux à 0 ou 1 en base 2.

\begin{enumerate}

\item Écrivez les nombres de 0 à 17  en base 2. Quel est le plus grand
  nombre que l'on peut écrire avec 8 bits?
  
\item  En fait,  on aimerait  avoir des  entiers signés,  c'est-à-dire
  pouvoir  représenter des  entiers  tant positifs  que négatifs  avec
  cette contrainte.

  On va donc réserver un bit (le plus à gauche) pour indiquer le signe
  du nombre: on mettra un 0 s'il est positif et un 1 s'il est négatif.

  Écrivez en compréhension l'ensemble des  nombres que l'on peut ainsi
  représenter et qui se note sur Haskell \lstinline{Int8}.

\item  Bon,  pas  de  problème...enfin  si  quand  même  un  peu.  Que
  pensez-vous de ces deux nombres:

  \begin{Verbatim}
    00000000 10000000
  \end{Verbatim}

\item On voudrait additionner facilement  ces nombres. Une idée serait
  d'utiliser l'addition  posée comme  à l'école primaire.  Par exemple
  pour calculer $ 5 + 9$

  \begin{Verbatim}
    00000101
+   00001001
------------
    00001110
  \end{Verbatim}

  On trouve bien 14.
  
  Et maintenant si on veut calculer $ 5 + (-9)$, qu'est-ce que cela donne avec ce système?

\item  Considérez maintenant  le  nombre \lstinline{m  = 11111111}  et
  ajoutez-lui 1  (vous n'avez que  8 bits  à disposition). Que  vaut $
  m+1$? Que cela vous donne-t-il comme idée?

  Considérez \lstinline{n=11111110} et calculez $ n+2$.

  Considérez \lstinline{p=11111100} et calculez $ n+4$.

  Considérez \lstinline{p=11111000} et calculez $ n+8$.

  Considérez \lstinline{p=11111010} et calculez $ n+6$.

  Des idées?

\item Si l'on considère que $  2^8$ vaut 0 en \lstinline{Int8}, ce qui
  est d'ailleurs le cas:

  \begin{lstlisting}
λ> let n = 256 :: Int8
λ> n
0
  \end{lstlisting}

Que pensez-vous alors de $x$ et de $2^8-|x|$ si $ x$ est négatif?

Comment s'écrit $2^8-|x|$ sur 8 bits?

Bon, vous commencez à voir ce qui se passe?

Alors expliquez ce qui se passe ici:

\begin{lstlisting}
λ> let n = 13 :: Int8
λ> n * 2
26
λ> n * 4
52
λ> n * 8
104
λ> n * 16
-48
λ> n * 32
-96
λ> n * 64
64
\end{lstlisting}

Généralisez, énoncez votre  norme de représentation des  entiers sur 8
bits,  énoncez un  \og truc\fg{}  pour trouver  facilement de  tête le
complément à $ 2^8$.


\end{enumerate}


  \end{exercice}




\begin{exercice}
  \begin{enumerate}
  \item  Soit  $A=\bigl\{0,1\bigr\}$.  Déterminer  $\left(A^2\setminus
        \bigl\{(0,0)\bigr\}\right)\otimes A$.
    \item            Soit           $A=\bigl\{3,5,7\bigr\}$           et
          $B=\bigl\{a,b\bigr\}$. Déterminer $A^2$, $B^2$, $A\otimes B$,
          $B\otimes A$, $B^2\otimes A$.
  \end{enumerate}
\end{exercice}

\begin{exercice}[liste en compréhension]

Lire                           avec                          attention
\href{http://lyah.haskell.fr/demarrons\#je-suis-une-liste-en-comprehension}{http://lyah.haskell.fr/demarrons\#je-suis-une-liste-en-comprehension}


puis répondez aux petites questions posées là:
\href{http://informathix.tuxfamily.org/?q=node/89}{http://informathix.tuxfamily.org/?q=node/89}

  
\end{exercice}




\modenormal
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "PolyMD1_14"
%%% End: 
