[Caml-list] Maps and folds over an AST

[Caml-list] Maps and folds over an AST

[Dario Teixeira]

Hi everyone!

I have a library (Lambdoc) that exposes a document AST, and I want
to provide an AST mapper and an AST folder, using the same approach
used by the OCaml compiler's Ast_mapper.  Here's a simplified
version of the AST:

   type inline =
     | Text of string
     | Bold of seq
     | Emph of seq

   and seq = inline list

   type block =
     | Picture of string
     | Paragraph of seq
     | Quote of frag

   and frag = block list


Though I could offer separate APIs for mapping/folding, users will
often want to perform both on the same document, and it's kind
of silly to traverse the AST twice.  Now, I realise that clever
users could piggyback one on top of the other and avoid the double
traversing, but unless I'm missing something, this approach is not
very convenient.

Therefore, I'm thinking a providing a generic "transformer" that
handles both mapping and folding in a single pass (see code at the
end).  Anyway, I'm at bit of a loss concerning the terminology here.
Implementation-wise, I'm just doing a fold that also happens to
reconstruct the AST tree as it goes along.  However, as far as the
user is concerned, it seems as if I'm doing both a map and a fold
over the AST.  My question is about terminology: what is the proper
name for this operation?  (Note that for lack of a better word I've
called this a "morpher" in the code below).

Thanks in advance for your time!
Best regards,
Dario Teixeira

type 'a morpher =
     {
     text: 'a morpher -> 'a -> string -> 'a * inline;
     bold: 'a morpher -> 'a -> seq -> 'a * inline;
     emph: 'a morpher -> 'a -> seq -> 'a * inline;
     picture: 'a morpher -> 'a -> string -> 'a * block;
     paragraph: 'a morpher -> 'a -> seq -> 'a * block;
     quote: 'a morpher -> 'a -> frag -> 'a * block;
     }

let morph_inline morpher acc = function
     | Text str -> morpher.text morpher acc str
     | Bold seq -> morpher.bold morpher acc seq
     | Emph seq -> morpher.emph morpher acc seq

let morph_seq morpher acc seq =
     let f inline (acc_alpha, acc_seq) =
         let (acc_alpha', inline') = morph_inline morpher acc_alpha 
inline in
         (acc_alpha', inline' :: acc_seq) in
     List.fold_right f seq (acc, [])

let morph_block morpher acc = function
     | Picture str   -> morpher.picture morpher acc str
     | Paragraph seq -> morpher.paragraph morpher acc seq
     | Quote frag    -> morpher.quote morpher acc frag

(* Nearly identical to morph_seq; commonality can be factored out *)
let morph_frag morpher acc frag =
     let f block (acc_alpha, acc_frag) =
         let (acc_alpha', block') = morph_block morpher acc_alpha block 
in
         (acc_alpha', block' :: acc_frag) in
     List.fold_right f frag (acc, [])

let identity =
     {
     text = (fun morpher acc str -> (acc, Text str));
     bold = (fun morpher acc seq -> let (acc, seq') = morph_seq morpher 
acc seq in (acc, Bold seq'));
     emph = (fun morpher acc seq -> let (acc, seq') = morph_seq morpher 
acc seq in (acc, Emph seq'));
     picture = (fun morpher acc str -> (acc, Picture str));
     paragraph = (fun morpher acc seq -> let (acc, seq') = morph_seq 
morpher acc seq in (acc, Paragraph seq'));
     quote = (fun morpher acc frag -> let (acc, frag') = morph_frag 
morpher acc frag in (acc, Quote frag'));
     }