Fwd: Re: [Caml-list] The boon of static type checking

Fwd: Re: [Caml-list] The boon of static type checking

[Jon Harrop]

On Sunday 06 February 2005 22:26, Radu Grigore wrote:
> By "fork lineages" you mean keeping "old" versions of the map around?

Exactly, "persistence".

> > I would like to think that your stack will be big enough to fit 40
> > recursive calls if you expect your computer to handle trillion-element
> > maps!
>
> In the worst case (most unbalanced) 40 corresponds to a few million
> keys, not trillions. If I haven't made a mistake the minimum number of
> keys in a (OCaml) Map with height h is given by the recurrence:
> T(h)=1+T(h-1)+T(h-3).

I think you are right. Regardless, your computer is unlikely to struggle with 
80 recursive function calls.

> > > Yet another problem is the missing cardinal function.
> >
> > An arbitrary number of functions are "missing". You can't expect INRIA to
> > implement all infinity of them for you! :-)
>
> Considering the fact that the code in set.ml and map.ml looks like it
> is copy&pasted I guess asking for some consistency in the interface is
> not unreasonable. In any case copy&pasting the cardinal function
> wouldn't provide better performance (I think).

Yes, Set's cardinal looks O(n) to me. So you're asking for an equally 
inefficient cardinal function in Map? ;-)

Personally, I'd like to see a core balanced binary tree implementation with
various different set and map (and other) data structures built from it.

> > The STL will probably take <<1ms because the STL's size() is probably
> > O(1) whereas Map's fold is O(n). In contrast, forking lineages is
> > probably O(n) with the STL (requiring a copy) and O(1) with ocaml's Map.
>
> I haven't actually tested with STL but the implementation of size() is
> indeed a simple return. Do you have an example where forking lineages
> is useful?

I often exploit persistence when writing interpreters in a functional style,
to handle bindings in an inner scope. Note that more intelligent people use
an imperative style and the seemingly-quirky Hashtbl for this...

> As I said, I don't doubt there are situations where it is
> useful; just that right now I'm having trouble coming up with a
> realistic example.

I can't think of any other places I've used persistence...

> I am exploring possibilities right now. My only "complaint" is that
> switching from Hashtbl to Map for a dictionary of about 200000 keys
> decreases the performance a LOT! I would have expected a factor of
> 20-30 but it seems to be a lot more: probably due to memory management
> (as Gerd Stolpmann notices) due to the functional nature of Map.

Now that I've had a little more time to think about it, I can think of three
possible causes of this poor performance. The most likely is the O(ln n)
(unnecessary) string comparisons it will be doing (particularly if your
strings are similar "lexicographically"), compared to a single hash. Next is
the time spent in allocate and GC, as someone else said. Third is cache
incoherence, as I said before.

You could profile your code to work out which but you might as well skip this
and just use a more appropriate data structure. Or use Hashtbl and sort, as
Gerd says. If you really want to stick with Map then you could also store a
hash along with each string, so the comparison acts on the hash before it
acts on the string. This should greatly speed up the comparisons (oh, and
write your own comparison function, using String.compare and not
Pervasives.compare) and, I think, the whole program.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.

Re: Fwd: Re: [Caml-list] The boon of static type checking

[skaller]

On Mon, 2005-02-07 at 13:24, Jon Harrop wrote:

> I often exploit persistence when writing interpreters in a functional style,
> to handle bindings in an inner scope. Note that more intelligent people use
> an imperative style and the seemingly-quirky Hashtbl for this...

.. actually I use a list of Hashtbls .. 

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

String to list to string

[Juancarlo Añez]

Why aren't there functions in the standard library to convert strings to
lists of characters and back?

Haskell treats strings as lists of chars by default.

Juanco

Re: [Caml-list] String to list to string

[William D.Neumann]

On Feb 9, 2005, at 7:10 PM, Juancarlo Añez wrote:

> Why aren't there functions in the standard library to convert strings 
> to
> lists of characters and back?

Because a) they're not all that useful and b) they're trivial to write 
for yourself:

let explode s =
   let rec exh acc = function
   | -1 -> acc
   | i -> exh (s.[i]::acc) (pred i)
   in exh [] (pred (String.length s))

let implode l =
   let s = String.create (List.length l) in
   let rec imh i = function
   | h::t -> s.[i] <- h; imh (succ i) t
   | [] -> s
   in imh 0 l

William D. Neumann

