ocaml-lib-devel — Developer's mailing list

Re: [Ocaml-lib-devel] List.map_pairs

[Richard W. M. J. <ri...@me...>]

On Wed, Aug 10, 2005 at 07:30:42PM +0200, Nicolas Cannasse wrote:
> > On the subject of new list functions, how about:
> >
> > let rec list_map_pairs f = function
> >   | [] | [_] -> invalid_arg "list_map_pairs"
> >   | [x; y] -> [f x y]
> >   | x :: (y :: _ as xs) ->
> >       f x y :: list_map_pairs f xs
> >
> > We use this sort of pattern to disaggregate data which has been
> > collected using an incrementing counter - something like this:
> >
> > # let xs = [ 0; 1; 4; 5; 5; 5; 8; 9; 9; 10 ];;
> > val xs : int list = [0; 1; 4; 5; 5; 5; 8; 9; 9; 10]
> > # list_map_pairs (fun a b -> b - a) xs;;
> > - : int list = [1; 3; 1; 0; 0; 3; 1; 0; 1]
> >
> > Rich.
> 
> I think that it's not very the Ocaml spirit of handling pairs, in general
> you will first transform your "int list" into an "(int * int) list" with
> error handling and then treat pairs uniformly in a typesafe manner.

Well OK, but we don't even have a function to do the
int list -> (int * int) list transformation.

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] List.map_pairs

[Nicolas C. <war...@fr...>]

> On the subject of new list functions, how about:
>
> let rec list_map_pairs f = function
>   | [] | [_] -> invalid_arg "list_map_pairs"
>   | [x; y] -> [f x y]
>   | x :: (y :: _ as xs) ->
>       f x y :: list_map_pairs f xs
>
> We use this sort of pattern to disaggregate data which has been
> collected using an incrementing counter - something like this:
>
> # let xs = [ 0; 1; 4; 5; 5; 5; 8; 9; 9; 10 ];;
> val xs : int list = [0; 1; 4; 5; 5; 5; 8; 9; 9; 10]
> # list_map_pairs (fun a b -> b - a) xs;;
> - : int list = [1; 3; 1; 0; 0; 3; 1; 0; 1]
>
> Rich.

I think that it's not very the Ocaml spirit of handling pairs, in general
you will first transform your "int list" into an "(int * int) list" with
error handling and then treat pairs uniformly in a typesafe manner.

Nicolas

Re: [Ocaml-lib-devel] Proposal for new list functions

[Nicolas C. <war...@fr...>]

> I propose the addition of two new functions into ExtList.List module.
> I've found these to be useful in parsing and manipulating token lists.
> I think these might be useful for other people as well.  I'm not sure
> if the naming is good, so feedback is welcome.  There's already a
> function called "split" in the List module, so I guess I need to come
> up with some other name for it.  The name stems from the functions
> similarity to String.split.

> val fold_left_while :
>    ('a -> 'b -> bool) -> ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

I think too that having an exception is better than providing two functions.
In general you want to stop recursion on a case that can't be treated by
your "fold" , so you're already matching into your fold, with maybe an
assert false in the case you already filtered it. It's better then to group
both test+fold into a single function since I can't see good cases when you
want to freely compose different folds and different stoppers.

> The second function is called split.  I've used it to split lists of
> tokens into sublists (such as splitting argument lists by
> COMMA-token).

>> let split : ('a -> bool) -> 'a list -> 'a list list = <fun>

That one might be useful in some cases.
But it needs a new name ;)

Nicolas

Re: [Ocaml-lib-devel] Proposal for new list functions

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

On Wed, Aug 10, 2005 at 05:00:30PM +0900, Janne Hellsten wrote:
> I don't have a good name to propose for split.  I'd rather rename
> List.split and List.combine to List.unzip and List.zip respectively.
> But I'm not sure if changing the stdlib function names is such a good
> idea.. 

Please don't rename these functions - it would break a lot of our
code, and it's already annoying enough that ExtList/ExtString are
wantonly incompatible with List/String (eg. renaming exceptions,
List.sort - for why?)

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] Proposal for new list functions

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

I can see both these functions being useful to us.

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] List.map_pairs

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

On the subject of new list functions, how about:

let rec list_map_pairs f = function
  | [] | [_] -> invalid_arg "list_map_pairs"
  | [x; y] -> [f x y]
  | x :: (y :: _ as xs) ->
      f x y :: list_map_pairs f xs

