Le langage Haskell

1) Introduction

Son nom vient du mathématicien Haskell Brooks Curry. Haskell est un langage fonctionnel, c'est-à-dire que tout est fait avec des appels de fonction. Il est typé statiquement et implicitement, les types sont vérifiés par le compilateur et il n'est pas nécessaire de les déclarer. Il est paresseux, rien n'est fait avant que ce ne soit nécessaire.

1.1) Le compilateur GHC

GHC (Glasgow Haskell Compiler) est un compilateur libre pour le langage Haskell développé par l'Université de Glasgow sous licence BSD. Pour le télécharger, aller sur le site http://www.haskell.org/

1.2) L'interprèteur GHCi

Il accompagne le compilateur GHC, et permet d'exécuter à la volée des instructions haskell. C'est un interpréteur. Il permet également de lancer des commandes systèmes, de chargement de fichiers, d'édition, d'information, de contrôle, de débugage... Il peut charger des modules compilés ou interprétés.

Pour le lancer dans une fenêtre MSDOS, exécuter GHCi.

WinGHCi est la version graphique de GHCi.

On peut Spécifier l'éditeur que l'on souhaite utiliser (ici l'éditeur Notepad++) en lanceant la commande suivante :
      File|Option Editor : C:\Program Files\SciTE\Notepad++.exe
ou la ligne de commande suivante :
   :set editor C:\Program Files\SciTE\Notepad++.exe

1.3) L'interprèteur Hugs

Hugs est un interpréteur bytecode. Il offre une compilation rapide du Haskell en bytecode et une vitesse d'exécution raisonnable. Il possède aussi une bibliothèque graphique simple. Il permet de lancer des commandes système comme dans l'interpreteur GHCi. Hugs se prête bien à l'apprentissage de Haskell, mais il ne faut pas en déduire que Hugs est une implémentation simpliste. C'est la plus portable et la plus légère des implémentations de Haskell. Pour télécharger l'interpréteur Hugs, aller sur le site http://cvs.haskell.org/Hugs/.

Pour lancer l'interpreteur Hugs dans une fenêtre MSDOS, exécuter la commande "C:\Program Files\WinHugs\hugs.exe".

WinHugs est la version graphique de Hugs.

1.4) Editeur Notepad++

Notpad++ est un éditeur de code source qui prend en charge plusieurs langages dont haskell. Il donne une coloration syntaxique pour de nombreux langages. Pour le télécharger, aller sur le site http://notepad-plus-plus.org/fr/

1.5) Editeur SciTE

SciTE est un éditeur de code source qui prend en charge plusieurs langages. Il donne une coloration syntaxique pour de nombreux langages, et on peut facilement en ajouter d'autres. Pour le télécharger, aller sur le site http://www.scintilla.org/
La partie droite de l'éditeur se comporte comme une fenêtre de commande MSDOS
Pour ajouter le langage Haskell à sa liste de langage, faite comme suit :
   1- Copier le fichier haskell.properties dans le répertoire C:\Program Files\SciTE\
   2- Modifier le fichier SciTEGlobal.propertie (ouvrable dans SciTE via Option|Open Global Options File) comme suit :
       Ajoutez-y l'extention hs dans la commande suivante :
             source.files=*.asm;*.c;*.cc;*.cpp;*.cxx;*.cs;*.h;*.hs;*.hh;*.hxx;*.hp
    Ajoutez-y le langage Haskell dans la commande "menu.language=" entre le langage Gap et Hypertext comme suit :
             ...
       #Gap|g||\
       &Haskell|hs||\
       H&ypertext|html|F12|\
         ...
        Ajoutez-y le langage Haskell dans la liste des imports entre le langage Gap et Hypertext comme suit :
         ...
         #import gap
       import haskell
       import html
       ...

2) Compiler un programme Haskell

Créez le fichier hello.hs et placez-y le programme Haskell suivant :

main = putStrLn "Bonjour"

Compilez-le avec la commande

ghc -o hello hello.hs

Cela crée dans le même répertoire le fichier : hello.o, hello.hi, et le fichier exécutable hello.exe

3) Documents sur le langage Haskell

Documents PDF :

3+5 2**64 2^^64 2^64 11/3 div 104 5 mod 104 5 divMod 104 5 sqrt 2 pi exp 3 0xff 0o77 'a' "Bonjour" reverse "Bonjour"

=> 8 => 1.8446744073709552e19 => 1.8446744073709552e19 => 18446744073709551616 => 3.6666666666666665 => 20 => 4 => (20,4) => 1.4142135623730951 => 3.141592653589793 => 20.085536923187668 => 255 => 63 => 'a' => "Bonjour" => "ruojnoB"

