Deuxième contact avec Haskell

Échauffement

  1. Écrivez une fonction alterne qui prend un élément sur deux dans une liste. Par exemple alterne [1..5] est égal à [1,3,5].

  2. Définissez une fonction combine :: (a -> b -> c) -> [a] -> [b] -> [c] qui prend en argument :

    • une fonction f,
    • une liste [x1, x2, ...],
    • une seconde liste [y1, y2, ...],

    et retourne la liste des [f x1 y1, f x2 y2, ...] (ayant la même longueur que la plus courte des deux listes en argument).

    Par exemple :

Triangle de Pascal

Nous allons définir le triangle de Pascal.

La fonction nommée combine juste au-dessus s’appelle zipWith dans le Prelude.

  1. En utilisant la fonction zipWith, définissez une fonction pasPascal :: [Integer] -> [Integer] qui calcule une ligne du triangle de Pascal en fonction de la ligne précédente.

  2. Définissez le triangle de Pascal pascal :: [[Integer]] en utilisant la fonction iterate.

    Attention, pascal est une liste infinie : si vous demandez à GHCi de l’afficher, vous devrez l’interrompre (Ctrl-C). Le plus raisonnable est de n’afficher que les premières lignes : take 10 pascal est la liste des 10 premières lignes.

Courbe du dragon

L’objectif de cet exercice est de dessiner la courbe du dragon. Nous allons la représenter de la façon suivante : chaque point sera identifié par ses coordonnées, c’est-à-dire un couple de Float ; la courbe elle-même sera simplement la liste des points.

Nous utiliserons le module Graphics.Gloss pour dessiner la courbe. Ce module définit les deux synonymes de type suivants :

type Point = (Float, Float)
type Path  = [Point]

Comme l’illustre wikipédia, cette courbe peut être construite par itérations successives.

Entre deux points A et B (de coordonnées (xA, yA) et (xB, yB)) d’une itération, nous allons intercaler un point de coordonnées
((xA + xB)/2 + (yB − yA)/2, (yA + yB)/2 + (xA − xB)/2)
à l’itération suivante.

  1. Définissez une fonction pointAintercaler :: Point -> Point -> Point utilisant cette formule.

Attention : pointAintercaler a b et pointAintercaler b a ne sont pas égaux. Pour trois points successifs A, B et C de la courbe, vous intercalerez par exemple à l’itération suivante pointAintercaler a b entre A et B, et pointAintercaler c b entre B et C : il faut cette alternance pour créer la courbe !

  1. Définissez une fonction pasDragon :: Path -> Path qui, à partir de la courbe d’une itération, calcule la courbe à l’itération suivante.

  2. Définissez une fonction dragon :: Point -> Point -> [Path] qui calcule la liste des différentes itérations de la courbe du dragon créée entre les deux points donnés.

Vous pouvez finir en affichant successivement les itérations de la courbe en insérant au début de votre fichier dragon.hs :

import Graphics.Gloss

main = animate (InWindow "Dragon" (500, 500) (0, 0)) white (dragonAnime (50,250) (450,250))

dragonAnime a b t = Line (dragon a b !! (round t `mod` 20))

dragon = -- Là, c’est à vous
         undefined

Vous pourrez consulter la documentation de Gloss (/usr/share/doc/libghc-gloss-doc/html/Graphics-Gloss.html au M5). Cette documentation indique en particulier comment contrôler le programme lancé :

Comme votre programme est interactif, il est plus naturel de le compiler en un exécutable et de lancer le résultat que d’essayer de l’exécuter dans GHCi. Vous pourrez ainsi faire :

$ ghc -Wall dragon.hs
...
$ ./dragon

L’option -Wall de GHC permet d’activer tous les avertissements. Essayez de comprendre ce qu’ils signifient (mais ne vous inquiétez pas si vous ne les comprenez pas tous) !

Vous pourrez bien entendu utiliser un Makefile pour reconstruire dragon quand dragon.hs change, avec une règle :

dragon: dragon.hs
	ghc -Wall dragon.hs

Définition alternative

La courbe du dragon peut aussi être définie en partant de deux points A et B de la façon suivante :

  1. Définissez une fonction dragonOrdre :: Point -> Point -> Int -> Path qui prend en arguments deux points A et B et un ordre et calcule le dragon de cet ordre.

  2. Adapter le canevas de fonction main donné ci-dessus pour utiliser cette version.

Si vous terminez rapidement, vous pouvez poursuivre la lecture du LYAH en français ou en anglais.