ocaml-lib-devel — Developer's mailing list

[Ocaml-lib-devel] Re: "ocaml_beginners"::[] A good structure for counting things (?)

[Brian H. <bh...@sp...>]

On Wed, 8 Mar 2006, Richard Jones wrote:

>
> This is a problem I often have - count "things" in an imperative way.
> As an example, read a document and count the frequency of each word in
> the document.

That's not a bad way.  If you want to do it functionally, you could use a 
Map instead of a hash table:

module StringMap = Map.Make(String);

let count_words (f: unit -> string option) =
     let rec loop cnt =
         match (f ()) with
             | None ->
                 List.rev
                     (StringMap.fold (fun k c l -> (k, c) :: l) cnt [])
             | Some(word) ->
                 let cnt =
                     try
                         let c = StringMap.find word cnt in
                         StringMap.add word (c+1) cnt
                     with
                         | Not_found -> StringMap.add word 1 cnt
                 in
                 loop cnt
     in
     loop StringMap.empty
;;

Now, the disadvantage of doing it this way is that it'll probably be 
somewhat slower than using a hash table- doing the find and add are O(log 
N) operations vr.s O(1) operations for hash tables, however the Map based 
implementation has lower constant factors (comparing two strings is 
generally cheap compared to the cost of calculating a hash), so the 
performance loss isn't as large as you might think.

The advantage of doing things this way is that the strings are returned in 
sorted order.  I don't know if this is an advantage or not.  I'd also be 
tempted to return the StringMap instead of the equivelent list- walking a 
string map is about as expensive as walking a list (OK, a little more 
expensive, but not much).  And keeping it in the map allows for O(log N) 
accesses to any given element.  Wether I'd do this or not depends upon 
what uses the calling code has for the table.

I don't think this is a common enough problem to be worth putting into a 
standard library, however.

Brian

[Ocaml-lib-devel] A good structure for counting things (?)

[Richard J. <ri...@an...>]

This is a problem I often have - count "things" in an imperative way.
As an example, read a document and count the frequency of each word in
the document.

The way I normally solve it is something like this:

  let results = Hashtbl.create 31 in
  List.iter (
    fun word ->
      try
        let count = Hashtbl.find results word in
        Hashtbl.replace results word (count+1)
      with Not_found ->
        Hashtbl.add results word 1
  ) words;
  let results =
    Hashtbl.fold (fun word count xs -> (count, word) :: xs) results [] in
  (* ... *)

It's not particularly elegant ...

Is there a better structure that I should be using, or should we add
one to Extlib?

Rich.

PS. Note that "words" is only an example.  In real life I'm processing
gigabytes of "things", and they don't live in a convenient list in
memory either -- hence the imperative approach.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

Re: [Ocaml-lib-devel] Re: String.nsplit empty string

[Richard J. <ri...@an...>]

OK, I've committed this change, so nsplit "" _ ==> []

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

Re: [Ocaml-lib-devel] Re: String.nsplit empty string

[Nicolas C. <nca...@mo...>]

Richard Jones wrote:
> On Mon, Mar 06, 2006 at 09:55:36PM +0100, Bardur Arantsson wrote:
> 
>>Richard Jones wrote:
>>
>>>Currently, String.nsplit "" _ returns a single element list:
>>>
>>>$ ocaml -I +extlib
>>>        Objective Caml version 3.08.3
>>>
>>># #load "unix.cma";;
>>># #load "extLib.cma";;
>>># open ExtString;;
>>># String.nsplit "" ",";;
>>>- : string list = [""]
>>># String.nsplit "execute" ",";;
>>>- : string list = ["execute"]
>>>
>>>I would argue, however, that it'd be much better if it acted like
>>>Perl's split and this was special-cased to return a zero-length list:
>>>
>>
>>I agree. It probably more useful in general.
> 
> 
> Anyone else have any opinion on this?  I would really like to change
> the current implementation.
> 
> Rich.

In general I would say it's not very good idea to change some behavior
in an incompatible way. But in that case I can't see any example relying
on split "" = [""] and not [] so it's ok for me.

Nicolas

[Ocaml-lib-devel] A couple of tiny documentation fixes

[Bardur A. <sp...@sc...>]

Hi all,

I've committed a couple of tiny doc fixes. (See attached diff).

-- 
Bardur Arantsson
<bar...@TH...>
<bar...@TH...>

- Let your anger be like a monkey in a piñata.
                                        The Old Master / Kung Pow