"You've got Rita Marlowe in the palm of your hand."
"Palm of my hand?  You haven't seen Rita Marlowe..."

		-- Will Success Spoil Rock Hunter?

Re: [Caml-list] String to list to string

[Erik de Castro Lopo]

On Wed, 9 Feb 2005 19:27:37 -0700
"William D.Neumann" <wneumann@cs.unm.edu> wrote:

> Because a) they're not all that useful and b) they're trivial to write 
> for yourself:

Agree on both counts.

> let explode s =
>    let rec exh acc = function
>    | -1 -> acc
>    | i -> exh (s.[i]::acc) (pred i)
>    in exh [] (pred (String.length s))

Here's one thats a little more obvious (remove the function, use String.get)
and runs about 20% faster (at least on my iBook running Linux):

let string_to_charlist str =
	let rec stc lst n =
		if n < 0 then lst
		else stc ((String.get str n) :: lst) (n - 1)
	in
	stc [] ((String.length str) - 1)
	;;

To be honest, this was my second attempt. My first attempt was slower
than yours and blew the stack on million character strings (obviously
not tail rescursive). This one (and yours) is quite happy with strings 
10 times that size.

Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo  nospam@mega-nerd.com (Yes it's valid)
+-----------------------------------------------------------+
C++ is a siren song. It *looks* like a HLL in which you ought to be
able to write an application, but it really isn't."
-- Alain Picard (comp.lang.lisp)

Re: [Caml-list] String to list to string

[Radu Grigore]

On Thu, 10 Feb 2005 14:24:01 +1100, Erik de Castro Lopo
<ocaml-erikd@mega-nerd.com> wrote:
> On Wed, 9 Feb 2005 19:27:37 -0700
> "William D.Neumann" <wneumann@cs.unm.edu> wrote:
> 
> > Because a) they're not all that useful and b) they're trivial to write
> > for yourself:
> 
> Agree on both counts.
> 
> Here's one thats a little more obvious [...]
> let string_to_charlist str = [...]

Yet another one:
http://caml.inria.fr/FAQ/FAQ_EXPERT-eng.html#strings

-- 
regards,
 radu
http://rgrig.idilis.ro/

Re: [Caml-list] String to list to string

[Erik de Castro Lopo]

On Thu, 10 Feb 2005 08:31:50 +0200
Radu Grigore <radugrigore@gmail.com> wrote:

> Yet another one:
> http://caml.inria.fr/FAQ/FAQ_EXPERT-eng.html#strings

Oh cool! My implementation was alomost exactly the same
as the one in the FAQ. I must be getting the hang of this
thing :-).

Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo  nospam@mega-nerd.com (Yes it's valid)
+-----------------------------------------------------------+
"I could never learn to use C++, because of the completely overwhelming
desire to redesign the language every time I tried to use it, but this
is the normal, healthy reaction to C++." -- Erik Naggum

Re: [Caml-list] String to list to string

[Jon Harrop]

On Thursday 10 February 2005 02:10, Juancarlo Añez wrote:
> Why aren't there functions in the standard library to convert strings to
> lists of characters and back?

Outrageously, the core library fails to provide an arbitrary number of 
arbitrary functions. This exact question came up recently. The answer was 
essentially: Why string -> char list and not string -> char array? Why string 
-> char list and not string -> string list? And so on.

If you want succinct implementations then I'd go for:

let char_list_of_string s =
  let l = ref [] in
  String.iter (fun c -> l := c :: !l) s;
  List.rev !l

let string_of_char_list l =
  String.concat "" (List.map (String.make 1) l)

> Haskell treats strings as lists of chars by default.

I see an optimisation...

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.

Re: [Caml-list] String to list to string

[Aaron Bohannon]

Sorry to revive an old thread, but I have to add my $.02 here.

Jon Harrop wrote:
> Outrageously, the core library fails to provide an arbitrary number of 
> arbitrary functions. This exact question came up recently. The answer was 
> essentially: Why string -> char list and not string -> char array? Why string 
> -> char list and not string -> string list? And so on.

Instead of adding one of these functions, I would much rather see a 
"fold" function on strings in the String module.  The Array module has 
both "iter" and "fold" functions.  Why, then, would the String module 
provide an "iter" but no "fold"--in a functional language??  The 
addition of a fold function would very often eliminate the need to 
convert a string to a char list or to introduce imperative-style 
programming into an otherwise purely functional section of code (not to 
mention that writing "char_list_of_string" would become trivial if it 
ever were necessary to do so).

I acknowledge the fact that I can write my own fold function, but I just 
wanted to point out that this seems to be the most logical addition to 
the String module.

Aaron

-- 
Aaron Bohannon
http://www.cis.upenn.edu/~bohannon/

Re: [Caml-list] String to list to string

[Richard Jones]

On Mon, Feb 14, 2005 at 08:16:51PM -0500, Aaron Bohannon wrote:
> Instead of adding one of these functions, I would much rather see a 
> "fold" function on strings in the String module.  The Array module has 
> both "iter" and "fold" functions.  Why, then, would the String module 
> provide an "iter" but no "fold"--in a functional language??  The 
> addition of a fold function would very often eliminate the need to 
> convert a string to a char list or to introduce imperative-style 
> programming into an otherwise purely functional section of code (not to 
> mention that writing "char_list_of_string" would become trivial if it 
> ever were necessary to do so).
> 
> I acknowledge the fact that I can write my own fold function, but I just 
> wanted to point out that this seems to be the most logical addition to 
> the String module.

If you can suggest suitable fold_left and fold_right functions, then
they can be added to ExtLib.

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: [Caml-list] String to list to string

[Eric C. Cooper]

On Tue, Feb 15, 2005 at 10:33:16AM +0000, Richard Jones wrote:
> If you can suggest suitable fold_left and fold_right functions, then
> they can be added to ExtLib.

Here's what I use:

val string_fold_left : ('a -> char -> 'a) -> 'a -> string -> 'a
val string_fold_right : (char -> 'a -> 'a) -> 'a -> string -> 'a

let string_fold_left f init str =
  let n = String.length str in
  let rec loop i result =
    if i = n then result
    else loop (i + 1) (f result str.[i])
  in
  loop 0 init

let string_fold_right f init str =
  let n = String.length str in
  let rec loop i result =
    if i = 0 then result
    else
      let i' = i - 1 in
      loop i' (f str.[i'] result)
  in
  loop n init

