%\RequirePackage{atbegshi}
\documentclass[french]{beamer}
\usepackage{etex}

\usepackage[beamer,utf8,fourier]{preambuleTrm}
%\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage{bookmark,multido}
%\usepackage{xlop}




\usepackage{tikz}
\usetikzlibrary{automata,fit,trees,matrix,arrows,decorations.pathmorphing,shapes.arrows,chains,positioning,intersections,backgrounds,calc,through,mindmap}
\newcommand{\myunit}{1.1cm}
\usepackage{tkz-graph}
\input{patch-tkz-graph}
\usepackage{tikz-qtree}

\usepackage{caption}
\captionsetup{labelformat=empty,font=footnotesize}


\usepackage{media9}

%\usepackage{multimedia}
% \usepackage{cclicenses}
% \usepackage{cclicence}
\setbeamertemplate{theorems}[numbered]




\usepackage{algo}

\renewcommand{\algocommentfont}{\small\ttfamily\itshape}

\newcommand\nor{\downarrow}
\newcommand\nand{\uparrow}
\newcommand\xor{\oplus}

\newcommand\foncpart{\rightarrow\!\!\!\!\!\!\shortmid}
\newcommand\fonctot{\rightarrow}
\newcommand\injpart{\rightarrowtail\!\!\!\!\!\!\!\shortmid}
\newcommand\injtot{\rightarrowtail}
\newcommand\surjpart{\twoheadrightarrow\!\!\!\!\!\!\!\shortmid}
\newcommand\surjtot{\twoheadrightarrow}
\newcommand\bijpart{\rightarrowtail\!\!\!\!\!\!\!\shortmid\!\!\!\!\twoheadrightarrow}
\newcommand\bijtot{\rightarrowtail\!\!\!\!\!\!\!\!\!\twoheadrightarrow}


\newtheorem{exercice}{Exercice}


\setlength{\columnseprule}{0pt}

%\setlength{\parskip}{0pt}

\graphicspath{{/home/moi/IUT/PolyINFO1}{/home/moi/Lycee/TDmaple/2006_7/}{/home/moi/Figures/Arbres_Graphes/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigMaple/}{/home/moi/Photos/Maths/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Lycee/Informatique/XCAS/2008_9/}{/home/moi/Lycee/TDmaple/2008_9/}{/home/moi/IUT/Thierry/Conversions/}{/home/moi/Photos/informathix/}{/home/moi/Lycee/Informatique/PafAlgo/}}




