ocaml-lib-devel — Developer's mailing list

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

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

On Wed, Nov 30, 2005 at 01:45:03PM +0000, Mark White wrote:
> I'd like to write some OCaml routines to read and write
> large arrays from an (already defined) binary file format,
> in several numeric types (big/little endian, short/long
> ints, single/double prec floats).  Is there a convenient way
> to do this without resorting to writing a C module?
> 
> 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)

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

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: IO.pipe is broken

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

Curiously, I'd like to add, using read_byte repetitively, the
exception is raised properly:

# while true do Printf.printf "%d " (read_byte i) done;;
104 101 108 108 111 32 119 111 114 108 100 Exception: IO.No_more_input.

Jonathan

[Ocaml-lib-devel] IO.pipe is broken

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

Hi,

IO.pipe () is broken. Input wraps around, rather than raising No_more_input=
.

A session from O'Caml:

# #load "extLib.cma";;
# open IO;;
# let (i,o) =3D pipe ();;
val i : IO.input =3D <abstr>
val o : unit IO.output =3D <abstr>
# nwrite o "hello world";;
- : unit =3D ()
# read_all i;;
Interrupted.
# nread;;
- : IO.input -> int -> string =3D <fun>
# nread 16 i;;
Characters 6-8:
  nread 16 i;;
        ^^
This expression has type int but is here used with type IO.input
# nread i 16;;
- : string =3D "hello worldhello"
# nread i 16;;
- : string =3D "hello worldhello"
# really_nread i 16;;
- : string =3D "hello worldhello"
# nread i 255;;
- : string =3D
"hello worldhello worldhello worldhello worldhello worldhello
worldhello worldhello worldhello worldhello worldhello worldhello
worldhello worldhello worldhello worldhello worldhello worldhello
worldhello worldhello worldhello worldhello worldhello worldhe"


This also means you can't use read_all on an input from pipe(), which
is a problem for me.

Jonathan

Re: [Ocaml-lib-devel] ExtArray?

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

On Fri, 25 Nov 2005, Amit Dubey wrote:

> Hi,
>
> Did you do any benchmarks?

Nope.

Brian

Re: [Ocaml-lib-devel] ExtArray?

[Amit D. <ami...@gm...>]

Hi,

Did you do any benchmarks?  I did a quick, creating 10000 arrays of random
size between 0-1000 (a couple preliminary tests of size 0-10000 elements
gave a similar trend).  On average,  I get results like:

byte code:
jones 6.9 (from CVS)
hurt 7.2 (from email)
skaller  5.8 (list with remembered size - see below)

native code:
jones  0.82
hurt  0.80
skaller 0.72

So, it would seem that the version which uses lists + length as an
intermediate representation is the fastest.  Caveat: I probably didn't run
it long enough/with large enough arrays to test the effects of garbage
collection. Brian's version might be better in these cases, but that may
require more in-depth testing.  But Max's version is much simpler! :)

I think these results suggest that it may make a lot of sense to have
find_all return a list.  (As Max suggested, perhaps a common function calle=
d
by both find_all and filter, which returns list * length).

-Amit

(Code for skaller below)

let filter f a =3D
    let result =3D ref [] in
    let n =3D ref 0 in
        Array.iter
            (fun x ->
                if f x then begin
                    result :=3D x :: !result;
                    incr n
                end)
            a;
    match !result with
    | []    ->    [| |]
    | x::xs    ->
        let filtered =3D Array.create !n x in
        let rec fill i =3D function
        | []    -> filtered
        | x::xs -> filtered.(i) <- x; fill (i+1) xs
        in
            fill 1 xs;;

On 11/25/05, Richard Jones <ri...@an...> wrote:
>
>
> I've changed the implementation of Array.filter to use BitSets at your
> suggestion.  The version using the actual BitSet type is quite a bit
> shorter than your version.
>
> I've also implemented Array.partition along the same lines.
>
> 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
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by: Splunk Inc. Do you grep through log
> files
> for problems?  Stop!  Download the new AJAX search engine that makes
> searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
> http://ads.osdn.com/?ad_id=3D7637&alloc_id=3D16865&op=3Dclick
> _______________________________________________
> ocaml-lib-devel mailing list
> oca...@li...
> https://lists.sourceforge.net/lists/listinfo/ocaml-lib-devel
>

Re: [Ocaml-lib-devel] ExtArray?

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