Re: [Ocaml-lib-devel] Re: String.nsplit empty string

[Richard J. <ri...@an...>]

On Mon, Mar 06, 2006 at 09:55:36PM +0100, Bardur Arantsson wrote:
> Richard Jones wrote:
> > Currently, String.nsplit "" _ returns a single element list:
> > 
> > $ ocaml -I +extlib
> >         Objective Caml version 3.08.3
> > 
> > # #load "unix.cma";;
> > # #load "extLib.cma";;
> > # open ExtString;;
> > # String.nsplit "" ",";;
> > - : string list = [""]
> > # String.nsplit "execute" ",";;
> > - : string list = ["execute"]
> > 
> > I would argue, however, that it'd be much better if it acted like
> > Perl's split and this was special-cased to return a zero-length list:
> > 
> 
> I agree. It probably more useful in general.

Anyone else have any opinion on this?  I would really like to change
the current implementation.

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

[Ocaml-lib-devel] Re: String.nsplit empty string

[Bardur A. <sp...@sc...>]

Richard Jones wrote:
> Currently, String.nsplit "" _ returns a single element list:
> 
> $ ocaml -I +extlib
>         Objective Caml version 3.08.3
> 
> # #load "unix.cma";;
> # #load "extLib.cma";;
> # open ExtString;;
> # String.nsplit "" ",";;
> - : string list = [""]
> # String.nsplit "execute" ",";;
> - : string list = ["execute"]
> 
> I would argue, however, that it'd be much better if it acted like
> Perl's split and this was special-cased to return a zero-length list:
> 

I agree. It probably more useful in general.

-- 
Bardur Arantsson
<bar...@TH...>
<bar...@TH...>

- If you want something done properly, kill Baldrick before you
start.
                              Edmund Blackadder, 'Blackadder III'

[Ocaml-lib-devel] String.nsplit empty string

[Richard J. <ri...@an...>]

Currently, String.nsplit "" _ returns a single element list:

$ ocaml -I +extlib
        Objective Caml version 3.08.3

# #load "unix.cma";;
# #load "extLib.cma";;
# open ExtString;;
# String.nsplit "" ",";;
- : string list = [""]
# String.nsplit "execute" ",";;
- : string list = ["execute"]

I would argue, however, that it'd be much better if it acted like
Perl's split and this was special-cased to return a zero-length list:

$ perl -MData::Dumper -e 'print (Dumper (split /,/, ""))'
$ perl -MData::Dumper -e 'print (Dumper (split /,/, "execute"))'
--> $VAR1 = 'execute';
$ perl -MData::Dumper -e 'print (Dumper (split /,/, "execute,him"))'
--> $VAR1 = 'execute';
    $VAR2 = 'him';

The reason is that otherwise you need a special case when dealing with
lists of flags, for example:

let f ?(flags = "") () =
  let flags = String.nsplit flags "," in
  (* following doesn't work because if there are no flags, the
   * inner function is called once with a "" argument
   *)
  List.iter (
    fun flag ->
      (* handle it *)
  ) flags;

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

Re: [Ocaml-lib-devel] ExtLib 1.5 Final

[Peter J. <pe...@jo...>]

Nicolas Cannasse wrote:
> Hi list,
> 
> Just to let you know that after a long time, since looks like nobody is 
> making developments on ExtLib anymore, I packaged and released a 1.5 
> Final version of the library, and updated the website documentation.
> The previous 1.4 was not so much up-to-date so it's better this way.

The findlib META file identifies this release as 1.3 (!).  Could this
please be corrected?

[Ocaml-lib-devel] ExtLib 1.5 Final

[Nicolas C. <nca...@mo...>]

Hi list,

Just to let you know that after a long time, since looks like nobody is 
making developments on ExtLib anymore, I packaged and released a 1.5 
Final version of the library, and updated the website documentation.
The previous 1.4 was not so much up-to-date so it's better this way.

Enjoy !
Nicolas

Re: [Ocaml-lib-devel] Efficiency studies of enums?

[Nicolas C. <nca...@mo...>]

Christian Stork wrote:
> Hi extlibbers,
> 
> Here's a question which came to my mind a long time ago when I first
> looked at the implementation of extlib's enums:
> 
>     What are the measurable benefits of the lazy enum construct compared
>     against the naive alternative of building intermediate data
>     structures?
> 
> I haven't seen any performance measurements.  Obviously, it's a good
> idea for really big arrays/lists, but what should be considered "really
> big" in this context?
> 
> Anyway, just curious,
> Chris