L'opérateur :: sert à spécifier le type, et à le vérifier donc au moment de la compilation. Ainsi x :: Integer retourne x si x peut bien être restreint au type Integer sinon cela déclenche une erreur lors de la compilation. Voici quelques types :

Integer : type des entiers
Int : type des entiers signés sur 32 bits.
Char : type des charactères
[Integer] : type des listes d'entiers
(Char,Integer) : type des couples d'un charactère et d'un entier.

5 :: Integer 'a' :: Char [2,5,4] :: [Integer] ('b',5) :: (Char,Integer) [] :: [Integer] "Bonjour" :: [Char]

=> 5 => 'a' => [2,5,4] => ('b',5) => [] => "Bonjour"

succ : la fonction successeur

succ 2 succ(2) succ(succ 2)

=> 3 => 3 => 4

(succ :: Integer->Integer) 3 (succ :: Integer->Integer)(3::Integer) (succ :: Int->Int)(3::Int)

=> 4 => 4 => 4

(succ :: Int->Int)((succ :: Int->Int)(3)

=> 5

3.9) Définition de fonction

f :: (a,b) -> c
(curry f) :: a->b->c

g :: a->b->c
(uncurry g) :: (a,b) -> c

head et tail peuvent être redéfinis par :
     head (x:_) = x
     tail (_:s) = s

map peut être redéfini par :
     map _ [] = []
     map f (x:q) = f x : map f q

let sum = foldl (+) 0; aplat = foldl (++) []
sum [1,2,3,4,5,6]    => 21
aplat [[1,2],[5,6],[9]]    => [1,2,5,6,9]

until peut être redéfini par :
     until p f x = if p x then x else until p f (f x)

map peut être redéfini par :
      map _ [] = [] et map f (x:q) = f x : map f q

all et any peuvent être redéfinie par :
     all p s = and (map p s)
     any p s = or (map p s)

Les fonctions partielles

(*2) 5 => 10
(2*) 5 => 10
(>0) 2 => True
(1/) 2 => 0.5
(/2) 8 => 4
(+1) 2 => 3

3.9) Quelques algorithmes courants

L'évaluation en profondeur d'abord (innermost) signifie que pour chaque f(x) l'argument x doit être évalué avant la fonction f sur son argument x. Et lorsque toutes les opérations s'évaluent de gauche à droite, cela autorise alors la notation polonaise ou postfixées qui permet comme en Forth de commencer l'évaluation d'une expression au fur et à mesure de sa lecture. L'inconvénient de cette méthode est que l'évaluation de tous les arguments est toujours faites en premiers même si cela n'est pas utile pour le calcul final.

Par contre l'évaluation paresseuse, l'évaluation par l'exterieur d'abord (outermost) signifie que pour chaque f(x) on tente d'évaluer f sur son argument x d'abord, et on évalue x que si c'est necessaire.

f(x)=f(x+1)
g(x)=3
a=1/0

g(f 4) => 3
g a =>3
a => Infinity
f 2 => ne s'arrète jamais...

Les types définie par constructeurs

Les commandes de plateforme :

64 exercices...
:load nom.hs charge le fichier spécifié. En chargeant un fichier "essai.hs" le prompt devient essai>
:load enlève toutes les définitions chargées à l'exception du "prelude"
:also autre.hs charge un autre fichier
:reload répète la dernière commande de chargemant
:edit nom.hs Ouvre le fichier nom.hs
:edit edite le dernier module
:module <module> pose un module for evaluating expressions
:type <expr> affiche le type d'une expression
:? affiche cette liste de commandes
:set <options> set command line options
:set help on command line options
:names [pat] édite tous les noms contenus
:browse <modules> donne la liste des fonctions et leur type dans le module indiqué
:gc force le garbage collecteur
:quit exit Hugs interpreter

 

Une expression s'évalue en une valeur et possède un type static.

Il y a 6 sortes d'identificateurs :

• varid (Variables) : commence par une minuscule ou _
• conid (Constructeurs) : commence par une majuscule
• tyvar (Variable de type) : commence par une minuscule ou _
• tycon (Constructeurs de type) : commence par une majuscule
• tycls (Classes de type) : commence par une majuscule
• modid (Modules) : commence par une majuscule

Type de constructeur de nom différent que type classe. Les noms peuvent être qualifié sauf les typvar et les modid.

3.2 Variables, Constructors, Operators, and Literals
aexp -> qvar (variable)
| gcon (general constructor)
| literal

gcon -> ()
| []
| (,{,})
| qcon
var -> varid | ( varsym ) (variable)
qvar -> qvarid | ( qvarsym ) (qualified variable)
con -> conid | ( consym ) (constructor)
qcon -> qconid | ( gconsym ) (qualified constructor)
varop -> varsym | `varid ` (variable operator)
qvarop -> qvarsym | `qvarid ` (qualified variable operator)
conop -> consym | `conid ` (constructor operator)
qconop -> gconsym | `qconid ` (qualified constructor operator)
op -> varop | conop (operator)
qop -> qvarop | qconop (qualified operator)
gconsym -> : | qconsym

 

 

 