We use this sort of pattern to disaggregate data which has been
collected using an incrementing counter - something like this:

# let xs = [ 0; 1; 4; 5; 5; 5; 8; 9; 9; 10 ];;
val xs : int list = [0; 1; 4; 5; 5; 5; 8; 9; 9; 10]
# list_map_pairs (fun a b -> b - a) xs;;
- : int list = [1; 3; 1; 0; 0; 3; 1; 0; 1]

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] Non-blocking IO streams

[Nicolas C. <war...@fr...>]

> Hi,
>
> How do I create an IO stream that's non-blocking, by building classes
> on top of in_chars and out_chars? Is that possible? And, if so, how do
> I use the IO module on non-blocking streams?
>
> Jonathan

Related to IO, I found and fixed today a bug in IO.pipe that was causing
infinite loops on read.

Nicolas

Re: [Ocaml-lib-devel] Proposal for new list functions

[Janne H. <jjh...@gm...>]

> Having gone back and read the first message in this thread- the only
> difference between my code and the original proposed code is:
> 1) I shortened some of the variable names (note that this is not
> necessarily good)
> 2) I created an inner loop function, instead of making fold_left_while
> recursive.
>=20
> Otherwise, my code is identical to the code originally posted.

Yep.  I take it now that fold_left_while is OK as it is now.  If we decide
to add it, we should add fold_right_while as well.  If we make it
tail-recursive, it's actually more convenient than fold_left_while.

Skaller suggested split/fold_*_while should take the rest of the list
as an argument to the while-condition predicate.  I don't like that
idea, especially as it's not orthogonal to the already existing
dropwhile and takewhile functions, or pretty much all the other list
functions taking some ('a -> bool) function as a parameter.

I don't have a good name to propose for split.  I'd rather rename
List.split and List.combine to List.unzip and List.zip respectively.
But I'm not sure if changing the stdlib function names is such a good
idea..  Haskell prelude contains "break" function.  It is similar to
the split function I'm proposing.  But if we add functions that can be
found from Haskell's standard library, we should try to make them
behave similarly.

How about the name "separate" instead of "split"?  That is what it's
doing anyway, isolating parts of a list separated by some values.  I
still think "split" a better name for it though.

Best regards,
Janne

Re: [Ocaml-lib-devel] Proposal for new list functions

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

On Wed, 10 Aug 2005, skaller wrote:

> On Tue, 2005-08-09 at 19:46 -0500, Brian Hurt wrote:
>>
>> I don't think we need an exception to do this.  Wouldn't this do:
>>
>> let fold_left_while f p init lst =
>>      let rec loop accu = function
>>          | h :: t ->
>>              if p h then loop (f accu h) t else accu
>>          | [] -> accu
>>      in
>>      loop init lst
>> ;;
>
> Yes, that's good!

Having gone back and read the first message in this thread- the only 
difference between my code and the original proposed code is:
1) I shortened some of the variable names (note that this is not 
necessarily good)
2) I created an inner loop function, instead of making fold_left_while 
recursive.

Otherwise, my code is identical to the code originally posted.

Brian

Re: [Ocaml-lib-devel] Proposal for new list functions

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

On Tue, 2005-08-09 at 19:46 -0500, Brian Hurt wrote:
>=20
> I don't think we need an exception to do this.  Wouldn't this do:
>=20
> let fold_left_while f p init lst =3D
>      let rec loop accu =3D function
>          | h :: t ->
>              if p h then loop (f accu h) t else accu
>          | [] -> accu
>      in
>      loop init lst
> ;;

Yes, that's good!