I've changed the implementation of Array.filter to use BitSets at your
suggestion.  The version using the actual BitSet type is quite a bit
shorter than your version.

I've also implemented Array.partition along the same lines.

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] ExtArray?

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

On Fri, 25 Nov 2005, Jonathan Roewen wrote:

> IMO, Array.filter should return an array of the same size. Reason:
> whilst arrays are mutable, they are not resizable.

Which makes the usefullness of this function deeply questionable, I agree.

>
> Then it's just a specialised Array.map.
>
> let filter pred = map (fun elt -> if pred elt then Some elt else None);;

This is simple enough, I don't see why a new library function is needed. 
The changing size version is complicated enough I don't want to be 
constantly recoding it.

Brian

Re: [Ocaml-lib-devel] ExtArray?

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

IMO, Array.filter should return an array of the same size. Reason:
whilst arrays are mutable, they are not resizable.

Then it's just a specialised Array.map.

let filter pred =3D map (fun elt -> if pred elt then Some elt else None);;

find_all then builds a list by unwrapping all values Some 'a from filter.

My 2c,

Jonathan

Re: [Ocaml-lib-devel] ExtArray?

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

On Thu, 24 Nov 2005, Richard W. M. Jones wrote:

> On Thu, Nov 24, 2005 at 03:56:20PM +0000, Amit Dubey wrote:
>>> Array.filter
>>>> Array.find_all
>>>> Array.partition
>>>>
>>>> Would these return lists or arrays?
>>>
>>> I think it's better to return arrays, but what do people think about
>>> that?
>>
>> Actually, I agree it makes complete sense for partition.  As I think about
>> it, I think filter and find_all should be different.  find_all should return
>> a list, and filter should return an array.  And possibly, filter should be
>> defined in terms of find_all.
>
> Perhaps you can share your thinking on this :-)
>
> I think the principle of least surprise is going to be that
> Array.filter should return an array - this is surely what users would
> expect.  The problem will be in the implementation which may require
> two passes -- it could be solved better if there was a truncation
> primitive for arrays.

I wonder if something like this (coding into email- ymmv) might work:

let filter f arr =
     let len = Array.length arr in
     if len == 0 then
         [| |]
     else
     let bits = String.make ((len + 7)/8) '\000' in
     let rec loop i c =
         if (i >= len) then
             c
         else
             if f arr.(i) then
                 begin
                     bits.[i/8] <- char_of_int (
                         (int_of_char bits.[i/8]) lor (1 lsl (i mod 8))
                     );
                     loop (i+1) (c+1)
                 end
             else
                 loop (i+1) c
     in
     let rlen = loop 0 0 in
     if rlen == 0 then
         [| |]
     else
     let rarr = Array.make rlen arr.(0) in
     let rec loop2 i j =
         if j >= rlen then
             rarr
         else if (((int_of_char bits.[i/8]) lsr (i mod 8)) land 1) == 1
         then
 	            begin
                 rarr.(j) <- arr.(i);
                 loop2 (i+1) (j+1)
             end
         else
             loop2 (i+1) j
     in
     loop2 0 0
;;

OK, that's a little more complicated than I originally envisioned.  But 
the idea is to use a bit field (in this case a string) to hold the 
"results" of the filter function- 0 for not copying the element over and 1 
for copying the element over.  So we do two passes, but the filter 
function is only called for one- on the second pass, we just use the saved 
results.

Brian

Re: [Ocaml-lib-devel] extlib on OS X

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

Dave Harrison wrote:
> Quick question, I installed ocaml using darwinports, and now I want to install
> extlib.  I tried downloading and running the install, but I get this message :
> 
>> sh: line 1: ocamlfind: command not found
>> Findlib not found.
> 
> Googling around hasn't brought me much luck in solving this, has anyone got any
> advice on what I can do to fix this ?

What needs fixing?  You don't need findlib (you probably want it, but
it's not needed to install extlib), so the fact that it hasn't been
found shouldn't be a problem.

The installer should continue after that message - is it actually
aborting, and if so, is it printing any error messages?

Fwd: [Ocaml-lib-devel] extlib on OS X

[William N. <wne...@cs...>]

> Quick question, I installed ocaml using darwinports, and now I want  
> to install
> extlib.  I tried downloading and running the install, but I get  
> this message :
>
>> sh: line 1: ocamlfind: command not found
>> Findlib not found.
>
>
> Googling around hasn't brought me much luck in solving this, has  
> anyone got any
> advice on what I can do to fix this ?