ghc -o prog --make Main

ghc -o executable --make ModuleMain

Commande	Re	Appel exemple	Description
:help :?	:h :?	:help	Affiche la liste des commandes
:cd	:c	:cd C:\dir1	Change le répertoire courant à C:\dir1
:load	:l	:load :load Toto :load *Toto	Charge le module Prélude Charge le module compilé contenu dans le fichier Toto.hs Charge le module non-compilé contenu dans le fichier Toto.hs
:add	:a	:add Toto :add *Toto	Charge le module compilé contenu dans le fichier Toto.o et conserve les références des autres modules.
:module	:m	:m +*Toto :m +Toto :m -Toto :m -*Toto	Spécifit le contexte pour l'évaluation des expressions : Active le module non-compilé Toto Active le module compilé Toto Désactive le module compilé Toto Désactive le module non-compilé Toto
:browse	:bro	:load Toto
:info	:i	:load Toto
:type	:t	:load Toto
:!	:!	:! dir
:main	:ma	:load Toto

 

Commande	Re	Appel exemple	Description
:!	:h :?	:! ghc -o Toto Toto.hs	Affiche la liste des commandes
:cd	:c	:cd C:\dir1	Change le répertoire courant à C:\dir1
:load	:l	:load :load Toto :load *Toto	Charge le module Prélude Charge le module compilé contenu dans le fichier Toto.hs Charge le module non-compilé contenu dans le fichier Toto.hs
:add	:a	:add Toto :add *Toto	Charge le module compilé contenu dans le fichier Toto.o et conserve les références des autres modules.
:module	:m	:m +*Toto :m +Toto :m -Toto :m -*Toto	Spécifit le contexte pour l'évaluation des expressions : Active le module non-compilé Toto Active le module compilé Toto Désactive le module compilé Toto Désactive le module non-compilé Toto
:browse	:bro	:load Toto
:info	:i	:load Toto
:type	:t	:load Toto
:!	:!	:! dir
:main	:ma	:load Toto

Le chemin de recherche pour la découverte de fichiers source est spécifié avec l'option-i

 

La programmation en Haskell se fait dans des modules mis dans des fichiers d'extension hs ou lhs, un module par fichier. Par commodité on utilisera le même nom de module pour le fichier. Les module peuvent être emboités, et le module Data.Bool.Arbre correspond alors au fichier Data\Bool\Arbre.hs

 

:help       # List the diffent types of commands
:?
  

Spécifit le répertoire courant, ici le répertoire c:\dir1

:cd c:\dir1
:c c:\dir1

Spécifier le chemins de recherche des sources, ici les deux répertoires c:\dir1 et c:\dir2

:set -ic:\dir1:c:\dir2
:s -ic:\dir1:c:\dir2

Initialise le chemin à vide, (le répertoire courant)

:set -i
:s -i

:info map
:i map

:browse GHC.Base
:bro GHC.Base

:browse! GHC.Base

:module +Complexe
:m +Complex

:cd   dir   # Change the current directory
:load file  # Read and eval the contents of a file
:reload     # Read and eval the contents of the last file
  

:type expr
:t expr

Debugging

One tip about debugging. A handy function called trace is in the module Debug.Trace. It was the side effect of printing (to stderr) a string and can use used in the middle of computing values to print out an intermediate result.

Debug.Trace.trace :: String -> a -> a
  

It should be used for debugging only, i.e., not for normally printing of results.

f x = g (x+y) (x*y)
f x =
  trace ("f: x=" ++ (show x) ++ ", y= " ++ (show y) ++ "\n")
  (g (x+y) (x*y))

Single line comments are preceded by ``--'' and continue to the end of the line. For example:

7 - 4   -- this is subtraction

Multiline and nested comments begin with {- and end with -}. Thus

{- this is a
   multiline
   comment -}

The literate programming style in Haskell allows you to write *.lhs files in which every line is a comment by default. A line is Haskell code only when it begins with ">".

Anything is a comment unless it begins with ">".
> main = print [ (n, product[1..n]) | n <- [1..20]]

Files that don't have the lhs suffix can be compiled by the compiler by using the -x option.

shell> ghc -x lhs haskell.html

Dans l'interpreteur WinGHCi (ou GHCi) Spécifier les répertoires contenant les fichiers sources par exemple c:\dir1 et c:\dir2, à l'aide de la commande suivante :

:set -ic:\dir1:c:\dir2

ou alors déplacer le répertoire courant à l'aide de la commande suivante :