I didn't do any serious benchmarks.
In general, I think that lazy operations tends to be slower than 
imperative ones, especially in OCaml where allocation is very fast. 
Using enums is not a choice of performances but of flexibility.

Nicolas

[Ocaml-lib-devel] Efficiency studies of enums?

[Christian S. <ext...@cs...>]

Hi extlibbers,

Here's a question which came to my mind a long time ago when I first
looked at the implementation of extlib's enums:

    What are the measurable benefits of the lazy enum construct compared
    against the naive alternative of building intermediate data
    structures?

I haven't seen any performance measurements.  Obviously, it's a good
idea for really big arrays/lists, but what should be considered "really
big" in this context?

Anyway, just curious,
Chris

-- 
Chris Stork   <>  Support eff.org!  <>   http://www.ics.uci.edu/~cstork/
OpenPGP fingerprint:  B08B 602C C806 C492 D069  021E 41F3 8C8D 50F9 CA2F

Re: [Ocaml-lib-devel] Pickler (type-safe marshalling)

[skaller <sk...@us...>]

On Wed, 2006-01-11 at 23:30 +1300, Jonathan Roewen wrote:
> > http://devnulled.ath.cx/svn/dst/trunk/kernel/pickle.mli
> > http://devnulled.ath.cx/svn/dst/trunk/kernel/pickle.ml
> >
> > Unfortunately it's not clear what the license is, but a trivial
> > reimplementation from the signature is possible.
> >
> > Rich.
> 
> >From what I understand from SML.NET licence, it should be safe to
> declare our pickler stuff public domain.

Two points here: 

1. If you don't provide convincing evidence someone can copy
your code freely, they are well advised to assume it is
Copyright with no Licence to copy. Even downloading it
would breach copyright, and, you'd be up for Criminal
charges yourself for Inciting a Crime -- by placing
such stuff in easy reach on the Internet.

None of this is likely to happen, and the laws on incitement
vary from country to country, but here, if, for example,
you leave your car keys in your car, you're committing  
the crime of inciting theft.

2. I hear that in Europe "Public Domain" only applies to
a particular media. Thus a work in "Public Domain" on
say Film is NOT copyable on say a DVD. The rights to each
media are separate. [Another eg: Beethoven's Ninth
Symphony is surely in the public domain .. but 
recordings of it, or printings of the score by a publisher
are NOT .. copyright still applies to everything other than
the original score]

Therefore, Public Domain is not recommended by licencing
experts. An explicit Licence permitting copying and modification
on any and all media is preferred.

Whilst it is unlikely any legal action will eventuate 
on minor pieces of software .. if you do wish to encourage
people to use your software it seems like a good idea to
try to make them comfortable about it -- a one line text
in the webpage or source saying Copyright Fred Nurk 2005,
Free for Any Use, or, Licence: LGPL or whatever, seems
like a good idea.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Ocaml-lib-devel] Pickler (type-safe marshalling)

[Jonathan R. <jon...@gm...>]

> http://devnulled.ath.cx/svn/dst/trunk/kernel/pickle.mli
> http://devnulled.ath.cx/svn/dst/trunk/kernel/pickle.ml
>
> Unfortunately it's not clear what the license is, but a trivial
> reimplementation from the signature is possible.
>
> Rich.

From what I understand from SML.NET licence, it should be safe to
declare our pickler stuff public domain.

BTW: this was inspired by the paper: Functional Pearl: Pickler
Combinators (http://research.microsoft.com/~akenn/fun/picklercombinators.pd=
f)

Jonathan

[Ocaml-lib-devel] Pickler (type-safe marshalling)

[Richard J. <ri...@an...>]

This interesting item appeared on the main list:

http://caml.inria.fr/pub/ml-archives/caml-list/2006/01/aca0c9c3739de50e35db65f7620fe7da.en.html

http://devnulled.ath.cx/svn/dst/trunk/kernel/pickle.mli
http://devnulled.ath.cx/svn/dst/trunk/kernel/pickle.ml

Unfortunately it's not clear what the license is, but a trivial
reimplementation from the signature is possible.

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

[Ocaml-lib-devel] ExtLib.findi and ExtArray.findi

[Christian S. <ext...@cs...>]

Hi,