I don't believe there's a port set up for findlib.  Just DL and  
install it manually.  You can get it at <http://www.ocaml- 
programming.de/packages/>.

I just manage my ocaml install manually on OS X.  Fink and  
Darwinports are light on resources, and GODI is nowhere near mature  
enough -- at least with OS X.

William D. Neumann

"I eat T-bone steaks, I lift barbell plates, I'm sweeter than a
German chocolate cake. I'm the reflection of perfection, the number
one selection. I'm the man of the hour, the man with the power, too
sweet to be sour. The ladies' pet, the men's regret, where what you
see is what you get, and what you don't see, is better yet."

          --Superstar Billy Graham

Re: [Ocaml-lib-devel] extlib on OS X

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

On Fri, Nov 25, 2005 at 09:05:03AM +1100, Dave Harrison wrote:
> Quick question, I installed ocaml using darwinports, and now I want to install
> extlib.  I tried downloading and running the install, but I get this message :
> 
> > sh: line 1: ocamlfind: command not found
> > Findlib not found.

ocamlfind is part of a package called findlib.  I'm not familiar with
darwinports, because I'm using GODI on OS X which supplies ocamlfind
as a rather fundamental component.  However I'm sure that darwinports
should provide this package somewhere.

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 on OS X

[Dave H. <da...@cr...>]

Hi all,

Quick question, I installed ocaml using darwinports, and now I want to install
extlib.  I tried downloading and running the install, but I get this message :

> sh: line 1: ocamlfind: command not found
> Findlib not found.


Googling around hasn't brought me much luck in solving this, has anyone got any
advice on what I can do to fix this ?

Cheers
Dave

Re: [Ocaml-lib-devel] ExtArray?

[Amit D. <ami...@gm...>]

Hi,

I can't see the CVS version, but I have a couple questions:

(1) What is the point of having two rev functions?  Arrays are indexed, you
can just access n-i instead of i.

(2) find_all should return a list.  e.g. find_all in ExtHashtbl returns a
list.

-Amit

