Menu
▾
▴
ocaml-lib-devel
|
From: Richard J. <ri...@an...> - 2005-11-24 13:11:54
|
Does anyone have any opinions on whether we should have ExtArray, analogous to ExtList and ExtString? Particular functions which are missing from standard Array but which would be useful are: Array.for_all Array.exists Array.mem Array.memq Array.find Array.filter Array.find_all Array.partition Array.assoc etc. Array.sort Now you can argue that I'm using the wrong data structure and I should be using a list, but I have my reasons for using an array and having to convert it to a list just to do a quick "for_all" seems a bit silly. 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 |
|
From: Peter J. <pe...@jo...> - 2005-11-24 13:31:10
|
Richard Jones wrote: > Does anyone have any opinions on whether we should have ExtArray, > analogous to ExtList and ExtString? As an ExtLib user I would find such a module very convenient. While I generally use DynArray when I have the liberty to choose my own data structure, existing libraries - including parts of the OCaml standard library - force the use of the built-in arrays in many cases. I'm sure I can't be the only person who's got quick-and-dirty implementations of Array.mem, Array.filter, Array.find, and Array.enum embedded in various projects. |
|
From: Amit D. <ami...@gm...> - 2005-11-24 14:16:31
|
Hi, Array.for_all Array.exists Array.mem Array.memq Array.assoc etc. These seem like nice additions. Array.sort This already exists. Array.find Will this return the element or an index? Array.filter Array.find_all Array.partition Would these return lists or arrays? -Amit On 11/24/05, Richard Jones <ri...@an...> wrote: > > > Does anyone have any opinions on whether we should have ExtArray, > analogous to ExtList and ExtString? > > Particular functions which are missing from standard Array but which > would be useful are: > > Now you can argue that I'm using the wrong data structure and I should > be using a list, but I have my reasons for using an array and having > to convert it to a list just to do a quick "for_all" seems a bit > silly. > > 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 > |
|
From: Richard J. <ri...@an...> - 2005-11-24 15:23:18
|
Well, it seems like people are generally for this proposal, so I have added a skeletal ExtArray module to CVS. At present it is simply a straightforward include of Array. > Array.for_all > Array.exists > Array.mem > Array.memq > Array.assoc etc. > > These seem like nice additions. I'll add these and make them look like the List versions. > Array.sort > > This already exists. > > Array.find > > Will this return the element or an index? I'm not sure which is better? I think probably having Array.find be exactly like List.find, ie. returning an element, and having an additional Array.find_index to return the index would be the best idea. What do people think? > 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? 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 |
|
From: Amit D. <ami...@gm...> - 2005-11-24 15:56:24
|
On 11/24/05, Richard Jones <ri...@an...> wrote: > > Array.find > > > > Will this return the element or an index? > > I'm not sure which is better? I think probably having Array.find be > exactly like List.find, ie. returning an element, and having an > additional Array.find_index to return the index would be the best > idea. What do people think? I agree that returning the element is similar to what List does, but arrays are not lists ;) I would argue that something like find_index is all that'= s necessary, and you can do a lookup if you need the element. > 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 retur= n a list, and filter should return an array. And possibly, filter should be defined in terms of find_all. -Amit |
|
From: Richard W. M. J. <ri...@me...> - 2005-11-24 16:09:49
|
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. 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 |
|
From: William N. <wne...@cs...> - 2005-11-24 16:27:43
|
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
|
|
From: skaller <sk...@us...> - 2005-11-24 18:04:43
|
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 |
|
From: Richard J. <ri...@an...> - 2005-11-24 18:38:47
|
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 |
|
From: Peter J. <pe...@jo...> - 2005-11-24 16:15:43
|
Richard Jones wrote: >Amit Dubey wrote: >> Array.find >> >> Will this return the element or an index? > > I'm not sure which is better? I think probably having Array.find be > exactly like List.find, ie. returning an element, and having an > additional Array.find_index to return the index would be the best > idea. What do people think? The principle of least surprise suggests that identically-named functions should have identical behaviours, so I agree with this. >> 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? Again, since List.filter returns a list and Enum.filter returns an enum, it seems logical that Array.filter should return an array. The other behaviour can be derived trivially, and hopefully not too inefficiently, by doing the filtering on an intermediate enum: let filter_to_list f a = List.of_enum (Enum.filter f (Array.enum a)) Incidentally, I notice that DynArray lacks most of these functions too, including sort. Would it be worth adding them there, to give all the common linear containers equivalent interfaces? |
|
From: Richard J. <ri...@an...> - 2005-11-24 16:25:15
|
On Thu, Nov 24, 2005 at 04:08:51PM +0000, Peter Jolly wrote: > Incidentally, I notice that DynArray lacks most of these functions too, > including sort. Would it be worth adding them there, to give all the > common linear containers equivalent interfaces? Having a common set of interface functions is definitely a goal to go for. It's a bit of a shame that Extlib has fiddled with some of the standard library interfaces, particularly changing List.sort and adding its own non-standard exceptions. 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 |
|
From: Amit D. <ami...@gm...> - 2005-11-24 15:57:30
|
William writes:
---------- Forwarded message ----------
From: William Neumann <wne...@cs...>
Date: Nov 24, 2005 2:58 PM
Subject: Re: [Ocaml-lib-devel] ExtArray?
To: Amit Dubey <ami...@gm...>
On Nov 24, 2005, at 7:16 AM, Amit Dubey wrote:
> Array.find
>
> Will this return the element or an index?
If I were writing it (and I'm sure I have at some point) I'd have
Array.find
return the element, but I'd also have an Array.findi that returned
the element and it's index (and just define Array.find as snd
(Array.findi ...) ).
> Array.filter
> Array.find_all
> Array.partition
>
> Would these return lists or arrays?
I'd have them return arrays, myself. Less efficient, perhaps, but
certainly more consistent. And if I wanted lists back, I'd just use
List.XXX (Array.to_list arr).
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
|
|
From: William N. <wne...@cs...> - 2005-11-24 16:02:26
|
On Nov 24, 2005, at 8:57 AM, Amit Dubey wrote:
> William writes:
Thanks. I am apparently still confused by the mysteries of "Reply to
all".
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
|
|
From: Janne H. <jjh...@gm...> - 2005-11-24 14:48:39
|
Hi, > Does anyone have any opinions on whether we should have ExtArray, > analogous to ExtList and ExtString? > > Particular functions which are missing from standard Array but which > would be useful are: > ... I would personally find these very useful. Best regards, Janne |
|
From: Amit D. <ami...@gm...> - 2005-11-24 16:23:48
|
On 11/24/05, Richard W. M. Jones <ri...@me...> wrote: > > 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 :-) > Sorry! 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. I agree: filter implies you're given a container, then you "filter" away some elements, still left with the same type of container. 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. 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. As I suggested above, one way to implement filter is just: let filter x y =3D of_list (find_all x y) 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). -Amit |
|
From: Richard J. <ri...@an...> - 2005-11-24 16:26:35
|
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 |
|
From: skaller <sk...@us...> - 2005-11-24 18:12:13
|
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 |
|
From: Richard J. <ri...@an...> - 2005-11-24 17:00:39
|
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
|
|
From: Peter J. <pe...@jo...> - 2005-11-24 18:25:43
|
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? |
|
From: Richard J. <ri...@an...> - 2005-11-24 19:00:49
|
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 |
|
From: Amit D. <ami...@gm...> - 2005-11-24 19:08:35
|
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
>
|
|
From: Amit D. <ami...@gm...> - 2005-11-24 17:37:17
|
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 |
|
From: Richard J. <ri...@an...> - 2005-11-24 17:39:22
|
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 |
|
From: Amit D. <ami...@gm...> - 2005-11-24 18:15:29
|
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 |
|
From: Brian H. <bh...@sp...> - 2005-11-25 03:16:54
|
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
|
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X