Looking at CVS I see in ExtArray.mli:

  val findi : ('a -> bool) -> 'a array -> int
    (** [findi p a] returns the index of the first element of array [a]
        that satisfies the predicate [p].
        Raise [Not_found] if there is no value that satisfies [p] in the
        array [a].
    *)

and in ExtList.mli:

   val findi : (int -> 'a -> bool) -> 'a list -> (int * 'a)
     (** [findi p e l] returns the first element [ai] of [l] along with its
         index [i] such that [p i ai] is true, or raises [Not_found] if no
         such element has been found. *)

This seems quite inconsistent to me.   IMHO, a library should attempt to
use equivalent type signatures for functions with the same name.  This
does not only make functions easier to remember but it also allows
easier refactoring of code.  For example

    let i = ExtList.findi p coll in ...

should easily be changable to 

    let i = ExtArray.findi p coll in ...

in case that coll is a collection that's first implemented as a list and
then (while tuning performance) is changed to an array.


In the case at hand I would actually advocate to rename ExtList.findi
to ExtLib.index_by since there should also be a 

    val index : 'a -> 'a array -> int

just as String.index, and index_by would simply be the predicated
variant of the standard index function.  ExtArray.findi should still be
available and should be exchangable with ExtList.findi.

What do you think?

Friendly,
Chris

-- 
Chris Stork   <>  Support eff.org!  <>   http://www.ics.uci.edu/~cstork/
OpenPGP fingerprint:  B08B 602C C806 C492 D069  021E 41F3 8C8D 50F9 CA2F

Re: [Ocaml-lib-devel] ExtArray?

[Nicolas P. <nic...@gm...>]

SGksCgpPbiAxMi83LzA1LCBSaWNoYXJkIEpvbmVzIDxyaWNoQGFubmV4aWEub3JnPiB3cm90ZToK
Pgo+IEhlcmUgYXJlIGEgY291cGxlIG1vcmUgZnVuY3Rpb25zIHdoaWNoIEkgcHJvcG9zZSBmb3Ig
YWRkaXRpb24gdG8KPiBFeHRBcnJheToKPgpbLi4uXQoKPgo+ICAgKCogUmFuZG9taXplIGFuIGFy
cmF5IChpbiBwbGFjZSkuICopCj4gICBsZXQgdW5zb3J0IHhzID0KWy4uLl0KCklNSE8gSSB0aGlu
ayB0aGF0IHNodWZmbGUgaXMgYSBtb3JlIHN1aXRhYmxlIG5hbWUgZm9yIHRoZXNlIGZ1bmN0aW9u
cy4KCi0tCk5pY29sYXMgUG91aWxsYXJkIGFrYSBFcnRhaSAgPGVydGFpQGZleWRha2lucy5vcmc+
Cmh0dHA6Ly91dHRrLm9yZyAgICAgIFV0dGsgLS0gVW5pZmllZCBUZXN0IFRvb2wgS2l0Cg==

[Ocaml-lib-devel] Recent Subjects

[Nicolas C. <nca...@mo...>]

Hi list,

I don't use anymore my old mail account so I just resubscribed and 
catchingup with recent threads.

- ExtArray is cool, although ExtLib is trying to "promote" DynArray has 
being more convenient.

- Unzip is implementing the "Inflate" algorithm used by ZLib. They would 
be additional work for supporting the Zip file Format which store 
several files by using this compression algorithm with an index. If 
implemented I'm pretty sure it could be added to the Unzip module.

- I'm interested in a patch for the IO.pipe problem

- The Int32.float_of_bits was only added 3.08 I think so that's why it 
was not part of IO module. Maybe that now a lot of people moved away 
from 3.07 it would be nice to have it (?)

BTW, I'm using ExtLib intensively is several big projects such as the 
MTASC compiler (http://mtasc.org) and the haXe compiler 
(http://haxe.org). The NekoML language (http://nekovm.org) also have its 
standard library designed based on ExtLib experience.

Best,

Nicolas

Re: [Ocaml-lib-devel] ExtArray?

[Richard J. <ri...@an...>]

Here are a couple more functions which I propose for addition to
ExtArray:

  (* Swap two elements in an array. *)
  let swap xs i j =
    if i <> j then (
      let c = xs.(i) in
      xs.(i) <- xs.(j);
      xs.(j) <- c
    )
  
  (* Randomize an array (in place). *)
  let unsort xs =
    let n = Array.length xs in
    for i = 0 to n-2 do
      let j = Random.int (n - i) in
      swap xs i j
    done

If you like those, then one for ExtList:

  (* Randomize a list. *)
  let unsort xs =
    let xs = Array.of_list xs in
    Array.unsort xs;
    Array.to_list xs

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

Re: [Ocaml-lib-devel] Extra function for List

[Richard J. <ri...@an...>]

I like it.

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

[Ocaml-lib-devel] Re: Extra function for List

[Christophe P. <chr...@gm...>]

Hello,

I have looked inside extList.ml and noticed the hackery used to forgo
List.rev to keep functions tail-recursive.  Anyways, here is a new fold_map
that uses the same hackery:

let fold_map f b l =3D
    let rec loop x dst =3D function
        | [] -> x
        | h :: t ->
      let (x', h') =3D f x h in
      let r =3D {hd =3D h'; tl =3D []} in
      dst.tl <- inj r;
      loop x' r t
    in
    let dummy =3D dummy_node() in
    let e =3D loop b dummy l in
    (e, dummy.tl)

cheers,
Christophe

On 12/6/05, Christophe Poucet <chr...@gm...> wrote:
>
> Hello,
> I have here a function I would like to propose for the list module.  It's
> a foldmap.  Basically it's a map but it allows you to pass along a variab=
le
> among the different calls.  Perhaps it could be called foldmap_left such
> that a foldmap_right could be implemented as well.
>
> let foldmap f b l =3D
>   let (e, l') =3D List.fold_left
>    (fun (x, t) a -> let (x', a') =3D f x a in (x', a'::t)) (b, []) l
>   in (e, List.rev l')
>
>
> An example of it's use:
> foldmap (fun a e -> (a+1, e)) 0 [1;2;3] =3D> (3, [1;2;3])
>
> The motivation for this is that sometimes you want to map a certain list
> (imagine for instance a list of statements in a compiler), but you also w=
ant
> to gradually build up a functional environment as you pass down this list=
.
>
> Cheers,
> Christophe
>

[Ocaml-lib-devel] Extra function for List

[Christophe P. <chr...@gm...>]

Hello,
I have here a function I would like to propose for the list module.  It's a
foldmap.  Basically it's a map but it allows you to pass along a variable
among the different calls.  Perhaps it could be called foldmap_left such
that a foldmap_right could be implemented as well.

let foldmap f b l =3D
  let (e, l') =3D List.fold_left
   (fun (x, t) a -> let (x', a') =3D f x a in (x', a'::t)) (b, []) l
  in (e, List.rev l')


An example of it's use:
foldmap (fun a e -> (a+1, e)) 0 [1;2;3] =3D> (3, [1;2;3])

The motivation for this is that sometimes you want to map a certain list
(imagine for instance a list of statements in a compiler), but you also wan=
t
to gradually build up a functional environment as you pass down this list.

Cheers,
Christophe

[Ocaml-lib-devel] Unzip module and zip files

[Jonathan R. <jon...@gm...>]

Hi,

Am I right that Unzip module doesn't work with zip files themselves?
Only individually zipped files? Would gzip'd files work?

Jonathan

Re: [Ocaml-lib-devel] ExtArray?

[Jonathan R. <jon...@gm...>]

How about this for Array.filter?

# let filter pred array =3D
    let j =3D ref 0 in
    for i =3D 0 to Array.length array - 1 do
      if pred array.(i) then (
        array.(!j) <- array.(i); incr j;
      )
    done;
    Array.sub array 0 !j;;
val filter : ('a -> bool) -> 'a array -> 'a array =3D <fun>

Although, it's a destructive update, which is probably not desired...
in which case, add "let array =3D Array.copy array in" before the loop.

I haven't done a benchmark, but I think could be more efficient.

Jonathan

[Ocaml-lib-devel] Re: "ocaml_beginners"::[] Reading/writing binary data

[Mark W. <mj...@ce...>]

Richard Jones writes:
> On Wed, Nov 30, 2005 at 01:45:03PM +0000, Mark White wrote:
> > I've found the IO module in ocaml-lib, which is quite
> > helpful; biggest issue it doesn't seem to read/write
> > single-precision IEEE floats.  I'd be perfectly happy to
> > use doubles internally and convert them at the IO stage.
> 
> This looks like an omission from extlib which ought to be fixed.  I've
> just checked and it doesn't exist in CVS either.
> 
> (X-posted to the extlib development list)

Ok, sure -- a read_single there would make sense.

> Does someone who understands single-precision floating point formats
> want to comment on whether this is possible in pure OCaml?

I've just noticed a work-around using the Int32 module:

    Int32.float_of_bits (IO.read_real_i32 ip)

which seems to do the right thing.

Thanks,
Mark <><