From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id A01247EEF8 for ; Wed, 29 Jul 2015 13:01:38 +0200 (CEST) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of dario.teixeira@nleyten.com) identity=pra; client-ip=217.70.183.198; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="dario.teixeira@nleyten.com"; x-sender="dario.teixeira@nleyten.com"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of dario.teixeira@nleyten.com) identity=mailfrom; client-ip=217.70.183.198; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="dario.teixeira@nleyten.com"; x-sender="dario.teixeira@nleyten.com"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@relay6-d.mail.gandi.net) identity=helo; client-ip=217.70.183.198; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="dario.teixeira@nleyten.com"; x-sender="postmaster@relay6-d.mail.gandi.net"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0A1AQD9sbhVnMa3RtlSCYRYxVVMAQEBAQEBEgEBAQEBBg0JCSEuhFERAlOBRYgqqSCmFopMhS2FDwWMSIUngwGOCZQIg2ECgQpmAQoBAQEBgiWCNoEEAQEB X-IPAS-Result: A0A1AQD9sbhVnMa3RtlSCYRYxVVMAQEBAQEBEgEBAQEBBg0JCSEuhFERAlOBRYgqqSCmFopMhS2FDwWMSIUngwGOCZQIg2ECgQpmAQoBAQEBgiWCNoEEAQEB X-IronPort-AV: E=Sophos;i="5.15,570,1432591200"; d="scan'208";a="141479345" Received: from relay6-d.mail.gandi.net ([217.70.183.198]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/ADH-AES256-SHA; 29 Jul 2015 13:01:38 +0200 Received: from mfilter37-d.gandi.net (mfilter37-d.gandi.net [217.70.178.168]) by relay6-d.mail.gandi.net (Postfix) with ESMTP id 598A8FB882 for ; Wed, 29 Jul 2015 13:01:37 +0200 (CEST) X-Virus-Scanned: Debian amavisd-new at mfilter37-d.gandi.net Received: from relay6-d.mail.gandi.net ([217.70.183.198]) by mfilter37-d.gandi.net (mfilter37-d.gandi.net [10.0.15.180]) (amavisd-new, port 10024) with ESMTP id n48Ugf88vFDN for ; Wed, 29 Jul 2015 13:01:35 +0200 (CEST) X-Originating-IP: 10.58.1.142 Received: from webmail.gandi.net (unknown [10.58.1.142]) (Authenticated sender: dario.teixeira@nleyten.com) by relay6-d.mail.gandi.net (Postfix) with ESMTPA id EB0EEFB881 for ; Wed, 29 Jul 2015 13:01:35 +0200 (CEST) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII; format=flowed Content-Transfer-Encoding: 7bit Date: Wed, 29 Jul 2015 12:01:35 +0100 From: Dario Teixeira To: caml-list@inria.fr Message-ID: <851d996ceba0b46e7b8e3b7e131f0ced@nleyten.com> X-Sender: dario.teixeira@nleyten.com User-Agent: Roundcube Webmail/1.1.2 Subject: [Caml-list] Maps and folds over an AST 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')); }