Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] [ANN] The Missing Library
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: james woodyatt <jhw@w...>
Subject: Re: [Caml-list] [ANN] The Missing Library
On 28 Apr 2004, at 18:03, skaller wrote:
>
> Sure like to see a monadic/lazy solution to
> the example using streams ..

Let's see... a contrived example... you have a sequence of strings, and 
you'd like to process it into a sequence of different strings with a 
state machine.  What would that look like using my Cf library?

Consider this demonstration:

     (*---
       This is a trivial demonstration of sequences, flows and monadic 
programming
       with the Pagoda Cf library.  It shows how to write a flow that 
reads a
       sequence of strings and writes the sequence of strings with 
duplicates elided,
       using a state-continuation monad, parameterized with the state of 
the set of
       strings already seen in the input.  The flow resulting from 
evaluating the monad
       is then used in a function that operates on lists of strings.
      ---*)
     open Cf_scmonad.Op

     module String_set = Cf_rbtree.Create(String)

     (* val memoize: (string, string) Cf_flow.t *)
     let memoize =
         let rec loop () =
             Cf_flow.readSC >>= fun s ->
             Cf_scmonad.load >>= fun u ->
             if String_set.member s u then
                 loop ()
             else
                 Cf_flow.writeSC s >>= fun () ->
                 let u = String_set.put s u in
                 Cf_scmonad.store u >>= fun () ->
                 loop ()
         in
         Cf_flow.evalSC (loop ()) String_set.null

     (* val uniq: string list -> string list *)
     let uniq s =
         let z = Cf_seq.of_list s in
         let z = Cf_flow.commute memoize z in
         Cf_seq.to_list z

     let test () =
         let s1 = [ "Hello"; "World!"; "Hello"; "AGAIN!" ] in
         let s2 = [ "Hello"; "World!"; "AGAIN!" ] in
         let s2' = uniq s1 in
         if s2 <> s2' then failwith "Error in uniq!"

     ;;test ()
     (*--- End of demonstration ---*)

This is a toy, and it will obviously not produce the most efficient 
program in the world.  To solve this particular problem, in actuality, 
I probably wouldn't use the monad.  I'd just write a quick loop on the 
sequence, and I'd use a mutable hash table for state.

However, the code above begins to illustrate how to build much more 
complicated state machines.  In a real case study, e.g. my 
implementation of RFC 3080, the "loop" function will often be a 
collection of recursive state-event handling functions.


-- 
j h woodyatt <jhw@wetware.com>
markets are only free to the people who own them.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners