Haskell : notes de cours 1 (23 juin 2010)

module Cours1 where
 
-- Importation explicite du prélude en excluant certaines constructions :
--   - Maybe et tous ses constructeurs
--   - repeat
 
import Prelude hiding (Maybe(..), repeat)
 
-- Équivalence entre opérateurs et fonctions. Par exemple, (+) est la
-- fonction correspondant à l'addition et `f` ci-dessous est la version
-- opérateur de la fonction f.
 
x `f` y = x*2 + y*3
g x y = x*2 + y*3
x +!+ y = x*2 + y*3
 
-- Liste infinie de factorielle.
 
facts :: [Integer]
facts = 1 : (zipWith (*) [1..] facts)
 
-- Application partielle de !! qui permet de récupérer le n-ième
-- élément d'une liste.
 
fact :: Int -> Integer
fact = (facts !!)
 
-- Définition de la suite de Fibonacci.
 
fibos :: [Integer]
fibos = 1 : 1 : (zipWith (+) fibos (tail fibos))
 
-- Fonction constante qui, en application partielle, retourne toujours
-- la même chose lorsqu'elle est finalement appliquée.
 
c :: a -> b -> a
c x _ = x
 
-- Fonction qui fait la même chose avec son deuxième argument. J'y ajoute
-- une seconde définition s' qui utilise la fonction identité.
 
s :: a -> b -> b
s a b = c b a
 
s' :: a -> b -> b
s' _ = id
 
-- Équivalent de la fonction prédéfinie flip qui inverse l'ordre des
-- arguments d'une fonction en prenant deux.
 
fl :: (a -> b -> c) -> b -> a -> c
fl f x y = f y x
 
-- Lambda.
 
add = \ x y -> x+y
 
-- Nouveau type de données, affichable.
 
data B = T | F deriving (Show)
 
-- Ce type peut être utilisé pour des comparaisons en fournissant ==.
 
instance Eq B where
         T == T = True
         F == F = True
         _ == _ = False
 
-- Type option similaire à ce qu'on avait fait en Factor.
 
data Maybe a = Just a | Nothing
     deriving (Show)
 
fromJust :: Maybe a -> a
fromJust (Just x) = x
fromJust Nothing = error "empty Maybe"
 
app :: Maybe a -> (a -> Maybe b) -> Maybe b
app (Just x) f = f x
app Nothing _ = Nothing
 
-- Maybe est également un Monad si on fournit les bonnes fonctions.
 
instance Monad Maybe where
         return = Just
         fail _ = Nothing
         (Just x) >>= f = f x
         Nothing >>= _ = Nothing
 
-- Incrémentation de n'importe quel type de Monad si on utilise minc
-- avec la fonction bind (>>=).
 
minc :: (Monad m, Num a) => a -> m a
minc = return.(1+)
 
-- Utilisation de do.
 
mcomplex :: (Monad m, Num a) => m a -> m a
mcomplex x = do
                v <- x
                return $ (v+1)*2
 
-- En appliquant cette fonction à deux listes, on obtient le produit
-- cartésien. Si on l'applique à deux Maybe, on obtient un Maybe.
 
mpair :: Monad m => m a -> m b -> m (a,b)
mpair x y = do
                xx <- x
                yy <- y
                return $ (xx,yy)
 
-- Utilisation d'une fonction normale à l'intérieur d'un monad en la
-- liftant. Ici, nous avons un exemple avec deux paramètres et avec
-- un seul.
 
liftm2 :: Monad m => (a -> b -> c) -> m a -> m b -> m c
liftm2 f x y = do
      xx <- x
      yy <- y
      return $ xx `f` yy
 
liftm :: Monad m => (a -> b) -> m a -> m b
liftm f = (>>= return.f)
 
-- Traduction d'un do en applications successives de >>= et >>.
 
toto = do
     x <- [1,2,3]
     return 3
     return (x*2)
 
--[1,2,3] >>= (\x ->
--        return 3 >> (return (x*2)))
 
-- Utilisation du monad IO.
 
helloworld :: IO ()
helloworld = do
           putStrLn "Hello"
           putStrLn "World"
 
-- Répétition deux fois d'une chaîne saisie par l'utilisateur.
 
repeat :: IO ()
repeat = do
       s <- getLine
       putStrLn s
       putStrLn s
 
-- Exemple de structure avec création de fonction automatique
-- permettant d'extraire les données.
 
data Person = Person { first :: String,
                       last :: String }
                       deriving (Show)
 
-- State monad. On veut garder un état implicite tout en manipulant
-- le contenu du monad avec les fonctions monadiques traditionnelles.
 
data SM s a = SM {runSM :: s -> (s,a)}
 
-- Bien entendu, le state monad est un monad.
 
instance Monad (SM s) where
         return a = SM $ \s -> (s,a)
         (SM x) >>= f = SM $ \ s ->
                           let (s', r) = x s
                               (s'', r') = runSM (f r) s'
                           in (s'', r')
 
-- Récupération du contenu de l'état en le liftant dans le monad.
 
get :: SM s s
get = SM $ \s -> (s,s)
 
-- Remplacement de l'état en ignorant l'état initial.
 
put :: s -> SM s ()
put s = SM $ \_ -> (s, ())
 
-- Modification de l'état. C'est équivalent à
 
--    change f = do
--                 v <- get
--                 put $ f v
 
-- mais l'écriture avec >>= est plis simple et plus lisible.
 
change :: (s -> s) -> SM s ()
change f = get >>= (put.f)
 
-- Exemple d'une fonction factorielle qui ajoute à un état
-- numérique le nombre de multiplications effectuées.
 
fact' :: (Num t, Ord t) => t -> SM Int t
fact' n = if n < 3
          then return n
           else do
               temp <- fact' $ n-1
               change (+1)
               return $ n * temp
 
-- Extraction de l'état.
 
state :: SM s a -> s -> s
state m i = fst $ runSM m i
 
-- Extraction du contenu.
 
content :: SM s a -> s -> a
content m i = snd $ runSM m i
 
-- Illustration de let, where et de la différence de scoping entre
-- les deux.
 
ff x = let y = x+1
       in y * 2
 
gg x = y * 2
       where y = x+1
 
hh x | x >= 3 = x * temp
     | otherwise = seq temp x
    where temp = hh (x-1)