\newcommand\caml{\lstset{numbers=none,language=Caml,xleftmargin=10pt,%
keywordstyle =\small\color{orange!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\small\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!red},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}



\newcommand\haskell{\lstset{numbers=none, escapeinside={(*@}{@*)},language=haskell,xleftmargin=10pt,%
keywordstyle =\footnotesize\color{blue!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\footnotesize\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!blue},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}


\newcommand\prolog{\lstset{numbers=none,language=prolog,xleftmargin=10pt,%
keywordstyle =\color{blue!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!blue},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}


\newcommand\ce{\lstset{numbers=none,language=c,xleftmargin=10pt,%
keywordstyle =\footnotesize\color{blue!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\scriptsize\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!blue},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}

\newcommand\shell{\lstset{numbers=none,language=sh,xleftmargin=10pt,%
keywordstyle =\footnotesize\color{blue!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\footnotesize\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!blue},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}


\setcounter{tocdepth}{1} %\setcounter{page}{0}


\renewcommand\FancyVerbFormatLine[1]{\colorbox{green}{#1}}


\mode<presentation>
{
  \usetheme[secheader]{Madrid}
  % or ...Warsaw

  \setbeamercovered{highly dynamic}
  % or whatever (possibly just delete it)
}
\usepackage{elephantbird}

\newcommand{\triangleup}{\Delta}

\begin{document}


\title[] % (optional, use only with long paper titles)
{Programmation fonctionnelle et Haskell for dummies}

\subtitle{INFO1 - Semaine 41}

\author[] % (optional, use only with lots of authors)
{Guillaume CONNAN }
% - Give the names in the same order as the appear in the paper.
% - Use the inst{?} command only if the authors have different
%   affiliation.

\institute{\textsc{IUT} de Nantes - Dpt d'informatique }% (optional, but mostly needed)

\logo{\includegraphics[scale=0.15]{logo_iut}}

%\logo{\includegraphics[scale=0.15]{big_connan}}

\date[] % (optional, should be abbreviation of conference name)
{Dernière mise à jour: \today{} à \now}
% - Either use conference name or its abbreviation.
% - Not really informative to the audience, more for people (including
%   yourself) who are reading the slides online

\subject{ }


\beamerdefaultoverlayspecification{<+->}

% \AtBeginSubsubsection[]
% {
%   \begin{frame}<beamer>
%     \frametitle{Sommaire}
%  {\scriptsize
% \begin{multicols}{2}
%     \tableofcontents[currentsection,currentsubsection]
%        \end{multicols}
% }

%   \end{frame}
% }




% \AtBeginSubsection[]
% {\scriptsize
%   \begin{frame}<beamer>
%     \frametitle{Sommaire}
%  {\tiny
% \begin{multicols}{2}
%     \tableofcontents[currentsection,currentsubsection]
%        \end{multicols}
% }

%   \end{frame}
% }





\AtBeginSection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection]
       \end{multicols}
}

  \end{frame}
}


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

\beamerdefaultoverlayspecification{<+->}




\newcommand{\TR}{\mathcal{T}}


\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
 \frametitle{Sommaire}
{\scriptsize
\begin{multicols}{2} 
 \tableofcontents
\end{multicols}
}

 
 \end{frame}


\haskell


\section{Born to be lazy}

\begin{frame}[fragile]\frametitle{En C}
 \ce

\begin{lstlisting}
#include <stdio.h>

int somme(int,int);

void main(void)
{ int s,a,b;
  printf("Entrez la valeur du plus petit entier: ");
  scanf("%d" , &a);
  printf("Entrez la valeur du plus grand entier: ");
  scanf("%d" , &b);
  s = somme(a,b);
  printf("La somme des entiers de  %d à %d est %d \n", a,b,s);
}
int somme(int a, int b)
{ int tmp; int som;
  tmp = a;
  som = a;
  while (tmp != b)
   { tmp = tmp + 1;
     som = som + tmp;}
  return som;
}
\end{lstlisting}

\end{frame}




\begin{frame}[fragile]

\shell

\begin{lstlisting}
$ gcc -o somme poly_haskell.c 
$ ./somme
Entrez la valeur du plus petit entier: 1
Entrez la valeur du plus grand entier: 10
La somme des entiers de  1 à 10 est 55 
\end{lstlisting}


\pause

Que s'est-il passé?

\pause

A t-on ce que l'on désirait?


\end{frame}

\haskell

\begin{frame}[fragile]\frametitle{Avec Haskell}
\begin{lstlisting}
somme a b = foldl (+) 0 [a..b]
\end{lstlisting}

\pause

\begin{lstlisting}
*Main> somme 1 10
55
\end{lstlisting}

\pause

\begin{lstlisting}
*Main> sum [1..10]
55
\end{lstlisting}

\end{frame}



\begin{frame}[fragile]
\begin{lstlisting}
somme_fonction f a b = foldl (\accu x -> accu + f(x)) 0 [a..b]
\end{lstlisting}

\pause

\begin{lstlisting}
*Main> somme_fonction (\x -> x^2) 1 10
385
\end{lstlisting}


\end{frame}

\begin{frame}[fragile]

Calculez la somme des carrés impairs inférieurs
à 1000 ?

\pause

En C ?

\pause

\begin{lstlisting}
sum (takeWhile (<1000) (filter odd (map (^2) [1..])))
\end{lstlisting}


\end{frame}


\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.6\textheight]{backus}

John \textsc{Backus} (1924 - 2007)

\pause

 {\itshape 
Much of my work has come from being lazy
}
\end{center}
%\end{figure}



\end{frame}


\section{Les fonctions}


\begin{frame}[fragile]\frametitle{Spécifier}
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.

\pause

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


\end{frame}






\begin{frame}[fragile]\frametitle{Réaliser}
RÉALISER la  fonction  c'est  associer   à  la  fonction  spécifiée  une
  expression. 

 Pour cela, on utilise des \textit{paramètres formels} qui font
  \textit{abstraction} des valeurs particulières qui leur seront ensuite \textit{substituées}.

\pause

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


\end{frame}




\begin{frame}[fragile]\frametitle{Utiliser}
UTILISER a  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:

\pause

  \begin{lstlisting}
*Main> (double 3) + (double 7)
20
  \end{lstlisting}


\end{frame}






\section{Curryfication}



\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.6\textheight]{curry}

Haskell \textsc{Curry} (1900 - 1982)

\end{center}
%\end{figure}



\end{frame}


\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.8\textheight]{curry_t}
\end{center}
%\end{figure}

\end{frame}




\begin{frame}
 Une \textbf{fonction curryfiée} est une fonction de
plusieurs  variables transformée  en une  fonction d'une  seule variable
qui renvoie une fonction ayant une variable de moins...


\pause


Cela permet de créer des fonctions partielles.




\end{frame}


\begin{frame}[fragile]

\begin{lstlisting}
plus x y = x + y
\end{lstlisting}


\pause

\begin{lstlisting}
plus :: Integer -> Integer -> Integer
plus    x          y       =  x + y
\end{lstlisting}

\pause

Associativité

\pause

\begin{lstlisting}
f = plus 3
\end{lstlisting}

\pause

Que vaut \verb+f(5)+?

\pause

\begin{lstlisting}
*Main> f 5
8
\end{lstlisting}

\pause

\begin{lstlisting}
*Main> :t f
f :: Integer -> Integer
\end{lstlisting}

\end{frame}



\begin{frame}
 $\FR(D,A)$ 

\pause

 $\mathtt{plus}\in\FR
\bigl( \bbn, \FR(\bbn,\bbn) \bigr)$
\end{frame}


\section{Un exemple}


\begin{frame}
  \begin{example}
    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.
  \end{example}
\end{frame}



\begin{frame}[fragile]\frametitle{Spécification}
   \begin{lstlisting}
moyenne_olympique4 :: Float -> Float -> Float -> Float -> Float
-- renvoie la moyenne olympique de 4 flottants sous forme d'un flottant
  \end{lstlisting}

\end{frame}



\begin{frame}[fragile]\frametitle{Réalisation}
Nous allons par exemple additionner
  les quatre nombres, retirer le plus grand et le plus petit puis diviser par 2.


\pause

\begin{lstlisting}
*Main> :t min
min :: Ord a => a -> a -> a
\end{lstlisting}


\pause

\begin{lstlisting}
*Main> min 'a' 'b'
'a'
*Main> min 5 3
3
*Main> min "Tralala" "Pouet Pouet"
"Pouet Pouet"
*Main> min True False
False
\end{lstlisting}


\end{frame}

\begin{frame}[fragile]\frametitle{Réalisation}
\begin{lstlisting}
moyenne_olympique4 a b c d =
  (s - mini - maxi) / 2 -- l'expression correspondant à la méthode choisie
  where s = a + b + c + d -- la somme des 4 nombres
        mini = min a (min  b (min c d) ) -- le plus petit des 4
        maxi = max a (max  b (max c d) ) -- le plus grand des 4
\end{lstlisting}


\pause


\begin{lstlisting}
*Main> moyenne_olympique4 10 8 12 14
11.0
\end{lstlisting}

\end{frame}



\section{Polymorphisme - abstraction - récursion - listes}

\begin{frame}
  \begin{example}
    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{example}
\end{frame}

\begin{frame}[fragile]\frametitle{Min et Max polymorphes}

\begin{lstlisting}
min_liste :: (Ord a) => [a] -> a
-- renvoie le mini d'une liste d'éléments ordonnables 
\end{lstlisting}

\pause


\begin{lstlisting}
max_liste :: (Ord a) => [a] -> a
-- renvoie le maxi d'une liste d'éléments ordonnables 
\end{lstlisting}

\pause


\begin{lstlisting}
extr_liste :: (Ord a) => (a -> a -> a) -> [a] -> a
-- renvoie le mini ou le maxi (on choisit en mettant la nature de l'extremum en paramètre) d'une liste d'éléments ordonnables 
\end{lstlisting}



\end{frame}



\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height = 0.9\textheight]{argh}
\end{center}
%\end{figure}

\end{frame}

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


\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{vache}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-0}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-1}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-2}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-3}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-4}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-5}
\end{center}
%\end{figure}