-- 
Eric C. Cooper          e c c @ c m u . e d u

Re: [Caml-list] String to list to string

[Richard Jones]

On Wed, Feb 09, 2005 at 10:10:03PM -0400, Juancarlo A?ez wrote:
> 
> Why aren't there functions in the standard library to convert strings to
> lists of characters and back?

As others have said, these functions are not in the standard library.
However, useful functions like these[1] are available in Extlib, which
you can find here:

http://sourceforge.net/projects/ocaml-lib/

and is also available as a binary package for various platforms such
as Debian.

It contains important functions such as String.map,
String.replace_chars, String.slice, String.starts_with,
String.ends_with, and many more.

Rich.

[1] Although embarrassingly, it appears, not these exact functions,
which is why I've CC'd to ocaml-lib-devel list.  To ocaml-lib-devel:
we should provide implementations of
http://caml.inria.fr/FAQ/FAQ_EXPERT-eng.html#strings

-- 
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: [Caml-list] String to list to string

[Juancarlo Añez]

Rich,

 | As others have said, these functions are not in the standard library.
 | However, useful functions like these[1] are available in 
 | Extlib, which you can find here:
 | 
 | http://sourceforge.net/projects/ocaml-lib/

Thanks. 

I don't understand why such functions are not part of the standard library.
Even if they are very easy to write, they are the kind of functions most
anyone _will_ have to write and not having them in the library is
inefficient.

Talking about efficiency, I've seen the solutions that have been posted, and
MHO is that having to recur to procedural constructs for such oviously
functional tasks as "implode" and "explode" seems odd.

Juanco

Re: [Caml-list] String to list to string

[Richard Jones]

On Thu, Feb 10, 2005 at 03:19:13PM -0400, Juancarlo A?ez wrote:
> I don't understand why such functions are not part of the standard library.

That's exactly the reason why extlib exists - to provide useful
functions to the community which are not part of the standard library.

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: [Caml-list] String to list to string

[brogoff]

On Wed, 9 Feb 2005, [iso-8859-1] Juancarlo Añez wrote:
> Why aren't there functions in the standard library to convert strings to
> lists of characters and back?

Because it's a bad idea. This has been discussed numerous times in this
mailing list, and if the mailing list search engine actually worked (like it
used to a few years ago) I'd tell you to search the archives.

> Haskell treats strings as lists of chars by default.

Just goes to show you that even really smart people can do some amazingly dumb
things.

Take a look at the SML Basis Library substrings for a smarter functional
approach to this issue.

-- Brian