On 11/24/05, Richard Jones <ri...@an...> wrote:
>
>
> In CVS is an untested implementation with the following interface.
> I'm currently writing some tests for extlib-test.
>
> module Array :
> sig
>
>   (** {6 New functions} *)
>   val rev : 'a array -> 'a array
>     (** Array reversal. *)
>
>   val rev_in_place : 'a array -> unit
>     (** In-place array reversal.  The array argument is updated. *)
>
>   val for_all : ('a -> bool) -> 'a array -> bool
>     (** [for_all p [a1; ...; an]] checks if all elements of the array
>         satisfy the predicate [p].  That is, it returns
>         [ (p a1) && (p a2) && ... && (p an)].
>     *)
>
>   val exists : ('a -> bool) -> 'a array -> bool
>     (** [exists p [a1; ...; an]] checks if at least one element of
>         the array satisfies the predicate [p].  That is, it returns
>         [ (p a1) || (p a2) || ... || (p an)].
>     *)
>
>   val mem : 'a -> 'a array -> bool
>     (** [mem m a] is true if and only if [m] is equal to an element of
> [a]. *)
>
>   val memq : 'a -> 'a array -> bool
>     (** Same as {!Array.mem} but uses physical equality instead of
>         structural equality to compare array elements.
>     *)
>
>   val find : ('a -> bool) -> 'a array -> 'a
>     (** [find p a] returns 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].
>     *)
>
>   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].
>     *)
>
>   val filter : ('a -> bool) -> 'a array -> 'a array
>     (** [filter p a] returns all the elements of the array [a]
>         that satisfy the predicate [p].  The order of the elements
>         in the input array is preserved.  *)
>
>   val find_all : ('a -> bool) -> 'a array -> 'a array
>     (** [find_all] is another name for {!Array.filter}. *)
>
> (* -- NOT IMPLEMENTED
>   val partition : ('a -> bool) -> 'a array -> 'a array * 'a array
>     (** [partition p a] returns a pair of arrays [(a1, a2)], where
>         [a1] is the array of all the elements of [a] that
>         satisfy the predicate [p], and [a2] is the array of all the
>         elements of [a] that do not satisfy [p].
>         The order of the elements in the input array is preserved. *)
> *)
>
>   (** {6 Old functions} *)
>
>   (** These functions are already part of the Ocaml standard library
>       and have not been modified. Please refer to the Ocaml Manual for
>       documentation. *)
>
>   external length : 'a array -> int =3D "%array_length"
>   external get : 'a array -> int -> 'a =3D "%array_safe_get"
>   external set : 'a array -> int -> 'a -> unit =3D "%array_safe_set"
>   external make : int -> 'a -> 'a array =3D "caml_make_vect"
>   external create : int -> 'a -> 'a array =3D "caml_make_vect"
>   val init : int -> (int -> 'a) -> 'a array
>   val make_matrix : int -> int -> 'a -> 'a array array
>   val create_matrix : int -> int -> 'a -> 'a array array
>   val append : 'a array -> 'a array -> 'a array
>   val concat : 'a array list -> 'a array
>   val sub : 'a array -> int -> int -> 'a array
>   val copy : 'a array -> 'a array
>   val fill : 'a array -> int -> int -> 'a -> unit
>   val blit : 'a array -> int -> 'a array -> int -> int -> unit
>   val to_list : 'a array -> 'a list
>   val of_list : 'a list -> 'a array
>   val iter : ('a -> unit) -> 'a array -> unit
>   val map : ('a -> 'b) -> 'a array -> 'b array
>   val iteri : (int -> 'a -> unit) -> 'a array -> unit
>   val mapi : (int -> 'a -> 'b) -> 'a array -> 'b array
>   val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b array -> 'a
>   val fold_right : ('b -> 'a -> 'a) -> 'b array -> 'a -> 'a
>   val sort : ('a -> 'a -> int) -> 'a array -> unit
>   val stable_sort : ('a -> 'a -> int) -> 'a array -> unit
>   val fast_sort : ('a -> 'a -> int) -> 'a array -> unit
>   external unsafe_get : 'a array -> int -> 'a =3D "%array_unsafe_get"
>   external unsafe_set : 'a array -> int -> 'a -> unit =3D
> "%array_unsafe_set"
>
> end
>
>
>
>
>
> --
> Richard Jones, CTO Merjis Ltd.
> Merjis - web marketing and technology - http://merjis.com
> Team Notepad - intranets and extranets for business -
> http://team-notepad.com
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by: Splunk Inc. Do you grep through log
> files
> for problems?  Stop!  Download the new AJAX search engine that makes
> searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
> http://ads.osdn.com/?ad_id=3D7637&alloc_id=3D16865&op=3Dclick
> _______________________________________________
> ocaml-lib-devel mailing list
> oca...@li...
> https://lists.sourceforge.net/lists/listinfo/ocaml-lib-devel
>

Re: [Ocaml-lib-devel] ExtArray?

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

OK, I have implemented the following interface.  There are also tests
for all the new functions in the extlib-test directory.

Rich.

(*
 * ExtArray - additional and modified functions for arrays.
 * Copyright (C) 2005 Richard W.M. Jones (rich @ annexia.org)
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version,
 * with the special exception on linking described in file LICENSE.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *)

(** Additional and modified functions for arrays.

	The OCaml standard library provides a module of array functions.
	This ExtArray module can be used to override the Array module or
	as a standalone module. It provides some additional functions.
*)

module Array :
sig

  (** {6 New functions} *)
  val rev : 'a array -> 'a array
    (** Array reversal. *)

  val rev_in_place : 'a array -> unit
    (** In-place array reversal.  The array argument is updated. *)

  val for_all : ('a -> bool) -> 'a array -> bool
    (** [for_all p [a1; ...; an]] checks if all elements of the array
	satisfy the predicate [p].  That is, it returns
	[ (p a1) && (p a2) && ... && (p an)].
    *)

  val exists : ('a -> bool) -> 'a array -> bool
    (** [exists p [a1; ...; an]] checks if at least one element of
	the array satisfies the predicate [p].  That is, it returns
	[ (p a1) || (p a2) || ... || (p an)].
    *)

  val mem : 'a -> 'a array -> bool
    (** [mem m a] is true if and only if [m] is equal to an element of [a]. *)

  val memq : 'a -> 'a array -> bool
    (** Same as {!Array.mem} but uses physical equality instead of
	structural equality to compare array elements.
    *)

  val find : ('a -> bool) -> 'a array -> 'a
    (** [find p a] returns 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].
    *)

  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].
    *)

  val filter : ('a -> bool) -> 'a array -> 'a array
    (** [filter p a] returns all the elements of the array [a]
	that satisfy the predicate [p].  The order of the elements
	in the input array is preserved.  *)

  val find_all : ('a -> bool) -> 'a array -> 'a array
    (** [find_all] is another name for {!Array.filter}. *)

(* -- NOT IMPLEMENTED
  val partition : ('a -> bool) -> 'a array -> 'a array * 'a array
    (** [partition p a] returns a pair of arrays [(a1, a2)], where
	[a1] is the array of all the elements of [a] that
	satisfy the predicate [p], and [a2] is the array of all the
	elements of [a] that do not satisfy [p].
	The order of the elements in the input array is preserved. *)
*)

  (** {6 Enumerations} *)

  val enum : 'a array -> 'a Enum.t
    (** Returns an enumeration of the elements of an array. *)

  val of_enum : 'a Enum.t -> 'a array
    (** Build an array from an enumeration. *)

  (** {6 Old functions} *)

  (** These functions are already part of the Ocaml standard library
      and have not been modified. Please refer to the Ocaml Manual for
      documentation. *)

  external length : 'a array -> int = "%array_length"
  external get : 'a array -> int -> 'a = "%array_safe_get"
  external set : 'a array -> int -> 'a -> unit = "%array_safe_set"
  external make : int -> 'a -> 'a array = "caml_make_vect"
  external create : int -> 'a -> 'a array = "caml_make_vect"
  val init : int -> (int -> 'a) -> 'a array
  val make_matrix : int -> int -> 'a -> 'a array array
  val create_matrix : int -> int -> 'a -> 'a array array
  val append : 'a array -> 'a array -> 'a array
  val concat : 'a array list -> 'a array
  val sub : 'a array -> int -> int -> 'a array
  val copy : 'a array -> 'a array
  val fill : 'a array -> int -> int -> 'a -> unit
  val blit : 'a array -> int -> 'a array -> int -> int -> unit
  val to_list : 'a array -> 'a list
  val of_list : 'a list -> 'a array
  val iter : ('a -> unit) -> 'a array -> unit
  val map : ('a -> 'b) -> 'a array -> 'b array
  val iteri : (int -> 'a -> unit) -> 'a array -> unit
  val mapi : (int -> 'a -> 'b) -> 'a array -> 'b array
  val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b array -> 'a
  val fold_right : ('b -> 'a -> 'a) -> 'b array -> 'a -> 'a
  val sort : ('a -> 'a -> int) -> 'a array -> unit
  val stable_sort : ('a -> 'a -> int) -> 'a array -> unit
  val fast_sort : ('a -> 'a -> int) -> 'a array -> unit
  external unsafe_get : 'a array -> int -> 'a = "%array_unsafe_get"
  external unsafe_set : 'a array -> int -> 'a -> unit = "%array_unsafe_set"

end


-- 
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] ExtArray?

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

On Fri, Nov 25, 2005 at 05:04:24AM +1100, skaller wrote:
> On Thu, 2005-11-24 at 16:30 +0000, Richard W. M. Jones wrote:
> 
> > I think the principle of least surprise is going to be that
> > Array.filter should return an array - this is surely what users would
> > expect. 
> 
> Curious .. but why not an Enum?

That'd be Array.enum surely :-)

I didn't implement Array.enum because I wasn't sure how to -- I've
never used Enums.

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] ExtArray?

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

Richard Jones wrote:
> In CVS is an untested implementation with the following interface.

Could you perhaps add

  val enum : 'a array -> 'a Enum.t
  val of_enum : 'a Enum.t -> 'a array

as well?

Re: [Ocaml-lib-devel] ExtArray?

[Amit D. <ami...@gm...>]

On 11/24/05, Richard Jones <ri...@an...> wrote:

> > (1) What is the point of having two rev functions?  Arrays are indexed,
> you
> > can just access n-i instead of i.
>
> I'm not sure if the objection is to having 'Array.rev*' altogether or
> having two different versions of this function.  Well, the point of
> having 'Array.rev' is simply because there is a 'List.rev'.  'Array.-
> rev_in_place' is an extension to the standard set of common functions
> which only applies to the special case of arrays because arrays are
> mutable.


Both ;)  But, I see some other languages seem to have library functions for
in place reversal.  Still, though, I'm unconvinced that there should be a
copying reversal function.  In the C++ STL, they defined interface function=
s
to be general across container types.  List doesn't have this property: it
was designed to be an interface for List alone.  And List is an immutable
container type.  So, I think we should be careful about duping the behaviou=
r
of List here.

> (2) find_all should return a list.  e.g. find_all in ExtHashtbl returns a
> > list.
>
> OK, but conversely List.find_all is defined as identical to
> List.filter.  Hashtbl.find_all is quite a different function.  It
> returns all values associated with a single key, and only makes sense
> because of a peculiarity of Hashtbl, namely that one can associate
> multiple values with a key.


True.  But I already stated another, probably more important reason above:
filter suggests it returns the same container type as it was given.
find_all doesn't suggest this at all.  They are the same in list only
because (barring enums) the only sensible return type for find_all is a
list.

Maybe we should change the documentation of ExtList.find_all to make this
clear.  i.e. say, find_all returns a list containing matching elements, in
the case lists, it is equivalent to filter.

-Amit

Re: [Ocaml-lib-devel] ExtArray?

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

On Thu, 2005-11-24 at 16:23 +0000, Amit Dubey wrote:


> I agree: filter implies you're given a container,  then you "filter"
> away some elements, still left with the same type of container.

Impossible for Array[n]. Ocaml Array is bogus type, not encoding
the length (since it is fixed length). See below ..

> Find_all suggests you're just looking for all matching elements.  It
> doesn't suggest any particular data structure.  So, a list is as good
> as anything.

A problem -- finding the length of the list, so as to create
an array next, is very wasteful. Better to return a list AND
the length of the list, then list + length -> Array is fast,
and you can make versions of filter and find_all that create
arrays.

So 3 primitives and 2 derived functions.

>  One worry with a two-pass approach, though, is it might be
> incompatible with find/inclusion functions that contain state (i.e.
> the state might get confused on the 2nd call).

The whole library has this problem ;(


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

Re: [Ocaml-lib-devel] ExtArray?

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

On Thu, 2005-11-24 at 16:30 +0000, Richard W. M. Jones wrote:

> I think the principle of least surprise is going to be that
> Array.filter should return an array - this is surely what users would
> expect. 

Curious .. but why not an Enum?

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

Re: [Ocaml-lib-devel] ExtArray?

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

On Thu, Nov 24, 2005 at 05:29:46PM +0000, Amit Dubey wrote:
> I can't see the CVS version, but I have a couple questions:
> 
> (1) What is the point of having two rev functions?  Arrays are indexed, you
> can just access n-i instead of i.

I'm not sure if the objection is to having 'Array.rev*' altogether or
having two different versions of this function.  Well, the point of
having 'Array.rev' is simply because there is a 'List.rev'.  'Array.-
rev_in_place' is an extension to the standard set of common functions
which only applies to the special case of arrays because arrays are
mutable.

> (2) find_all should return a list.  e.g. find_all in ExtHashtbl returns a
> list.

OK, but conversely List.find_all is defined as identical to
List.filter.  Hashtbl.find_all is quite a different function.  It
returns all values associated with a single key, and only makes sense
because of a peculiarity of Hashtbl, namely that one can associate
multiple values with a key.

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] ExtArray?

[Amit D. <ami...@gm...>]

On 11/24/05, Amit Dubey <ami...@gm...> wrote:
>
> Hi,
>
> I can't see the CVS version, but I have a couple questions:
>
> (1) What is the point of having two rev functions?  Arrays are indexed,
> you can just access n-i instead of i.
>
> (2) find_all should return a list.  e.g. find_all in ExtHashtbl returns a
> list.


Ok, that last one is a comment, not a question :)

-Amit

Re: [Ocaml-lib-devel] ExtArray?

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

In CVS is an untested implementation with the following interface.
I'm currently writing some tests for extlib-test.

module Array :
sig

  (** {6 New functions} *)
  val rev : 'a array -> 'a array
    (** Array reversal. *)

  val rev_in_place : 'a array -> unit
    (** In-place array reversal.  The array argument is updated. *)

  val for_all : ('a -> bool) -> 'a array -> bool
    (** [for_all p [a1; ...; an]] checks if all elements of the array
	satisfy the predicate [p].  That is, it returns
	[ (p a1) && (p a2) && ... && (p an)].
    *)

  val exists : ('a -> bool) -> 'a array -> bool
    (** [exists p [a1; ...; an]] checks if at least one element of
	the array satisfies the predicate [p].  That is, it returns
	[ (p a1) || (p a2) || ... || (p an)].
    *)

  val mem : 'a -> 'a array -> bool
    (** [mem m a] is true if and only if [m] is equal to an element of [a]. *)

  val memq : 'a -> 'a array -> bool
    (** Same as {!Array.mem} but uses physical equality instead of
	structural equality to compare array elements.
    *)

  val find : ('a -> bool) -> 'a array -> 'a
    (** [find p a] returns 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].
    *)

  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].
    *)

  val filter : ('a -> bool) -> 'a array -> 'a array
    (** [filter p a] returns all the elements of the array [a]
	that satisfy the predicate [p].  The order of the elements
	in the input array is preserved.  *)

  val find_all : ('a -> bool) -> 'a array -> 'a array
    (** [find_all] is another name for {!Array.filter}. *)

(* -- NOT IMPLEMENTED
  val partition : ('a -> bool) -> 'a array -> 'a array * 'a array
    (** [partition p a] returns a pair of arrays [(a1, a2)], where
	[a1] is the array of all the elements of [a] that
	satisfy the predicate [p], and [a2] is the array of all the
	elements of [a] that do not satisfy [p].
	The order of the elements in the input array is preserved. *)
*)

  (** {6 Old functions} *)

  (** These functions are already part of the Ocaml standard library
      and have not been modified. Please refer to the Ocaml Manual for
      documentation. *)

  external length : 'a array -> int = "%array_length"
  external get : 'a array -> int -> 'a = "%array_safe_get"
  external set : 'a array -> int -> 'a -> unit = "%array_safe_set"
  external make : int -> 'a -> 'a array = "caml_make_vect"
  external create : int -> 'a -> 'a array = "caml_make_vect"
  val init : int -> (int -> 'a) -> 'a array
  val make_matrix : int -> int -> 'a -> 'a array array
  val create_matrix : int -> int -> 'a -> 'a array array
  val append : 'a array -> 'a array -> 'a array
  val concat : 'a array list -> 'a array
  val sub : 'a array -> int -> int -> 'a array
  val copy : 'a array -> 'a array
  val fill : 'a array -> int -> int -> 'a -> unit
  val blit : 'a array -> int -> 'a array -> int -> int -> unit
  val to_list : 'a array -> 'a list
  val of_list : 'a list -> 'a array
  val iter : ('a -> unit) -> 'a array -> unit
  val map : ('a -> 'b) -> 'a array -> 'b array
  val iteri : (int -> 'a -> unit) -> 'a array -> unit
  val mapi : (int -> 'a -> 'b) -> 'a array -> 'b array
  val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b array -> 'a
  val fold_right : ('b -> 'a -> 'a) -> 'b array -> 'a -> 'a
  val sort : ('a -> 'a -> int) -> 'a array -> unit
  val stable_sort : ('a -> 'a -> int) -> 'a array -> unit
  val fast_sort : ('a -> 'a -> int) -> 'a array -> unit
  external unsafe_get : 'a array -> int -> 'a = "%array_unsafe_get"
  external unsafe_set : 'a array -> int -> 'a -> unit = "%array_unsafe_set"

end





-- 
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] ExtArray?

[William N. <wne...@cs...>]

On Nov 24, 2005, at 9:30 AM, Richard W. M. Jones wrote:

> The problem will be in the implementation which may require
> two passes -- it could be solved better if there was a truncation
> primitive for arrays.

Well, if you don't mind getting dirty, you can use Obj.truncate.

William D. Neumann

"I eat T-bone steaks, I lift barbell plates, I'm sweeter than a
German chocolate cake. I'm the reflection of perfection, the number
one selection. I'm the man of the hour, the man with the power, too
sweet to be sour. The ladies' pet, the men's regret, where what you
see is what you get, and what you don't see, is better yet."

          --Superstar Billy Graham

Re: [Ocaml-lib-devel] ExtArray?

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

On Thu, Nov 24, 2005 at 04:23:40PM +0000, Amit Dubey wrote:
> There are a number of other implementations, it might make sense to write a
> benchmark to decide which is faster.  One worry with a two-pass approach,
> though, is it might be incompatible with find/inclusion functions that
> contain state (i.e. the state might get confused on the 2nd call).

Yes, two passes isn't a good idea.

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