\end{frame}




\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-6}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-0}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-1}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-2}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-3}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-4}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-5}
\end{center}
%\end{figure}

\end{frame}




\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-6}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{hasselhoff-0}
\end{center}
%\end{figure}

\end{frame}




\begin{frame}
  \begin{itemize}
  \item induction
  \item induction mathématique (raisonnement par récurrence)
  \item fonction récurive et type récursif
  \end{itemize}
\end{frame}





\begin{frame}[fragile]\frametitle{Factorielle}

  \begin{itemize}
  \item $n!=1\times 2\times 3 \times\cdots\times n$
    \pause
  \item $n! = \begin{cases}  1 \text{ si n=0}\\ n\times (n-1)! \text{ si } n \geqslant 1 \end{cases} $
    \pause
  \item \texttt{fac(n): si n = 0 alors 1 sinon n * (fac (n - 1))}
    \pause
  \item \texttt{fac(n): si n = 0 alors 1 sinon (fac (n + 1)) / (n + 1) }
  \end{itemize}
  
\end{frame}




\begin{frame}[fragile]\frametitle{Factorielle}
\begin{lstlisting}
fac1 :: Integer -> Integer
fac1    0       =  1
fac1    n       =  n * (fac (n-1))
\end{lstlisting}


\pause


\begin{lstlisting}
*Main> fac1 100
933262154439441526816992388562667004907159682643816214685929638952175
999932299156089414639761565182862536979208272237582511852109168640000
00000000000000000000
\end{lstlisting}


