Haskell : TD

Calculatrice RPN

Une calculatrice RPN travaille avec une pile. Les opérations (par exemple l’addition) travaillent avec les valeurs au sommet de la pile et les y remettent (comme en Factor).

Le but de cet exercice est de factoriser un maximum de code et de limiter la duplication.

Types de base

Le mot-clé « type » permet de déclarer un alias de type. Par exemple, le type chaîne est défini comme:

type String = [Char]

Définir un type Stack comme étant équivalent à une liste d’entiers courts (Int).

Définir un type Operator représentant une fonction travaillant sur la pile. Un tel opérateur prend une pile en paramètre, utilise certaines valeurs et renvoie la nouvelle pile.

Fonctions

Définir ensuite une fonction parseOp ayant comme signature:

parseOp :: String -> Operator

qui, lorsqu’on lui passe les valeurs « + », « - », « * », fait ce qu’on attend intuitivement (la division entière en Haskell est l’opérateur préfixe « div »).

parseOp doit également reconnaître les opérateurs « dup », « swap », « drop » qui, respectivement, duplique le sommet de la pile, échange les deux valeurs au sommet de la pile, efface l’élement au sommet de la pile. « depth » renvoie le nombre d’éléments dans la pile au moment de l’appel, « pick » renvoie le n-ième élément de la pile.

Faire ensuite une fonction eval qui prend une pile et une liste [Operator] et appliquent les opérateurs à la suite.

La signature d’eval sera donc:

eval :: Stack -> [Operator] -> Stack

En utilisant Hoogle, le moteur de recherche spécialisé Haskell, on trouvera le module à importer pour utiliser « hFlush ». De la même manière, on trouvera probablement une fonction existante permettant de séparer une chaîne de caractères en ses différents composants, ce qui sera utile pour implémenter « parse » dont la signature est à deviner.

On pourra tester les opérations à l’aide du programme principal suivant:

repl :: Stack -> IO ()
repl stack = do
  putStr "> "
  hFlush stdout
  line <- getLine
  newstack <- return $ eval stack (parse line)
  putStrLn $ show $ reverse newstack
  repl newstack
main = repl []

Nombres de Peano

Les nombres de Peano permettent de représenter les entiers non-négatifs. 0 est défini comme Zero, 1 comme le successeur de Zero, 2 comme le successeur du successeur de Zero, etc.

Définir, avec « data », un type Peano comme étant un type avec deux constructeurs, Zero (qui ne prend pas d’argument) et Succ (qui prend un nombre de Peano).

On souhaite que le type Peano puisse être une instance de la classe « Num ». Pour cela, il faut définir les opérations suivantes: « + », « - », « * », « signum » (qui renvoie 0, 1 ou -1 selon le signe du nombre passé en argument), « abs » et « fromInteger ».

La déclaration d’instance ressemblera donc à:

instance Num Peano where
  a + b = ...
  a - b = ...

On souhaite également que les nombres de Peano soient regardables : on les instancie donc avec le classe « Show » et on implémentera une méthode « show ». Ils font également partie de « Integral », « Real » et « Enum ».

Retour sur l’interpréteur RPN

Modifier l’interpréteur RPN pour qu’il utilise les nombres de Peano. Pour cela, il faudra rendre les nombres de Peano membres de la classe « Read », et adapter le type de la pile.