Le carnet web de florence

Malgré son aspect fortement orienté objets, Python propose plusieurs mécansimes de programmation fonctionnelle, comme les fonctions lambda, ou les list comprehension.

Mais il existe en OCaml une fonctionnalité très intéressante qui n'a pas d'équivalent en Python : le pattern matching.

Exemple de code OCaml (factorielle) :

# let rec fact n = match n with
      | 0 -> 1
      | n -> n * fact(n-1);;
val fact : int -> int = <fun>
# fact 0;;
- : int = 1
# fact 1;;
- : int = 1
# fact 2;;
- : int = 2
# fact 3;;
- : int = 6
# fact 4;;
- : int = 24
#

Du coup, j'ai essayé de voir ce qu'on pouvait faire en triturant un peu Python 3, qui apporte certaines nouveautés pouvant êtres utiles, comme (e1, *suite) = liste qui est l'équivalent Python 3 du code OCaml let e1 :: suite = liste.

En annexe se trouve un fichier pmatching.py, qui propose une classe match. Celle-ci permet de définir des pattern matching en Python 3, en réutilisant les mécanismes d'affectation ou les opérateurs de comparaison existants. Ainsi, notre factorielle devient :

>>> from pmatching import match
>>> fact = match(
...     '0 ==', 1,
...     'n =', lambda n, rec: n * rec(n-1)
... )
>>> fact(0)
1
>>> fact(1)
1
>>> fact(2)
2
>>> fact(3)
6
>>> fact(4)
24
>>> 

• Notez dans la définition de la fonction que le premier pattern est une comparaison (égalité) avec 0, alors que le second est une affectation de la valeur à n ;
• notez aussi que dans le premier cas, la valeur retournée est directement l'objet 1, alors que dans le second, la fonction lambda est exécutée, et prends pour paramètre n la variable affectée dans le pattern ;
• notez enfin l'usage du paramètre rec, qui a pour valeur l'instance correspondante de match. Cela est nécessaire pour les appels récursifs, puisque la fonction lambda est exécutée avec l'environnement qui existait au moment de sa définition, et qui ne contenait donc pas encore fact.

Puisque des morceaux de code vallent mieux que des longs discours, voici des exemples de code, d'abord en OCaml puis en Python 3 avec match. Il s'agit des exemples qui sont dans la documentation du module (help(match)).

Calcul de la somme des n premiers entiers :

# let rec sumi n = match n with
	| 0 -> 0
	| n -> n + sumi(n-1);;
val sumi : int -> int = <fun>
# sumi(5);;
- : int = 15

Maitenant en Python, défini de deux manières différentes :

>>> def sumi(n):
...     return match(
...         '0 ==', 0,
...         lambda: n + (sumi(n - 1)),
...     )(n)
...
>>> osumi = match(
...     '0 ==', 0,
...     'n =', lambda rec, n: n + rec(n-1)
... )
>>> x = 5
>>> sumi(x)
15
>>> osumi(x)
15
>>>

À noter : le second cas de la première fonction ne définit pas de pattern : c'est donc le pattern par défaut (et il doit se trouver en dernier).

Calcul de la somme des éléments d'une liste d'entiers :

# let rec lsum lst = match lst with
      | hd :: tl -> hd + lsum(tl)
      | [] -> 0;;
val lsum : int list -> int = <fun>
# lsum([40; 0; 3; -1]);;
- : int = 42

Et en Python :

>>> lsum = match(
...     '[e, *t] =', lambda rec, e, t: e + rec(t),
...     '[] ==', lambda: 0,
... )
>>> lsum([])
0
>>> lsum([40, 0, 3, -1])
42
>>> 

À noter : l'usage de *t de Python 3 pour récupérer la fin de la liste.

Calcul de n éléments de la suite de fibonacci. Ici, OCaml est plus élégant, puisqu'il permet dans un même pattern de faire à la fois des tests d'égalité et des affectations.

# let rec fib n p_2 p_1 = match (n, p_2, p_1) with
  | 0, _, _ -> []
  | n, 1, 1 -> [1; 1; 2] @ (fib (n - 3) 1 2)
  | _ -> (p_2 + p_1) :: (fib (n-1) p_1 (p_2 + p_1));;
val fib : int -> int -> int -> int list = <fun>
# fib 5 1 1;;
- : int list = [1; 1; 2; 3; 5]
# fib 7 1 1;;
- : int list = [1; 1; 2; 3; 5; 8; 13]
# 

Pour faire de même avec Python, match permet d'appliquer plusieurs pattern sur ses différents paramètres. Tous les patterns doivent correspondre pour que le code correspondant soit appelé. Il faut aussi spécifier le nombre de pattern en premier paramètre de match.

>>> fib = match(3,
...     '0 ==', '',      '',      [],
...     'n =',  '1 ==',  '1==',   lambda n, rec:
...                           [1, 1, 2] + rec(n - 3, 1, 2),
...     'n =',  'p_2 =', 'p_1 =', lambda n, p_2, p_1, rec:
...                           [p_2 + p_1] + rec(n - 1, p_1, (p_2 + p_1))
... )
>>> fib(7, 1, 1)
[1, 1, 2, 3, 5, 8, 13]

À noter : l'usage de patterns vides qui correspondent toujours. Ainsi, il suffit que le premier paramètre de fib soit à 0 pour que le premier cas soit appelé.

Ce module n'est qu'un proof of concept, il n'a jamais été utilisé en production. À utiliser à vos risques et périls, tout ça.