English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
Re: Folding in ML (was "OCaml's formatting libraries")
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2007-11-12 (01:21)
From: Till Varoquaux <till.varoquaux@g...>
Subject: Re: Folding in ML (was "OCaml's formatting libraries")
On Nov 10, 2007 2:13 PM, Jon Harrop <jon@ffconsultancy.com> wrote:
> On Saturday 10 November 2007 15:43, Bünzli Daniel wrote:
> > Le 10 nov. 07 à 15:58, Jon Harrop a écrit :
> > > Functional unparsing requires a lot more code,

First let me say that formats are an Opt-in feature: don't like don't
use it. Although on a theoretical point of view I'm not fond of it I
use it on a daily basis. I guess you could say it's a pragmatic
solution. On one hand formats are a hack on the other they are very
useful (and AFAIK there's no way to implement parser combinators in
functional unparsing). That being said functional uparsing printf's
are not as bad as make them sound. It is also a very useful technique
to master: it is the answer to a general class of problems and can be
an elegant to hairy problems. A typical example could be function
transformations composition (take f°g°h when you want f ,g and h to
have eventual additional parameters).

That being there are more succinct solutions to the "printf" problem,
some of them have probably not be found. This is part of a family of
problems you could call the "folding" family. Here are some of the
hacks I know of, I 'd be interested in learning new ones:

let string_of_string s = s
  I) Functional unparsing.

  This technique was first detailed by Olivier Danvy

type ('a,'b) format = (string -> 'a) -> string -> 'b
let (!)f : (_,_) format = fun k acc v -> k (acc ^ (f v))
let (++) (f:(_,_)format) (g:(_,_)format) : (_,_)format = fun x -> f (g x)
let int: (_,_) format = fun x -> !string_of_int x
let string : (_,_) format = fun x -> !string_of_int x
let sprintf (f:(_,_) format) = f (fun s -> s) ""

let myformat:(_,_) format =
  fun x -> (lit "expecting an int:\""++ int ++ lit "\"and a
string:\""++ string ++ lit "\";") x
let _ = sprintf myformat

  Mlton style folding....

  The formats resulting from this solution are very terse. Type-checking is
  very involved and cannot be abstracted easily.

  The mechanics behind are explained on mlton's web page (http://mlton.org/Fold)

  I believe this hack should be attribute to Stephen Weeks.
let endf acc f = f acc

module Fold =
 let fold a f g = g a f
 let step0 h a f = fold (h a) f
 let step1 h a f b = fold (h b a) f

module Foldr =
  let foldr a f = Fold.fold  f (fun g -> g a)
  let step0 h = Fold.step0 (fun g x -> g (h x))
  let step1 h = Fold.step1 (fun b g x -> g (h b x))

let (!) f = fun z -> Foldr.step1 (fun s k ((+),acc,stop) a -> k
((+),(acc + (f a)  + s),stop)) z;;
let (<<) s = Foldr.foldr (fun (_,acc,stop) -> stop acc) (fun k init
stop (+) -> k ((+),init+s,stop))
let (>>) = endf

let sprintf f =
  f (Buffer.create 17) (Buffer.contents) (fun b s -> Buffer.add_string b s;b)

let int k = !string_of_int k
let string k = !string_of_string k

let _ = sprintf ((<<)"expecting an int:\""int"\"and a string:\""string"\";"(>>))


  This one is by me... it requires -rectypes and is a lot more useless than the
  previous ones... I just felt like putting it down anyways

type ('a,'b) acc = (?peak:('b -> unit) -> 'a -> ('a,'b) acc)

let makeAcc init (+) : (_,_) acc  =
  let rec aux acc ?peak =
  (match peak with
   | Some f -> f acc
   | None -> ());
    fun v -> aux (acc+v)
  in aux init

let (|>) x f = f x
let peak (acc:(_,'a) acc) : 'a =
  let res = ref None in
  let set v = res := Some v in
  ignore (acc ~peak:set);
  match !res with
  | Some v -> v
  | None -> assert false

let _ =
  let sum = makeAcc 0 (+) in
  sum 3 4 5 6 |> peak