:cd c:\dir1

 

 

 

La programmation en Haskell se fait dans des modules mis dans des fichiers d'extension hs, un module par fichier. Par commodité on utilisera le même nom de module pour le fichier. Les module peuvent être emboités, et le module Data.Bool.Arbre correspond alors au fichier Data\Bool\Arbre.hs

On crée un répertoire de travail C:\Haskell. Et dans l'intérpréteur, on se positionne sur ce répertoire à l'aides de la commande :

:cd C:\Haskell

On peut exécuter toute commande MSDOS dans l'interpreteur GHCi (ou Hugs) à l'aide de la commande

:! <command>

Et obtenir une aide sur la liste des commandes avec

:?

On charge le fichier du module dans l'interpréteur GHCi (ou Hugs) à l'aide d'une des commandes :

:load C:\Haskell\toto.hs
:load C:\Haskell\toto
:load toto.hs
:load toto
:l C:\Haskell\toto.hs
:l Toto

Puis on pourra lancer l'éditeur avec la comande :

:edit

En ayant préalablement définie l'éditeur que l'on souhaite utiliser avec la commande :

:set editor C:\Program Files\SciTE\SciTE.exe

 

 

 

La fonction factoriel

let f(n) = if n==0 then 1 else n*f(n-1) f(5) f(10)

=> 120 => 3628800

Dans WinHugs la commande let doit comprendre une deuxième partie constituée par la commande in et qui délimite la porté du let.

let f(n) = if n==0 then 1 else n*f(n-1) in (f(3),f(5))

=> (6,120)

Le programme principale s'appel main est peut être lancé avec la commande :main

La fonction factorielle peut se programmer en deux instructions plus lisibles dans un module Std. Les noms de module commence obligatoirement par une majuscule :

Toto.hs

module Std where f(0) = 1 f(n) = n*f(n-1)

On peut charger le module comme suit :

:load Toto f(5) f(10) :main

[1 of 1] Compiling Main ( Toto.hs, interpreted ) => Ok, modules loaded: Main. => 120 => 3628800 => 2432902008176640000

On peut compiler le module comme suit, mais les fonctionalités non déclarée externe ne sont plus utilisable. On peut alors le rechargé sous forme intérprétée :

:! ghc -c toto.hs :load toto f(10) :main main :show modules :load *toto f(5) main :show modules

=> Ok, modules loaded: Main. <interactive>:1:0: Not in scope: `f' => 2432902008176640000 => 2432902008176640000 => Main (toto.hs, toto.o) [1 of 1] Compiling Main ( toto.hs, interpreted ) => 120 => 2432902008176640000 => Main (toto.hs, interpreted)

 

do {putStrLn "hello"; return "yes"} x <- return 42 print x x let x = 12 x let x = error "help!" print x

=> hello    "yes" => 42 => 42 => 12 => *** Exception: help!

 

let f(x,y) = x*y f(2,3) f 2 3 let f x y = x*y f 2 3 f(2,3)

=> 6 Erreur ! ... => 42 Erreur ! ...

let {f op 0 = 0; f op x = x `op` f op (x-1)} f (+) 3

=> 6

Pour autoriser les passages à la ligne dans un bloc de code soumis à l'interpréteur GHCi, on le commence par :{ et on le finit par }:, ainsi la dernière fonction peut s'écrire :

:{ let {f op 0 = 0;      f op x = x `op` f op (x-1)} }: f (+) 3

=> 6

 

:{ let {x=2;      y=[4,56];      a="Bonjour";      w=('a',2);      f x = x**x} }: :show bindings

=> a :: [Char] = _    f :: (Floating a) => a -> a = _    w :: (Char, Integer) = ('a',_)    x :: Integer = _    y :: [Integer] = [_,_]

Si vous activer l'option t, l'intérpréteur GHCi montrera le type de chaque variable affectée :

:set +t let x=("Bonjour",4) let f n = n^2 let f n = n**2 let (x:y) = [1,2,3] x y

=> x :: ([Char], Integer) => f :: (Num a) => a -> a => g :: (Floating a) => a -> a => 1 => [2,3]

let { f op n [] = n ; f op n (h:t) = h `op` f op n t }
f (+) 0 [1..3]

L'inférence des types : L'ordinateur reconnait le type le plus générale de l'object lors de sa construction sans qu'il n'y est besoin que son type soit défini préalablement.

Le polymorphisme paramétrique : une fonction peut s'appliquer à des paramètres avec des types différents d'un appel à l'autre, et produire un résultat de type différents, dépendant des types des paramètres et de la fonction.

Toto.hs

module Md1 where f(0) = 1 f(n) = n*f(n-1)

Titi.hs

module Md2 where import Md1 g(x) = x**x/f(x)