> >> The second function is called split.
> >
> > List.split already exists, it splits a list of pairs
> > into two lists, perhaps call it "part"? (short for
> > partition .. but that isn't quite accurate).
>=20
> List.partition already exists as well.

Hence 'part' rather than 'partition'.. but a better
name would be good.

--=20
John Skaller <skaller at users dot sourceforge dot net>

Re: [Ocaml-lib-devel] Proposal for new list functions

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

On Wed, 10 Aug 2005, skaller wrote:

> On Wed, 2005-08-10 at 00:28 +0900, Janne Hellsten wrote:
>
>> First one is called fold_left_while.  It works the same way as
>> fold_left except that it breaks the loop as soon as a "while
>> predicate" returns false.
>
> Sounds good, but must not be implemented as you
> have written it. The real implementation must use an
> inner exception to stop recursing, we do not want
> to uselessly scan the rest of the list after the
> termination condition is found.

I don't think we need an exception to do this.  Wouldn't this do:

let fold_left_while f p init lst =
     let rec loop accu = function
         | h :: t ->
             if p h then loop (f accu h) t else accu
         | [] -> accu
     in
     loop init lst
;;

>> The second function is called split.
>
> List.split already exists, it splits a list of pairs
> into two lists, perhaps call it "part"? (short for
> partition .. but that isn't quite accurate).

List.partition already exists as well.

Brian

Re: [Ocaml-lib-devel] Proposal for new list functions

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

On Wed, 2005-08-10 at 00:28 +0900, Janne Hellsten wrote:

> First one is called fold_left_while.  It works the same way as
> fold_left except that it breaks the loop as soon as a "while
> predicate" returns false.=20

Sounds good, but must not be implemented as you=20
have written it. The real implementation must use an
inner exception to stop recursing, we do not want
to uselessly scan the rest of the list after the
termination condition is found.

> The second function is called split. =20

List.split already exists, it splits a list of pairs
into two lists, perhaps call it "part"? (short for
partition .. but that isn't quite accurate).

******************

Consider generalise both functions so that the predicate=20
takes the whole of the remaining list as an argument, not just the next
element. It is easy to write a predicate to only consider
the first element, for example

fun acc (h::_) -> ...

isn't much harder to write than

fun acc h ->

but now we can pattern match to an arbitrary depth in the tail.

Trivial example of tail match in fold_left_while:
a list of characters finding the real content of the C++
code

here / some // C++ code

requires matching on //, which is two characters

The problem is with "part" (your "split") it no longer makes
sense to drop "the separator".



--=20
John Skaller <skaller at users dot sourceforge dot net>

[Ocaml-lib-devel] Proposal for new list functions

[Janne H. <jjh...@gm...>]

Hi all,

I propose the addition of two new functions into ExtList.List module.
I've found these to be useful in parsing and manipulating token lists.
I think these might be useful for other people as well.  I'm not sure
if the naming is good, so feedback is welcome.  There's already a
function called "split" in the List module, so I guess I need to come
up with some other name for it.  The name stems from the functions
similarity to String.split.

Comments are welcome!


First one is called fold_left_while.  It works the same way as
fold_left except that it breaks the loop as soon as a "while
predicate" returns false.  This is similar to dropwhile and takewhile
functions in List.  I've found this to be useful in many cases.

val fold_left_while :
   ('a -> 'b -> bool) -> ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a =3D <fun>

(* Fold while (while_pred accu x) is true. *)
let rec fold_left_while while_pred f accu =3D function
    [] -> accu
  | x::xs ->=20
      if while_pred accu x then
        fold_left_while while_pred f (f accu x) xs
      else accu

Example:

As an example of its usefulness, let's implement
ExtList.List.takewhile with fold_left_while:

let takewhile f lst =3D=20
  List.rev (fold_left_while (fun _ e -> f e) (fun acc e -> e::acc) [] lst)

* *=20

The second function is called split.  I've used it to split lists of
tokens into sublists (such as splitting argument lists by
COMMA-token).

val split : ('a -> bool) -> 'a list -> 'a list list =3D <fun>

let rec split pred =3D=20
  let rec loop (single_acc,accu) =3D function
      x::xs when pred x ->
        loop ([],single_acc::accu) xs
    | x::xs ->
        loop (x::single_acc,accu) xs
    | [] ->=20
        List.rev (List.map List.rev (single_acc::accu)) in
  loop ([],[])

Example:

# split (fun c -> c =3D 0) [1; 2; 0; 3; 4; 5; 0; 5];;
- : int list list =3D [[1; 2]; [3; 4; 5]; [5]]

Best regards,
Janne

[Ocaml-lib-devel] More about IO Module

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

Hi,

Is it possible to have the IO module's printf support flushing the
output stream when %! is encountered in the format string? Or is this
already supported?

Jonathan

[Ocaml-lib-devel] Non-blocking IO streams

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

Hi,

How do I create an IO stream that's non-blocking, by building classes
on top of in_chars and out_chars? Is that possible? And, if so, how do
I use the IO module on non-blocking streams?

Jonathan

[Ocaml-lib-devel] Re: IO.read_all doesn't work

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

Jonathan Roewen wrote:
> Hi,
> 
> IO.read_all doesn't return anything from my input stream.
> 
> Console.printf "%s" (IO.read_all fin) => ""
> 
> The following code works perfectly, however:
> 
> try while true do
>   Console.printf "%c" (IO.read fin)
> done with _ -> () => contents of the stream.
> 
> Jonathan
> 

Are you using an input stream "type" defined in IO or a custom one? If 
the latter, are you absolutely sure it adheres to the IO standard?

You can see the full standard at

     http://ocaml-programming.de/rec/IO-Classes.html

Of course, the page only defines the class-based interface, but the 
behavior of IO.t streams should be identical.

-- 
Bardur Arantsson
<ba...@im...>
<ba...@sc...>

- New York now leads the world's great cities in the number of
people around whom you shouldn't make a sudden move.
                                  David Letterman, 'The Late Show'

[Ocaml-lib-devel] IO.read_all doesn't work

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

Hi,

IO.read_all doesn't return anything from my input stream.

Console.printf "%s" (IO.read_all fin) =3D> ""

The following code works perfectly, however:

try while true do
  Console.printf "%c" (IO.read fin)
done with _ -> () =3D> contents of the stream.

Jonathan

[Ocaml-lib-devel] Seekable IO streams again

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

Hi,

I believe I've brought this up before, but I'm bringing it up again,
as I'm building an in-memory file system and want to use the IO module
for the interface to it.

However, the lack of seekable streams has pretty much left it near
useless. About the only operations I can do for writing a file is
either truncating it or appending to it (using my own class).

Perhaps you could take a leaf out of the C++ iostreams standard. That
is one hell of a flexible and truly useful IO library, which redone in
OCaml properly would be a kickass addition to Extlib.

Jonathan

Re: [Ocaml-lib-devel] Map with set operations over the keys

[Christophe R. <Chr...@un...>]

> 	symdiff x y = sub (union x y) (inter x y)
> or
> 	sub x y = inter x (symdiff x y)
> 
> Of course one can easily define both with only membership
> test and fold.
> 
> Perhaps if the symmetric difference was provided and named
> 
> 	symdiff
> 
> it would be clear that 'diff' was the substraction.
> 
> 
sub and symdiff are better name anyway ...

-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Chr...@un...
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------

Re: [Ocaml-lib-devel] Map with set operations over the keys

[John S. <sk...@us...>]

On Thu, 2005-06-09 at 13:02 -0700, Martin Jambon wrote:
> On Mon, 6 Jun 2005, Nicolas Cannasse wrote:

> The following signatures seem good to me:
> 
> (* Exception Remove can be raised by the user-given functions and means
>    "do not keep a binding to this key" for both union and inter. *)
> 
> val union :
>   ('key -> 'a -> 'c) -> ('key -> 'a -> 'b -> 'c) -> ('key -> 'b -> 'c) ->
>   ('key, 'a) t -> ('key, 'b) t -> ('key, 'c) t
> 
> val inter :
>   ('key -> 'a -> 'b -> 'c) -> ('key, 'a) t -> ('key, 'b) t -> ('key, 'c) t
> 
> val diff :
>   ('key, 'a) t -> ('key, 'b) t -> ('key, 'a) t


Just a minor comment, unrelated to the actual topic but
concerning these names: it isn't clear from the name
if 'diff' is setwise subtraction or symmetric difference.
It isn't clear in the Ocaml standard library either.
I believe 'diff' is actually subtraction, not the
symmetric difference, which makes the choice
of name extremely unfortunate. Both functions
should be provided, they're both useful and expensive
to compute with a multi-term expression eg: 

	symdiff x y = sub (union x y) (inter x y)
or
	sub x y = inter x (symdiff x y)

Of course one can easily define both with only membership
test and fold.

Perhaps if the symmetric difference was provided and named

	symdiff

it would be clear that 'diff' was the substraction.


-- 
John Skaller, skaller at users.sf.net
PO Box 401 Glebe, NSW 2037, Australia Ph:61-2-96600850 
Download Felix here: http://felix.sf.net

Re: [Ocaml-lib-devel] Map with set operations over the keys

[Martin J. <mar...@em...>]

On Thu, 9 Jun 2005, Martin Jambon wrote:

[...]

> Plus maybe some specialized versions for efficiency and/or convenience.
>
> I am not sure if the gain in performance would be terrific, and

Actually the union between a big and a small map could be quite fast if
some subtrees can be kept unmodified and don't have to be scanned (shared
between the arguments and the result). The algorithm in this case is
close to the one which is used in Set, but scanning systematically each
element on both maps given as arguments is a bit different.


Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr

Re: [Ocaml-lib-devel] Map with set operations over the keys

[Martin J. <mar...@em...>]

On Mon, 6 Jun 2005, Nicolas Cannasse wrote:

> > > I would say it's bad API design to use a "merge" function in order to
> remove
> > > elements.
> > > A more specific function should be provided.
> >
> > I do not think so. When your merge gives accidentally 0, and the value
> > should be removed, you do not want to scan the map once more to remove
> > the zero ...
>
> Then it's no longer a merge...
> What you want is a more generic function that will do a merge+filter.

"reduce" as suggested by Florian seems to be appropriate.

The following signatures seem good to me:

(* Exception Remove can be raised by the user-given functions and means
   "do not keep a binding to this key" for both union and inter. *)

val union :
  ('key -> 'a -> 'c) -> ('key -> 'a -> 'b -> 'c) -> ('key -> 'b -> 'c) ->
  ('key, 'a) t -> ('key, 'b) t -> ('key, 'c) t

val inter :
  ('key -> 'a -> 'b -> 'c) -> ('key, 'a) t -> ('key, 'b) t -> ('key, 'c) t

val diff :
  ('key, 'a) t -> ('key, 'b) t -> ('key, 'a) t


Plus maybe some specialized versions for efficiency and/or convenience.

I am not sure if the gain in performance would be terrific, and
specialized versions of union and inter can easily be defined out of PMap
anyway, so I wouldn't insist too much on having those functions or not.


Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr

Re: [Ocaml-lib-devel] Map with set operations over the keys

[Florian H. <ha...@bi...>]

Nicolas Cannasse wrote:
> After a second though I think it's little overweighted to make the user
> specify a merge function. Why not simply specify that in such cases, the
> item of the first map is selected ?

If I wanted to implement something like googles map-reduce-thingy in ocaml 
(which may be the easiest way to get anything out of a multicore processor), I 
might just want to marshal the results to send them around and use this merge 
function as the reduce operation. So if you don't want to force the user to 
select a merge function, at least don't force him to reimplement union to be 
able to do so, i. e. make it

let union ?(reduce = fun key v1 v2 -> v1) map1 map2 = ...

I strongly support the exception proposal for unwanted values.

Yours, Florian

Re: [Ocaml-lib-devel] Map with set operations over the keys

[Nicolas C. <war...@fr...>]

> If you want to provide a generic point-wise binary combinator for maps,
> the type should be something like:
>
> (key -> 'a option -> 'b option -> 'c option) ->
>    'a t -> 'b t -> 'c t
>
> The first argument is never called with two None arguments, and
> you might prefer to use exception to signal elements to remove, instead
> of a None result, so another type could be:
>
> (key -> 'a -> 'c) -> (key -> 'a -> 'b -> 'c) -> (key -> 'b -> 'c) ->
>   'a -> 'b t -> 'c t
>
>
> In my experience, having such a generic point-wise combinator on
> map-like structures is really useful. Maybe you also want special cases
> (as a convenience for the user but also to optimize the implementation),
> but I really believe a generic version should be offered in the interface.
>
> -- Alain

I agree too.
One generic function for specific uses plus some specific functions  merge /
union / diff for fast (no boxing, no callback) and easy usage.

Nicolas

Re: [Ocaml-lib-devel] Map with set operations over the keys

[Alain F. <Ala...@in...>]

If you want to provide a generic point-wise binary combinator for maps,
the type should be something like:

(key -> 'a option -> 'b option -> 'c option) ->
   'a t -> 'b t -> 'c t

The first argument is never called with two None arguments, and
you might prefer to use exception to signal elements to remove, instead
of a None result, so another type could be:

(key -> 'a -> 'c) -> (key -> 'a -> 'b -> 'c) -> (key -> 'b -> 'c) ->
  'a -> 'b t -> 'c t


In my experience, having such a generic point-wise combinator on
map-like structures is really useful. Maybe you also want special cases
(as a convenience for the user but also to optimize the implementation),
but I really believe a generic version should be offered in the interface.

-- Alain