\end{frame}


\begin{frame}[fragile]\frametitle{Factorielle}
 \begin{lstlisting}
fac2 n = fac_boucle n 1
  where 
    fac_boucle 0 accu = accu
    fac_boucle k accu = fac_boucle (k - 1) (k * accu)
  \end{lstlisting}



\end{frame}


\begin{frame}[fragile]\frametitle{Factorielle}
 \begin{lstlisting}
fac3 :: Integer -> Integer
fac3 n = foldl (*) 1 [1..n]
  \end{lstlisting}
\end{frame}

\begin{frame}[fragile]\frametitle{Factorielle}
 \begin{lstlisting}[caption={}]
fac4 :: Integer -> Integer
fac4 n = product [1..n]
  \end{lstlisting}
\end{frame}


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



\begin{frame}
\begin{center}
  Qu'est-ce qu'un mot?
\end{center}
\end{frame}



\begin{frame}
  \og glop\fg{}

\pause

\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}
\end{frame}






\begin{frame}[fragile]\frametitle{}
\begin{lstlisting}
infixr :+

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



\end{frame}





\begin{frame}[fragile]\frametitle{}
\begin{lstlisting}
infixr :+

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



\end{frame}





\begin{frame}[fragile]\frametitle{}
\begin{lstlisting}
infixr :+

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



\end{frame}




\begin{frame}[fragile]\frametitle{}

\begin{lstlisting}
*Main> let m = 'g' :+ 'l'  :+ 'o' :+ 'p' :+ Vide
*Main> m
'g' :+ ('l' :+ ('o' :+ ('p' :+ Vide)))
\end{lstlisting}

\pause


\begin{lstlisting}
*Main> :t m
m :: Mot
\end{lstlisting}


\end{frame}

\begin{frame}[fragile]\frametitle{Sélecteurs}


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


\pause

\begin{lstlisting}
*Main> tete m
'g'
\end{lstlisting}

\pause 

Et la queue?

\end{frame}


\begin{frame}[fragile]{Testeurs}
  \begin{lstlisting}
estVide :: Mot -> Bool
estVide m = m == Vide
  \end{lstlisting}

\pause

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



\end{frame}




\begin{frame}[fragile]{Construire une fonction définie sur un type récursif}

On voudrait compter le nombre de \og a\fg{} dans un mot.

\pause


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

\end{frame}




\begin{frame}[fragile]
  \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}


\pause

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

\end{frame}



\begin{frame}[fragile]\frametitle{Filtrage par motif}
  \begin{lstlisting}
nba2 Vide = 0
nba2 (t :+ q) 
  | t == 'a' = (nba2 q) + 1
  |otherwise =  nba2 q
\end{lstlisting}

\end{frame}


\begin{frame}[fragile]\frametitle{Case}
\begin{lstlisting}
nba3 mot = case mot of Vide     -> 0
                       (t :+ q) -> (nba3 q) + (if t == 'a' then 1 else 0)
\end{lstlisting}
\end{frame}


\begin{frame}\frametitle{Pliage}




\begin{center}
\begin{multicols}{2}
\begin{tikzpicture}[sibling distance=20pt% , every internal node/.style={circle,fill=white,draw=black,text=black}
  ]
\Tree [.: 1
         [.: 2
             [.: 3
                 [.: 4
                    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 1 ] 2 ] 3 ] 4 ];
\end{tikzpicture}
\end{multicols}
\end{center}

\end{frame}

\begin{frame}[fragile]\frametitle{Pliage}


\begin{lstlisting}
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}


\end{frame}


\begin{frame}[fragile]\frametitle{Pliage}
  \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
  \end{lstlisting}
\end{frame}




\begin{frame}[fragile]{Applique}

Mettre en majuscule.

\pause

\begin{lstlisting}
*Main> import Data.Char
*Main Data.Char> toUpper 'g'
'G'
\end{lstlisting}



  
\end{frame}



\begin{frame}
  \begin{center}
    glop -> GLOP ?
  \end{center}
\end{frame}


\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{leviosa}
\end{center}
%\end{figure}

\end{frame}



\end{document}
%%% Local Variables: 
%%% TeX-master: t
%%% End: 
