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

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

[Harrison, John R]

| > 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.

That's far too categorical; opinions differ on this subject. I'd be
quite
happy with strings as lists of characters, and I consider OCaml's
mutable
strings a far worse design error.

And yes, I use "implode" and "explode" all the time, because lists of
characters are often simple and convenient to deal with in a functional
style, and string manipulations are almost never performance-critical
in the kind of code I write.

John.

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

[Jon Harrop]

On Thursday 10 February 2005 18:35, Harrison, John R wrote:
> ...I consider OCaml's mutable strings a far worse design error.

That's interesting. Why?

I appreciate ocaml allowing me to write efficient code for all sorts of things 
when I need to. I would be very miffed if the language enforced an 
inefficient style upon me. If ocaml used char lists then you have vastly 
different complexities for a variety of important operations. Which of these 
operations is most important is subjective, of course. If ocaml used an 
immutable char array then you would need quite a bit more in the compilers to 
get decent performance. If ocaml used a balanced binary tree then the pattern 
matcher would need to know about this kind of data structure and the 
asymptotic complexity of pattern matching would go from O(1) to O(ln n) for 
some leaf patterns.

Having said that, I have been bitten by some oddities (e.g. statically 
allocated string constants) but this seems like a small price to pay for the 
expressiveness of an impure functional language, IMHO.

I suppose you could have "abcd" patterns over the type "char list" instead of 
"string" whilst keeping the string type. Do many programs/functions use both 
string patterns and the mutability of the string type?

Of course, the usefulness of the current string type would be much more 
clear-cut in the presence of Richard Jones' style "abcd".. | .."dcba" 
prefix/suffix patterns as the latter can't be done on lists in O(m) (where 
"n" is the number of chars in the matched string and "m" is the number of 
chars in the string appearing in the pattern).

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

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

[skaller]

On Fri, 2005-02-11 at 06:28, Jon Harrop wrote:
> On Thursday 10 February 2005 18:35, Harrison, John R wrote:
> > ...I consider OCaml's mutable strings a far worse design error.
> 
> That's interesting. Why?

Because it makes the worst possible compromise.

Throws out transparency/persistence and fails to
allow any length changing operations, which are
common for strings -- overwriting strings is rarely 
needed. The only use I can think of is as a buffer
(and we have Buffer module for that, and it
also allows variable length)

-- 
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

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

[John Prevost]

On Thu, 10 Feb 2005 17:32:18 -0800 (PST), skaller
<skaller@users.sourceforge.net> wrote:
> Throws out transparency/persistence and fails to
> allow any length changing operations, which are
> common for strings -- overwriting strings is rarely
> needed. The only use I can think of is as a buffer
> (and we have Buffer module for that, and it
> also allows variable length)

As much as I hate to agree with skaller, I do agree here.  :)  Having
the only kind of strings be mutable strings (like this, with each
point in the string being mutable, but not other attributes) is
painful.  I *do* think that having a natively supported type for these
"octet buffers" is handy, especially when doing IO.  But most of the
time, I want something else.

One way to think about why it's irritating for me is that by far the
*easiest* things to point to for "reasons the ML type system is really
helpful" are refs and options.  Because the default behavior is that
everything is immutable, but refs are simple and easy to use, we have
the option in ML to choose whether our datatype should be mutable or
not.  (Extend that somewhat to include Caml's mutable annotation,
which I think is acceptable.)  Likewise, by default every value must
be given, but options give us the ability to provide a kind of "null"
value.  (And if we wish to define our own datatype, we can distinguish
different types of null--N/A vs. unknown, for a basic example.)

But the way Caml strings are done forces us to deal with the fact that
every string is mutable--we don't have the option of making a string
that isn't.  If we want to, we can package things up to prevent
this--providing a way to box up a string into an immutable string
(make a copy, prevent mutation using the type system).  But then we
can't use the standard library without unboxing (making another copy)
to get a "normal" string value out.

This isn't the end of the world, of course.  But it is a wart that I
periodically meditate on.

John.

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

[brogoff]

On Thu, 10 Feb 2005, Harrison, John R wrote:
> | > 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.
>
> That's far too categorical; opinions differ on this subject.
> I'd be
> quite
> happy with strings as lists of characters, and I consider OCaml's
> mutable
> strings a far worse design error.

I disagree. Given strings as lists, or even something not as ridiculous, like
ropes (which Pierre Weis said existed in an older Caml) the programmer can
not write an efficient mutable string over it.  And, mutability aside, string
algorithms usually view strings as arrays, not lists. At least the other lazy
language gets this right. You would penalize almost all nontrivial string
manipulation programs if we fixed this "design error" with the approach you
find less odious.

IMO, the problem is that no one string (or array) type suffices for all or even
most purposes, and without some kind of overloading, having say five or six
different string types becomes notationally heavy.

So, while I'd love to have immutable strings, if there is going to be just one
privileged string type in OCaml, I think mutable strings are a reasonable
choice, not an error. Error is far too categorical.

> And yes, I use "implode" and "explode" all the time,

Have you no shame, to broadcast these perversions in a group which may have
young programmers? Really! ;-)

> because lists of
> characters are often simple and convenient to deal with in a functional
> style, and string manipulations are almost never performance-critical
> in the kind of code I write.

And you can (but shouldn't!) write those functions in your sleep in a few lines
of ML, over the existing mutable strings.

My preference for functional string processing is, as I said, substrings.
They are convenient, and encapsulate the index manipulations in the
data type. I'm almost certain you've seen them, what's your issue?

-- Brian

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

[Harrison, John R]

| > ...I consider OCaml's mutable strings a far worse design error.
| 
| That's interesting. Why?

Because it destroys persistence, one of the most fundamental advantages
of functional programming. Any function I call with a string argument
can
choose to modify it, and cause side-effects elsewhere.

Even Java has immutable strings, doesn't it? And I notice this feature
of OCaml is fixed in F#. All for very sound reasons, in my opinion.

John.

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

[Harrison, John R]

| My preference for functional string processing is, as I said,
substrings.
| They are convenient, and encapsulate the index manipulations in the
data
| type. I'm almost certain you've seen them, what's your issue?

None whatsoever. I'm perfectly willing to believe that some variant
of character arrays is the best string representation. (Provided
they are immutable!)

But for the relatively trivial string manipulations that I (and
quite possibly many other OCaml users) care about, lists of
characters are very convenient and perfectly adequate. So I don't
feel your hyperbolic dismissals of such a representation as
"dumb" and "ridiculous" are justified. You could say that with
equal force about any use of lists instead of arrays, and I'm
sure there are plenty of programmers who would.

John.