Salut,

Ce courriel est la suite d'une discussion que j'ai eu aujourd'hui avec Stefan. Elle portait sur l'utilisation de schémas de récursion pour définir les types comme `sexp` et `lexp`. En particulier, le but est simplifier le code en utilisant un point fixe qui n'est pas le plus petit, mais qui insérerait les métadonnées comme les `location` ou le hash dans le cas des `lexp`.

Par exemple, voici une définition « plate » de `sexp` (simplifiée).

type 'carrier sexp_f = | String of string | Integer of integer | Node of 'carrier * 'carrier list

Le plus petit point fixe serait le suivant.

type sexp' = Sexp' of sexp' sexp_f

Dans notre cas, on choisi plutôt d'ajouter un `location`.

type sexp = Sexp of location * sexp' sexp_f

Et on peut définir nos schémas de récursion classiques.

let map (eval : 'a -> 'b) : 'a f -> 'b f = function | String (location, value) -> String (location, value) | Integer (location, value) -> Integer (location, value) | Node (location, head, tail) -> Node (location, eval head, List.map eval tail)

type 'carrier algebra = 'carrier f -> 'carrier

let rec cata (algebra : 'carrier algebra) : t -> 'carrier = function | Sexp (sexp) -> map (cata algebra) sexp |> algebra

type 'carrier coalgebra = 'carrier -> 'carrier f

let rec ana (coalgebra : 'carrier coalgebra) (carrier : 'carrier) : t = Sexp (map (ana coalgebra) (coalgebra carrier))

Le problème est que ces schémas ne sont pas vraiment utiles parce que le location d'un nœud se situe « en haut » de ce nœud et n'est donc pas directement accessible. On peut définir un autre schéma qui ajoute la `location`.

type 'carrier located_algebra = ('carrier * location) f -> 'carrier

À mon ça, suggère plus que la `location` fait bel et bien partie des données.

type 'carrier sexp_f = | String of location * string | Integer of location * integer | Node of location * 'carrier * 'carrier list

Avec cette définition, les schémas bien connus fonctionnent. Nous avons aussi les avantages suivants. * Ça utilise moins de mémoire: 1 bloc par niveau plutôt que 2. * La définition est plus longue, mais le pattern matching plus court. C'est un avantage parce qu'il n'y a qu'une définition, mais plein de pattern matching.

Ma suggestion: conserver les `location` dans chaque constructeur de valeur.

Par contre, pour les hash des `lexp`, je crois que ça peut fonctionner parce qu'on n'y accède pas directement, mais je dois faire plus d'essais pour le confirmer.

Simon