[Caml-list] looping recursion

[Caml-list] looping recursion

[briand]

Well without an eof-object to check for (as in scheme) I've started
using the following code chunk to read all the lines out of a file :

let read_file filename =
  let file = open_in filename in
  let rec proc line =
    print_string line;
    print_newline();
    try
      proc (input_line file);
    with
        End_of_file -> true;
  in
    proc (input_line file);


works great until you read enough lines and then you get:

Stack overflow during evaluation (looping recursion?).

naturally I suspected that the try was perhaps ruining the
tail-callness of the code, so I moved it outside of the recursive
proc, i.e.

let rec proc line =
...
in
try
 proc (input_line file);
with
 End_of_file -> true;

and that works just fine.

Is there a better way to just pull in all the lines of a file ?  I've
just gotten used to doing it like this, because in scheme it's very
clean.  And since I'm not actually accumulating anything, I'm most
confused as to how the stack space is disappearing.

Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[John Prevost]

On Tue, 27 Jul 2004 16:43:10 -0700, briand@aracnet.com
<briand@aracnet.com> wrote:
> Well without an eof-object to check for (as in scheme) I've started
> using the following code chunk to read all the lines out of a file :
  {...}
> works great until you read enough lines and then you get:
> 
> Stack overflow during evaluation (looping recursion?).
> 
> naturally I suspected that the try was perhaps ruining the
> tail-callness of the code, so I moved it outside of the recursive
> proc, i.e.

Yup--this is one of the big things you have to watch out for when
doing tail loops.  The easy way to think of it is "try always makes
stack frames, so use try at the top level and then escape all the way
out".  In essence, if there's a try block around your expression, it's
not in tail position (even if every try block will return the same
thing.)

Here's an example of a loop that makes that obvious:

exception Boom

let rec loop x =
  try
    if x < 100 then loop (x + x) else raise Boom
  with Boom -> x

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[skaller]

On Wed, 2004-07-28 at 09:43, briand@aracnet.com wrote:

>  And since I'm not actually accumulating anything, I'm most
> confused as to how the stack space is disappearing.

The recursion is stacking up the exception handlers.

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



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[John Prevost]

Oops.  Hit the send button before I meant to...

Anyway, that little loop with Boom example should show why the try
prevents the inner call from being in tail position: because the try
block's expressions can refer to variables in the scope of the
original function call, there's a possible continuation (you raise an
exception) that brings those variables back into scope.

The compiler *could*, I suppose, do some magic and notice when there
are no locally bound variables in the exception code path, but even
just thinking about how that might be implemented, I think it could
get messy.  What if it's not always the same try block that's around
the call that would otherwise be a tail call?  What if the fact that
there are multiple exception handlers is important, like:

exception Boom2 of int

let rec loop2 x =
  try
    if x < 100 then loop2 (x + x) else raise (Boom2 0)
  with Boom2 y -> raise (Boom2 (y + 1))

let use_loop2 x = try loop2 x with Boom2 y -> y

In this second example, use_loop2 is using the exceptions in loop2 to
calculate the result.  (Admittedly, this is a bizarre little setup.)

So figuring out if it's "safe" to make it a tail call is hard--not to
mention it would probably end up confusing the user even more if it
did work only part of the time.  (How do I change this so it's
recongnized as tail recursive again?)

Hope this helps.  :)  I tried to find an FAQ entry on this, because I
thought there was one, but was unable to find anything.

John.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[briand]

After sufficient googling I finally found a post which yields the answer :

let readfile chan =
  let rec loop rlst =
    let line, eof = 
      try
        (input_line chan), false
      with
        | End_of_file -> "", true
    in
      if not eof then
        loop (line :: rlst)
      else
        List.rev rlst
  in
    loop []
;;

but then it gets better.  Imagine my surprise when the following failed:

let data = readfile (open_in "data") in
let split_lines = List.map
                    (fun line ->
                       line;
                    )
                    data
in
  print_string "Done.\n";;

That's just not good !  I can't even use standard map without the
stack blowing up ?  This is a Bad Thing (TM).

Oh but wait. I peruse the manual.  map_rev is what I want.

So I'm going to make a bold statement that .map which blows up
shouldn't even exist and .rev_map should be renamed to .map.

Naturally someone will be telling me very shortly why you can't do this...

Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[skaller]

On Wed, 2004-07-28 at 10:38, John Prevost wrote:

> 
> exception Boom2 of int
> 
> let rec loop2 x =
>   try
>     if x < 100 then loop2 (x + x) else raise (Boom2 0)
>   with Boom2 y -> raise (Boom2 (y + 1))
> 
> let use_loop2 x = try loop2 x with Boom2 y -> y
> 
> In this second example, use_loop2 is using the exceptions in loop2 to
> calculate the result.  (Admittedly, this is a bizarre little setup.)

I'm actually doing something like this (unfortunately)
in the Felix compiler.

Basically, Felix has overloading and requires the function
argument type to be specified, but the return type is deduced
bottom up by actually examining the function's return statement
argument type.

Unfortunately, this situation is complicated by the fact
a function can call itself. However, we cant just plug in
a type variable for the function's return type, calculate
the result, and then unify to eliminate the variable,
as Ocaml could, because in Felix functions can be overloaded.
So to calculate in function f, what the type of f(a) is,
we again have to do overload resolution. Having done that
we need the return type of the function .. but we can't
calculate it because that's what we're already in the middle
of doing, and we'd get an infinite loop.

you might think a type variable could be introduced here,
and eliminated when we pop back, but that isn't so.
The problem is we might have in f:

   return g (f a);

and now, the recursion isn't tail, and we have to have
a definite type for f a, in order to calculate which g
is called, in order to calculate the type of f.

So I just throw an exception and ignore that return statement.
Such recursions (in the client Felix code) usually 
have conditionals wrapped around them and one branch 
had better give a result: otherwise
the client must specify the return type.

[I suspect in terminating code this cannot be needed but
I'm not sure]

the actual algorithm unifies the specified return
type (if given) with all the types of return
statements (which don't lead to infinite recursion).

I have tried to localise exception handling in my
code but this is one case where I couldn't figure
out how to do so. It is of course vital that
the exception handlers stack up here, so the exceptions
propagate far enough but no further.

[The code is extremely messy and I'm not even sure it 
gives the correct result when it does succeed :]

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



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[Brian Hurt]

On Tue, 27 Jul 2004 briand@aracnet.com wrote:

> That's just not good !  I can't even use standard map without the
> stack blowing up ?  This is a Bad Thing (TM).

Take a look at ExtLib:
http://sourceforge.net/projects/ocaml-lib/

This contains a drop-in compatible replacement to the List library, which 
includes a List.map function that doesn't blow up.

If your list is that long, I'd actually recommend doing one of two things:

1) Switch off your list data structure for a more complicated data 
structure, like a Set.  If you do any sort of complicated access 
patterns, this will likely be a big win, or

2) If you only ever need to iterate through the list (and thus have simple 
access requirements), consider switching over to using an ExtLib style 
enum (same basic concept as Java's Iterator class).  This allows you do 
"wavefront" processing- apply the map to the list items as you read them 
in.

Very long lists are a sign that you're using the wrong data structure.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[briand]

>>>>> "Brian" == Brian Hurt <bhurt@spnz.org> writes:

  Brian> Take a look at ExtLib:
  Brian> http://sourceforge.net/projects/ocaml-lib/

thanks for the link.

  Brian> This contains a drop-in compatible replacement to the List
  Brian> library, which includes a List.map function that doesn't blow
  Brian> up.

  Brian> If your list is that long, I'd actually recommend doing one
  Brian> of two things:

it really is.
although I'd actually like it to be an array.
it's the classic situation, read whole file - iterate on elements.
easy to do in a list since I don't need to know the size.

some minor tweaks and I can include the size in a data file and just
fill an array directly.

however, my larger point is the fact that the "standard" map blows up
like that.  as a long time scheme user I just find that plain weird.
Now Everybody else seems to think I'm weird because I think that's
weird ;-)

  Brian> Very long lists are a sign that you're using the wrong data
  Brian> structure.

I'm not sure I understand that.  I have 10^6 data points to work on.
I'm thinking a list or an array is the right data structure.  Although
an array is more right.  I mean if you are not worried about
efficiency then incremental transformation by map'ing is a very
elegant and clean way to go about doing that sort of work.

Part of the problem is that powerful computers make for lazy
programmers :-) It's just so easy to read the 10^6 elements into a
list and then just keep map'ing them to the final value when it only
takes seconds to do :-) If it took 2 minutes I'd be more inclined to
think about the problem.

Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[Brian Hurt]

On Tue, 27 Jul 2004 briand@aracnet.com wrote:

> it really is.
> although I'd actually like it to be an array.
> it's the classic situation, read whole file - iterate on elements.
> easy to do in a list since I don't need to know the size.
> 
> some minor tweaks and I can include the size in a data file and just
> fill an array directly.
> 
> however, my larger point is the fact that the "standard" map blows up
> like that.  as a long time scheme user I just find that plain weird.
> Now Everybody else seems to think I'm weird because I think that's
> weird ;-)
> 
>   Brian> Very long lists are a sign that you're using the wrong data
>   Brian> structure.
> 
> I'm not sure I understand that.  I have 10^6 data points to work on.
> I'm thinking a list or an array is the right data structure.  Although
> an array is more right.  I mean if you are not worried about
> efficiency then incremental transformation by map'ing is a very
> elegant and clean way to go about doing that sort of work.
> 
> Part of the problem is that powerful computers make for lazy
> programmers :-) It's just so easy to read the 10^6 elements into a
> list and then just keep map'ing them to the final value when it only
> takes seconds to do :-) If it took 2 minutes I'd be more inclined to
> think about the problem.
> 

You want an enumeration.  You're basically taking a file, reading it into 
a list, mapping the list multiple different times, and then writting out 
the result, right?  Well, enumerations work the same way.  You take the 
file, and create an enumeration of the lines of the file (there's a 
function that does that).  You then map the enumeration multiple times, 
same map functions.  Then you write out the result.  As a programmer, it 
doesn't change the problem all that much.

But it allows the library to optimize things.  Maps of enumerations are 
applied lazily- that means they aren't calculated until the result is 
needed.  By creating the enumeration of the file doesn't read the file at 
that point.  When you go to write the result out, the output function 
grabs the first line from the enumeration.  This causes the enumeration to 
actually go read the first line of the input file, and apply all the 
appropriate maps to it, before writting it to the output file.  And so on.
You write the code as if the entire data structure were present right now, 
but it works like a stream processor.  With no extra work on the part of 
the programmer.


-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[Brian Hurt]

Hit "send" before I meant too- sorry.

On Tue, 27 Jul 2004 briand@aracnet.com wrote:

> however, my larger point is the fact that the "standard" map blows up
> like that.  as a long time scheme user I just find that plain weird.
> Now Everybody else seems to think I'm weird because I think that's
> weird ;-)

I agree with you.  Or rather, I don't think it's weird so much as really 
bad.  The problem is correct, and (while not as efficient as it might be) 
it sounds like it's not horribly inefficient either.  It's certainly not a 
bad idea to get it working first, and then worry about algorithmic 
inefficiencies.  I'd much rather have a program that takes two minutes to 
return the right answer, than a program that returns the wrong answer in 2 
seconds (or segfaults in 2 milliseconds, but that isn't a danger in 
Ocaml).


-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[brogoff]

On Tue, 27 Jul 2004 briand@aracnet.com wrote:
> >>>>> "Brian" == Brian Hurt <bhurt@spnz.org> writes:
> it really is.
> although I'd actually like it to be an array.
> it's the classic situation, read whole file - iterate on elements.
> easy to do in a list since I don't need to know the size.
>
> some minor tweaks and I can include the size in a data file and just
> fill an array directly.
>
> however, my larger point is the fact that the "standard" map blows up
> like that.  as a long time scheme user I just find that plain weird.
> Now Everybody else seems to think I'm weird because I think that's
> weird ;-)
>
>   Brian> Very long lists are a sign that you're using the wrong data
>   Brian> structure.
>
> I'm not sure I understand that.

I've heard the argument plenty of times, and I'm familiar with all of the
common data structures (and the uncommon ones in Okasaki's book), and I don't
buy that argument either.

It's a limitation of the current OCaml list library functions and the current
implementation of OCaml. You can easily fix it yourself by writing mapand
friends  to be tail recursive in the straightforward way (suboptimal efficiency,
but better than failing)  or the non-obvious way using Obj to make the
equivalent of set-cdr! (what ExtLib does) or wait until the implementors
decide to fix this by adding a language feature and reimplementing List.
Don't hold your breath for that last option.

> Part of the problem is that powerful computers make for lazy
> programmers :-) It's just so easy to read the 10^6 elements into a
> list and then just keep map'ing them to the final value when it only
> takes seconds to do :-) If it took 2 minutes I'd be more inclined to
> think about the problem.

Sometimes lists are best. If lists are OK for 100, 1_000, or 10_000 items,
why not 100_000 or 1_000_000? Map and friends shouldn't blow stack.

-- Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[Alex Baretta]

brogoff wrote:
> Sometimes lists are best. If lists are OK for 100, 1_000, or 10_000 items,
> why not 100_000 or 1_000_000? Map and friends shouldn't blow stack.
> 
> -- Brian

Actually, it's not that bad.

Sometimes I design an algorithm in terms of basic data structures, such 
as lists, and transformations applied through higher order iterators. 
Such "featurs" as the stack overflow in List.map or the Linux 
out-of-memory SIGKILL give me a clear indication of the simplemindedness 
of such algorithms and force me to rethink them in terms of more 
efficient structures and techniques, typically streams and laziness.

Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[skaller]

On Wed, 2004-07-28 at 11:43, Brian Hurt wrote:
> On Tue, 27 Jul 2004 briand@aracnet.com wrote:

> Very long lists are a sign that you're using the wrong data structure.

What would you recommend for a sequence of tokens?
Streams are slow and hard to match on.. bucket lists
have lower storage overhead but hard to match on.

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



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[Brian Hurt]

On 28 Jul 2004, skaller wrote:

> On Wed, 2004-07-28 at 11:43, Brian Hurt wrote:
> > On Tue, 27 Jul 2004 briand@aracnet.com wrote:
> 
> > Very long lists are a sign that you're using the wrong data structure.
> 
> What would you recommend for a sequence of tokens?
> Streams are slow and hard to match on.. bucket lists
> have lower storage overhead but hard to match on.

Extlib Enumerations.  For short lists, yeah they're slower than lists.  
But for long lists, I could see them being a lot faster.  Don't forget 
cache effects- streaming processing can have much better cache behavior 
than repeatedly walking a long list (too large to fit into cache). 


-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[brogoff]

On Wed, 28 Jul 2004, Alex Baretta wrote:
> brogoff wrote:
> > Sometimes lists are best. If lists are OK for 100, 1_000, or 10_000 items,
> > why not 100_000 or 1_000_000? Map and friends shouldn't blow stack.
> >
> > -- Brian
>
> Actually, it's not that bad.

Well, I'm still on the caml-list, so of course it isn't *that* bad. Also, as
I said, if you need a tail recursive map over built in lists, you have at
least two options. Unfortunately, my preference is to use Obj, which IMO
points to a deficiency in the core language. Most, maybe all, of my issues
with OCaml, amount to petty complaints, no showstoppers or dealbreakers.
Hey, at least I'm not whining about the license!

> Sometimes I design an algorithm in terms of basic data structures, such
> as lists, and transformations applied through higher order iterators.
> Such "featurs" as the stack overflow in List.map or the Linux
> out-of-memory SIGKILL give me a clear indication of the simplemindedness
> of such algorithms and force me to rethink them in terms of more
> efficient structures and techniques, typically streams and laziness.

There are quite a few cases where singly linked lists are the most efficient
data structure, and they're just right for the problem. Streams and laziness
are  not at all efficient in comparison. Stack overflow commonly happens when
one of my users (yup, I have users of my code who aren't me ;-) decides to
run on data much larger than I'd anticipated.

Also, lists are builtin, and have syntactic support in OCaml, by which I mean
nice, easy to read syntax. So the language encourages you to use them.

-- Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[Jon Harrop]

On Wednesday 28 July 2004 17:38, brogoff wrote:
> > brogoff wrote:
> > > Sometimes lists are best. If lists are OK for 100, 1_000, or 10_000
> > > items, why not 100_000 or 1_000_000? Map and friends shouldn't blow
> > > stack.

Creating an int list with 1,000,000 elements and applying List.map using 
ocamlopt works fine here, and took a meagre 3.6 secs.

If you must use bytecode for this then just increase the stack size limit, for 
example to 8Mb:

export OCAMLRUNPARAM='l=8M'

Then it runs fine, in 10.7 secs here. Wow, that's quite fast... :-)

> Well, I'm still on the caml-list, so of course it isn't *that* bad. Also,
> as I said, if you need a tail recursive map over built in lists, you have
> at least two options. Unfortunately, my preference is to use Obj, which IMO
> points to a deficiency in the core language.

No! That points to a severe deficiency in your programming style. OCaml has 
been developed and used by a great many very clever people, and me. If you're 
doing things like that then you should immediately stop and think what you 
might be doing wrong. Perhaps you picked the bad style up at a Seattle OCaml 
user group meeting?

What's wrong with List.rev_map, List.rev (List.rev_map ...), increasing the 
size of the VM's stack, using native code or even writing your own, 
tail-recursive map?

Cheers,
Jon.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

RE: [Caml-list] looping recursion

[Brandon J. Van Every]

Jon Harrop wrote:
> 
> No! That points to a severe deficiency in your programming 
> style. OCaml has 
> been developed and used by a great many very clever people, 
> and me. If you're 
> doing things like that then you should immediately stop and 
> think what you might be doing wrong. 

Although you might have a point, your need to bluster lends no weight.

> Perhaps you picked the bad style up at 
> a Seattle OCaml user group meeting?

Did you learn to debate from a politician, in soundbytes?


Cheers,                         www.indiegamedesign.com
Brand*n Van Every               S*attle, WA

Praise Be to the caml-list Bayesian filter! It blesseth
my postings, it is evil crap!  evil crap!  Bigarray!
Unboxed!  Overhead!  Wondering!  chant chant chant...

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[brogoff]

On Wed, 28 Jul 2004, Jon Harrop wrote:
> On Wednesday 28 July 2004 17:38, brogoff wrote:
> > > brogoff wrote:
> > > > Sometimes lists are best. If lists are OK for 100, 1_000, or 10_000
> > > > items, why not 100_000 or 1_000_000? Map and friends shouldn't blow
> > > > stack.
>
> Creating an int list with 1,000,000 elements and applying List.map using
> ocamlopt works fine here, and took a meagre 3.6 secs.
>
> If you must use bytecode for this then just increase the stack size limit, for
> example to 8Mb:
>
> export OCAMLRUNPARAM='l=8M'
>
> Then it runs fine, in 10.7 secs here. Wow, that's quite fast... :-)

I'm going to guess that you don't have much OCaml code running at a customer
site. Yes, I'm aware that stack size can be reset. Oh joy. I guess we don't
need tail call elimination at all then?

> > Well, I'm still on the caml-list, so of course it isn't *that* bad. Also,
> > as I said, if you need a tail recursive map over built in lists, you have
> > at least two options. Unfortunately, my preference is to use Obj, which IMO
> > points to a deficiency in the core language.
>
> No! That points to a severe deficiency in your programming style. OCaml has
> been developed and used by a great many very clever people, and me. If you're
> doing things like that then you should immediately stop and think what you
> might be doing wrong.

I guess all of the authors of ExtLib, who, last time I checked, used a set_cdr
approach, are also tyros compared to you?

> Perhaps you picked the bad style up at a Seattle OCaml user group meeting?

Very classy. :-(

> What's wrong with List.rev_map, List.rev (List.rev_map ...), increasing the
> size of the VM's stack, using native code or even writing your own,
> tail-recursive map?

I'm pretty damned well aware that I can reverse a rev mapped list. Does it occur
to you that that is not efficient? Have you tried comparing the run times of
this versus set_cdr version? Where were you when the "tail recursion modulo
cons" discussion came up? Do you understand that optimization? Here's a pointer
for you

	http://caml.inria.fr/archives/200306/msg00254.html

By my measurements, even for small lists, the set_cdr version was as fast (a
little faster even) than List.map, and it had the nice property of not failing
with huge lists.

-- Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[skaller]

On Thu, 2004-07-29 at 00:36, Brian Hurt wrote:
> On 28 Jul 2004, skaller wrote:
> 
> > On Wed, 2004-07-28 at 11:43, Brian Hurt wrote:
> > > On Tue, 27 Jul 2004 briand@aracnet.com wrote:
> > 
> > > Very long lists are a sign that you're using the wrong data structure.
> > 
> > What would you recommend for a sequence of tokens?
> > Streams are slow and hard to match on.. bucket lists
> > have lower storage overhead but hard to match on.
> 
> Extlib Enumerations.  For short lists, yeah they're slower than lists.  

That doesn't matter -- the lists are long by specification.

> But for long lists, I could see them being a lot faster.  Don't forget 
> cache effects- streaming processing can have much better cache behavior 
> than repeatedly walking a long list (too large to fit into cache). 

Can't pattern match on them. One reason for building
a list is I filter it, for example, in Felix I strip out white space
tokens, in Vyper (Python interpreter written in Ocaml)
I did something like 13 separate passes to handle
the indentation and other quirks to precondition the input
to the parser so it became LALR(1).

So, I'd have to use a list as a buffer for the head of the stream
anyhow..

Also, there is a serious design problem with ExtLib Enums.
Although the data structure appears functional, it doesn't
specify when things happen precisely.

In particular if the input is a stream, that is, uses 
mutators to extract elements, then instead of using
the persistence and laziness so you can use the Enums
as forward iterators -- for example in a backtracking
parser -- the Enums actually degrade to uncopyable
input iterators.

Since Ocamllex uses a mutable lex buffer, the Enums
based on them are also non-functional input iterators ..
[I can get around that by calling 'force()' but that
totally defeats the purpose of using Enums .. :]

Whereas, a plain old list is a purely functional
forward iterator, and unquestionably works with
a backtracking parser.

As an example of a simple modification I could do that
won't work easily with uncontrolled control inversion:
suppose I cache the token stream on disk, and in
particular Marshal file 'fred.flx' out as 'fred.tokens'.
[Now you *have* to force() all the iterators, or
each one inside the #include will write the file
to disk at the end of the sub-file .. but that 
should only be done once -- its quite slow writing
a file to disk .. forcing all the enums makes
separate copies of the tokens .. argggg .. ]

The problem goes away when I manually build lists
and preprocess them because I have explicit control.

Bottom line is that Enums work fine to integrate
purely functional data structures together but they're
not very useful mixing coupled streams together.

Crudely -- if you have a hierarchy of streams
you may need to read them in a particular order
due to the coupling .. with STL input iterators
you can do that, with hand written Ocaml
you can do that -- with Enums you can't.

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



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[Alex Baretta]

Brandon J. Van Every wrote:
> Jon Harrop wrote:
> 
>>No! That points to a severe deficiency in your programming 
>>style. OCaml has 
>>been developed and used by a great many very clever people, 
>>and me. If you're 
>>doing things like that then you should immediately stop and 
>>think what you might be doing wrong. 
> 
> 
> Although you might have a point, your need to bluster lends no weight.
> 
> 
>>Perhaps you picked the bad style up at 
>>a Seattle OCaml user group meeting?
> 
> 
> Did you learn to debate from a politician, in soundbytes?

May I respectfully suggest that you guys flame each other to death 
elsewhere? This place is for technical discussions, not for personal 
insults.

Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[Alex Baretta]

brogoff wrote:
> On Wed, 28 Jul 2004, Alex Baretta wrote:
> 
>>brogoff wrote:
>>
>>>Sometimes lists are best. If lists are OK for 100, 1_000, or 10_000 items,
>>>why not 100_000 or 1_000_000? Map and friends shouldn't blow stack.
>>>
>>>-- Brian
>>
>>Actually, it's not that bad.
> 
> 
> Well, I'm still on the caml-list, so of course it isn't *that* bad. Also, as
> I said, if you need a tail recursive map over built in lists, you have at
> least two options. Unfortunately, my preference is to use Obj, which IMO
> points to a deficiency in the core language. Most, maybe all, of my issues
> with OCaml, amount to petty complaints, no showstoppers or dealbreakers.
> Hey, at least I'm not whining about the license!

Yes, I guess we simply can live with it. I can't wait to have STL 
iterators in Ocaml, but meanwhile I can live with this functional 
nonsense: lists, maps, sets... ;)

> There are quite a few cases where singly linked lists are the most efficient
> data structure, and they're just right for the problem. Streams and laziness
> are  not at all efficient in comparison. Stack overflow commonly happens whenm
> one of my users (yup, I have users of my code who aren't me ;-) decides to
> run on data much larger than I'd anticipated.

Huge lists are usually not an efficient data structure. Lists are local 
structures: at any point you can only observe a fixed number of head 
elements (usually one at a time) and an unspecified tail. Such locality 
generally makes caching the entire data structure useless. Long lists 
(lists of a priori unbounded length) arise from user input: typically 
the are obtained by reading in a file of a priori unbounded length. In 
such cases lists are very much inefficient from the point of view of 
memory complexity: lists cost O(n) where n is the size of the input; 
streams cost O(1). Both cost O(n) in terms of time complexity. Usually 
the potential speed benefit of lists is amply counterbalanced by 
reduction in memory footprint, which usually means no memory swapping in 
the kernel.

Here's an obvious example (not too obvious: I fell for it at first). I 
have a XML syntax specifying relational databases. Essentially an entire 
relational database can be represented with it. This XML lexicon is 
meant for now only for the database initial schema definition and for 
human-readable backups. I initially wrote the backup algorithm in terms 
of transformations on a list of PXP trees which were finally serialized. 
Algebraically, this is perfect. The only problem is that this algorithm 
stores the entire contents of a database in memory before serializing 
everything. Ooops, here's a SIGKILL landing in! Now I only use PXP trees 
to represent the database schema, which I immediately begin to 
serialize. All the while I pass around continuations which are invoked 
iteratively on subnodes. If a subnode is an table-data node I declare an 
SQL cursor in the database and begin walking through the table. Result, 
where my initial memory footprint bought me a SIGKILL on a 2GB server 
now I have bounded memory usage (a few megabytes). I don't swap, so the 
the backup process actually runs an order of magnitude faster. And I 
actually get my output at the end ;)

> Also, lists are builtin, and have syntactic support in OCaml, by which I mean
> nice, easy to read syntax. So the language encourages you to use them.

They are sooo cool! I actually ask all trainees to reimplement the List 
module. But then the industrial practice is to use lists only where 
there is no input or as the result of some kind of slicing or research 
applied to bigger and more efficient data structures. I actually use a 
list iteration to schedule tasks in my real-time control kernel, but of 
course, I don't expect my collegues to write more than a few tasks at a 
time for my kernel to schedule: safety, liveness and UI.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[Daniel Andor]

On Wednesday 28 July 2004 10:22 pm, brogoff wrote:
> On Wed, 28 Jul 2004, Jon Harrop wrote:
> > On Wednesday 28 July 2004 17:38, brogoff wrote:
> > > > brogoff wrote:
> > > > > Sometimes lists are best. If lists are OK for 100, 1_000, or 10_000
> > > > > items, why not 100_000 or 1_000_000? Map and friends shouldn't blow
> > > > > stack.
[...]
> > What's wrong with List.rev_map, List.rev (List.rev_map ...), increasing
> > the size of the VM's stack, using native code or even writing your own,
> > tail-recursive map?
>
> I'm pretty damned well aware that I can reverse a rev mapped list. 

If you've got the mutable list version of map to hand, and you are happy with 
that, then that's clearly the way to go.

But the rev version of map is the same linear complexity as all the map 
functions, and is not much more inefficient than the stack version: CPU or 
memory-wise (given my limited understanding of the GC).  So if you were happy 
with List.map, except that it blew up on you, then you should definitely be 
happy with List.rev (List.rev_map ..).

Lemme try it out (10^6 elements):

ocamlc:
rev rev_map version:
 2 WALL ( 1.19 usr +  0.02 sys =  1.21 CPU)
vanilla map:
 7 WALL ( 6.50 usr +  0.09 sys =  6.59 CPU)

ocamlopt:
rev rev_map version:
 1 WALL ( 0.81 usr +  0.03 sys =  0.84 CPU)
vanilla map:
 2 WALL ( 2.45 usr +  0.02 sys =  2.47 CPU)

Wow, that was unexpected! 

> Does it occur to you that that is not efficient? 

Not any more!

Daniel.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[Keith Wansbrough]

> Lemme try it out (10^6 elements):
> 
> ocamlc:
> rev rev_map version:
>  2 WALL ( 1.19 usr +  0.02 sys =  1.21 CPU)
> vanilla map:
>  7 WALL ( 6.50 usr +  0.09 sys =  6.59 CPU)
> 
> ocamlopt:
> rev rev_map version:
>  1 WALL ( 0.81 usr +  0.03 sys =  0.84 CPU)
> vanilla map:
>  2 WALL ( 2.45 usr +  0.02 sys =  2.47 CPU)

OK, so why is List.map in the OCaml standard library implemented the
vanilla way rather than the rev rev_map way?  If it's such a big win,
it seems foolish to have a broken implementation for such a crucial
function.

(BTW, if you want efficient (and pure) mapping and filtering over long
streams, you should consider using lazy lists.  A good compiler (like
GHC) will do the deforestation optimisation, so the list is never even
allocated[1].)

[1] unless you make use of persistence, of course.

--KW 8-)

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[Nicolas Cannasse]

> > Lemme try it out (10^6 elements):
> >
> > ocamlc:
> > rev rev_map version:
> >  2 WALL ( 1.19 usr +  0.02 sys =  1.21 CPU)
> > vanilla map:
> >  7 WALL ( 6.50 usr +  0.09 sys =  6.59 CPU)
> >
> > ocamlopt:
> > rev rev_map version:
> >  1 WALL ( 0.81 usr +  0.03 sys =  0.84 CPU)
> > vanilla map:
> >  2 WALL ( 2.45 usr +  0.02 sys =  2.47 CPU)
>
> OK, so why is List.map in the OCaml standard library implemented the
> vanilla way rather than the rev rev_map way?  If it's such a big win,
> it seems foolish to have a broken implementation for such a crucial
> function.
>
> (BTW, if you want efficient (and pure) mapping and filtering over long
> streams, you should consider using lazy lists.  A good compiler (like
> GHC) will do the deforestation optimisation, so the list is never even
> allocated[1].)
>
> [1] unless you make use of persistence, of course.
>
> --KW 8-)

I think in this thread both "problems" are resolved by ExtLib :
- a fully tail-recursive List module
- Enums for lazy lists

http://ocaml-lib.sf.net

So of course you can still get the pro and cons of having ExtLib
implementation being the standard one, but anyone actually have the choice,
that's important. The choice is up to OCaml INRIA team, and I don't think
any thread - as long and flammy as it could be - would change their
opinions.

Regards,
Nicolas Cannasse

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[Xavier Leroy]

> > Lemme try it out (10^6 elements):
> > 
> > ocamlc:
> > rev rev_map version:
> >  2 WALL ( 1.19 usr +  0.02 sys =  1.21 CPU)
> > vanilla map:
> >  7 WALL ( 6.50 usr +  0.09 sys =  6.59 CPU)
> > 
> > ocamlopt:
> > rev rev_map version:
> >  1 WALL ( 0.81 usr +  0.03 sys =  0.84 CPU)
> > vanilla map:
> >  2 WALL ( 2.45 usr +  0.02 sys =  2.47 CPU)
> 
> OK, so why is List.map in the OCaml standard library implemented the
> vanilla way rather than the rev rev_map way?  If it's such a big win,
> it seems foolish to have a broken implementation for such a crucial
> function.

Because for smaller list the "vanilla way" is more efficient.
In the test above, the vanilla way spends significant time resizing
the stack.  I suspect that when running it a second time on a already
resized stack, the timings would improve quite a lot.

- Xavier Leroy

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[skaller]

On Thu, 2004-07-29 at 19:13, Daniel Andor wrote:

> Lemme try it out (10^6 elements):
> 
> ocamlc:
> rev rev_map version:
>  2 WALL ( 1.19 usr +  0.02 sys =  1.21 CPU)
> vanilla map:
>  7 WALL ( 6.50 usr +  0.09 sys =  6.59 CPU)
> 
> ocamlopt:
> rev rev_map version:
>  1 WALL ( 0.81 usr +  0.03 sys =  0.84 CPU)
> vanilla map:
>  2 WALL ( 2.45 usr +  0.02 sys =  2.47 CPU)
> 
> Wow, that was unexpected! 

The tail-rec version doesn't clobber the cache
with growing and shrinking stack -- you have
two areas of memory being accessed sequentially
instead of three .. (Ocaml allocator is sequential)

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



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[Daniel Andor]

On Thursday 29 July 2004 10:57 am, Xavier Leroy wrote:
> Because for smaller list the "vanilla way" is more efficient.

A little benchmarking with short lists shows that for lists that are near or 
smaller than my cache size (skaller's point), the stack map performs better; 
especially in the byte-code case.  

However, the thread was originally about long lists, and for that it is clear 
that algorithms other than the vanilla map are better suited.  To me, this 
just proves that there's no such thing as universal optimisation (yet!).  
One's got to actually think about the problem at hand. Damn. ;)

Daniel.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[brogoff]

On Thu, 29 Jul 2004, Daniel Andor wrote:
> On Wednesday 28 July 2004 10:22 pm, brogoff wrote:
> > On Wed, 28 Jul 2004, Jon Harrop wrote:
> > > On Wednesday 28 July 2004 17:38, brogoff wrote:
> > > > > brogoff wrote:
> > > > > > Sometimes lists are best. If lists are OK for 100, 1_000, or 10_000
> > > > > > items, why not 100_000 or 1_000_000? Map and friends shouldn't blow
> > > > > > stack.
> [...]
> > > What's wrong with List.rev_map, List.rev (List.rev_map ...), increasing
> > > the size of the VM's stack, using native code or even writing your own,
> > > tail-recursive map?
> >
> > I'm pretty damned well aware that I can reverse a rev mapped list.
>
> If you've got the mutable list version of map to hand, and you are happy with
> that, then that's clearly the way to go.

And I said as much. I also said it offends my sense of aesthetics ;-).

> Lemme try it out (10^6 elements):
>
> ocamlc:
> rev rev_map version:
>  2 WALL ( 1.19 usr +  0.02 sys =  1.21 CPU)
> vanilla map:
>  7 WALL ( 6.50 usr +  0.09 sys =  6.59 CPU)
>
> ocamlopt:
> rev rev_map version:
>  1 WALL ( 0.81 usr +  0.03 sys =  0.84 CPU)
> vanilla map:
>  2 WALL ( 2.45 usr +  0.02 sys =  2.47 CPU)
>
> Wow, that was unexpected!
>
> > Does it occur to you that that is not efficient?
>
> Not any more!

You neglected the "mutable" list version in your quickie benchmark. My
own quickie benchmark showed that version had better performance
than the doubly reversing implementation on large lists and very slightly
better performance than the default on small ones. I would expect that
if something like holes or promises (a la Alice SML) or whatever were in
OCaml, that under the hood it would be the same as the mutable list version and
so would have equivalent performance.

-- Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[brogoff]

On Thu, 29 Jul 2004, Daniel Andor wrote:

> On Thursday 29 July 2004 10:57 am, Xavier Leroy wrote:
> > Because for smaller list the "vanilla way" is more efficient.
>
> A little benchmarking with short lists shows that for lists that are near or
> smaller than my cache size (skaller's point), the stack map performs better;
> especially in the byte-code case.
>
> However, the thread was originally about long lists, and for that it is clear
> that algorithms other than the vanilla map are better suited.

It's not at all clear to me. Better how? Faster? Less coding effort? Clearer
to others maintaining the code?

> To me, this  just proves that there's no such thing as universal optimisation (yet!).

I agree with that. And I agree with Xavier's prioritization of a clean fix
to this as a "nice to have but not critical". For now, use ExtLib or roll your
own.

> One's got to actually think about the problem at hand. Damn. ;)

Yes. I'm going back to C and assembly code now, thanks to these arguments :-)

-- Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[brogoff]

On Thu, 29 Jul 2004, Alex Baretta wrote:
> brogoff wrote:
> > Well, I'm still on the caml-list, so of course it isn't *that* bad. Also, as
> > I said, if you need a tail recursive map over built in lists, you have at
> > least two options. Unfortunately, my preference is to use Obj, which IMO
> > points to a deficiency in the core language. Most, maybe all, of my issues
> > with OCaml, amount to petty complaints, no showstoppers or dealbreakers.
> > Hey, at least I'm not whining about the license!
>
> Yes, I guess we simply can live with it. I can't wait to have STL
> iterators in Ocaml, but meanwhile I can live with this functional
> nonsense: lists, maps, sets... ;)

That's funny! I used to get chided by the guy who hired me for being a
bit of a functional snob, always trying to find a side effect free solution
(BTW, the "mutable" lists using Obj are side effect free) instead of solving
every problem with a hash table :-)

Some problems are just way easier to solve with imperative programming
though. Have you ever taken a look at purely functional catenable deques?
If you don't need persistence (if your deques are used in a single threaded
manner that is) would you use those instead of the obvious doubly linked
list implementation? That's not an abstract question either, catenable deques
come up quite naturally when implementing some 2D computational geometry
algorithms.I took a look at the latest algorithm by Kaplan and Tarjan and
quickly realized that it was hugely complicated if persistence is not needed.

>
> > There are quite a few cases where singly linked lists are the most efficient
> > data structure, and they're just right for the problem. Streams and laziness
> > are  not at all efficient in comparison. Stack overflow commonly happens whenm
> > one of my users (yup, I have users of my code who aren't me ;-) decides to
> > run on data much larger than I'd anticipated.
>
> Huge lists are usually not an efficient data structure.

Sure, but sometimes you have programs which aren't intended to be used on huge
data sets, but pesky users aren't deterred by your warnings. So, even if the
extremely common case is not huge, it shouldn't fail in the huge case, unless of
course the failure is Out_of_memory.

-- Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[Brian Hurt]

On Thu, 29 Jul 2004, brogoff wrote:

> Some problems are just way easier to solve with imperative programming
> though. Have you ever taken a look at purely functional catenable deques?

Just got added to extlib, for the record.  A simplistic version that 
actually isn't that much more complicated than the imperitive 
implementation.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[james woodyatt]

On 29 Jul 2004, at 07:58, brogoff wrote:
>
> Some problems are just way easier to solve with imperative programming
> though. Have you ever taken a look at purely functional catenable 
> deques?
> If you don't need persistence (if your deques are used in a single 
> threaded
> manner that is) would you use those instead of the obvious doubly 
> linked
> list implementation? That's not an abstract question either, catenable 
> deques
> come up quite naturally when implementing some 2D computational 
> geometry
> algorithms.I took a look at the latest algorithm by Kaplan and Tarjan 
> and
> quickly realized that it was hugely complicated if persistence is not 
> needed.

As it happens, I have some experience with this problem.  I have 
implemented purely functional, catenable deques in Ocaml.  (I need the 
persistence.)  Yes, the Kaplan-Okasaki-Tarjan deques are hideously 
complicated.

However.  I have found a significantly simpler algorithm that uses lazy 
evaluation, still offers near real-time performance, and only adds the 
limitation that persistence is only available in program memory (lazy 
cells can't be marshalled, you know).  I can live with that limitation 
quite happily, and my deques are about three times as fast as the KOT 
deques.

My algorithm can be reviewed in the [Cf_deque] module of my Cf library. 
  The Ocaml HUMP has a link to it.  And the good news is that the 
algorithm is *not* patented as far as I know (the deadline for me to 
file an application has lapsed too), and the library is released under 
a BSD two-clause style license.  (I should be releasing an update to 
the library this week, but the [Cf_deque] module will not be changing.)

All that said, I can say that I have found I need persistent data 
structures to make other functional algorithms work well.  In those 
cases where I feel safe and comfortable mixing imperative and 
functional styles (fraught with peril!), then I certainly use the 
standard [Queue] module.  I'll be using that tactic in the [Cf_gadget] 
module when I make the next release (the current version uses 
[Cf_deque] unnecessarily).

[Off topic: there are also cases where I find the standard [Queue] 
module to be insufficiently well-endowed with utility functions, so I 
use my [Cf_deque] module instead.  It performs almost as well as 
[Queue], and it allows for more convenient transformation and 
manipulations of the represented sequence (see the [Cf_poll] module for 
an example of my thinking there).]


― ∴

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[james woodyatt]

On 29 Jul 2004, at 09:12, Brian Hurt wrote:
> On Thu, 29 Jul 2004, brogoff wrote:
>>
>> Some problems are just way easier to solve with imperative programming
>> though. Have you ever taken a look at purely functional catenable 
>> deques?
>
> Just got added to extlib, for the record.  A simplistic version that
> actually isn't that much more complicated than the imperitive
> implementation.

This is extraordinary!  Do you really mean to say the deques are purely 
functional, catenable *and* offering the same complexity as the 
non-persistent implementation?  Which algorithm was added to extlib?


― ∴

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[Brian Hurt]

On Thu, 29 Jul 2004, james woodyatt wrote:

> On 29 Jul 2004, at 09:12, Brian Hurt wrote:
> > On Thu, 29 Jul 2004, brogoff wrote:
> >>
> >> Some problems are just way easier to solve with imperative programming
> >> though. Have you ever taken a look at purely functional catenable 
> >> deques?
> >
> > Just got added to extlib, for the record.  A simplistic version that
> > actually isn't that much more complicated than the imperitive
> > implementation.
> 
> This is extraordinary!  Do you really mean to say the deques are purely 
> functional, catenable *and* offering the same complexity as the 
> non-persistent implementation?  Which algorithm was added to extlib?
> 

The version added is O(1) ammoritized.  It has the same problem as 
quicksort and hashtables, in that on average about 1 operation in N has 
cost O(N), instead of strict O(1).

The library added was the simplest double list implementation.  Basically, 
the queue is broken into two parts- a front part and a back part, both 
kept in lists.  The back part list is kept in reverse order- so to add an 
element to the end of the queue, you prepend it to the back part list.  
You remove elements from head of the front part queue, and when it's 
empty, you replace it with the reverse of the back part list.

Every element that goes through the queue is touched precisely three 
times- once when it's added to the end of the queue, once when it's 
removed from the head of the queue, and once when we reverse the back half 
to become the new front half.  So adding and then removing N elements from 
the list costs O(N).

The core code looks like this:

type 'a deque = 'a list * 'a list

let empty = ([], []) (* the empty queue *)

let add q x =
    match q with
        | ([], []) -> (* We add the first element to the front *)
            ([x], [])
        | ([], _) -> assert false
        | (front, back) -> (front, x :: back)

let remove q =
    match q with
        | ([], []) -> invalid_arg "remove"
        | ([], _) -> assert false
        | (h :: [], back) -> h, ((List.rev back), [])
        | (h :: front, back) -> h, (front, back)

I will note that if you use a capability that applicative semantics give 
us, you can get into trouble.  Imagine the following scenario: you create 
an empty queue and add 1000 new elements.  You then remove one element.  
This does a List.rev on a 999 element list.  You then throw the modified 
queue away, and remove the first element from the original queue again, 
reversing the same 999 element list.  Repeat- every removing reverses the 
same list.

The solution to this is "don't do that!"  Note that pushing an element 
onto the head of the queue is strict O(1):

let push x (front, back) = (x :: front, back)

Rather than using the applicative semantics to undo the removal, use push 
to push back the removed elements.  This way, you only reverse the back 
half of the list once.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[brogoff]

On Thu, 29 Jul 2004, Brian Hurt wrote:
> On Thu, 29 Jul 2004, james woodyatt wrote:
> > On 29 Jul 2004, at 09:12, Brian Hurt wrote:
> > > On Thu, 29 Jul 2004, brogoff wrote:
> > >>
> > >> Some problems are just way easier to solve with imperative programming
> > >> though. Have you ever taken a look at purely functional catenable
> > >> deques?
> > >
> > > Just got added to extlib, for the record.  A simplistic version that
> > > actually isn't that much more complicated than the imperitive
> > > implementation.
> >
> > This is extraordinary!  Do you really mean to say the deques are purely
> > functional, catenable *and* offering the same complexity as the
> > non-persistent implementation?  Which algorithm was added to extlib?
> >
>
> The version added is O(1) ammoritized.  It has the same problem as
> quicksort and hashtables, in that on average about 1 operation in N has
> cost O(N), instead of strict O(1).
>
> The library added was the simplest double list implementation.  Basically,
> the queue is broken into two parts- a front part and a back part, both
> kept in lists.  The back part list is kept in reverse order- so to add an
> element to the end of the queue, you prepend it to the back part list.
> You remove elements from head of the front part queue, and when it's
> empty, you replace it with the reverse of the back part list.

What you've described so far is a queue. I guess I was really oblique in my
message, or I'm just being really obtuse, but what I am basically asking for
something that implements this signature (people who don't likw modules, avert
your gaze!)

module type CatenableDeque =
  sig
    type 'a t
    val empty : 'a t
    val is_empty : 'a t -> bool

    val push_first : 'a -> 'a t -> 'a t
    val first : 'a t -> 'a
    val rest : 'a t -> 'a t

    val push_last : 'a -> 'a t -> 'a t
    val last : 'a t -> 'a
    val front : 'a t -> 'a t

    val append : 'a t -> 'a t -> 'a t
  end

and I want to be able to efficiently add at both ends and catenate. I ended up
doing this instead

module type ImpCatenableDeque =
  sig
    type 'a t

    val make : 'a -> 'a t

    val of_list : 'a list -> 'a t
    val to_list :  'a t -> 'a list

    val first   : 'a t -> 'a
    val last   : 'a t -> 'a

    val prev   : 'a t -> 'a t
    val next   : 'a t -> 'a t

    val insert_first : 'a -> 'a t -> unit
    val insert_last : 'a -> 'a t -> unit

    val remove_first : 'a t -> unit
    val remove_last : 'a t -> unit

    (** conc_front x y : x is modified so that y is in front, y destroyed *)
    val conc_front : 'a t -> 'a t -> unit
    (** conc_back x y : x is modified so that y is in back, y destroyed *)
    val conc_back : 'a t-> 'a t -> unit

    val iter : ('a -> unit) -> 'a t -> unit
    val iteri : (int -> 'a -> unit) -> 'a t -> unit
  end

and yes the implementation is a CS101 style doubly linked list, fraught with
peril. It may be mildly interesting to compare performance versus James
Woodyatt's version using lazy. If I remember correctly, Kaplan and Tarjan use
the term purely functional to exclude lazy in one of their papers, and just
allow primitive list ops like car/cdr/cons etc.

-- Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[Alex Baretta]

brogoff wrote:
> On Thu, 29 Jul 2004, Alex Baretta wrote:
> 
>>brogoff wrote:
> 
> Some problems are just way easier to solve with imperative programming
> though. Have you ever taken a look at purely functional catenable deques?
> If you don't need persistence (if your deques are used in a single threaded
> manner that is) would you use those instead of the obvious doubly linked
> list implementation? That's not an abstract question either, catenable deques
> come up quite naturally when implementing some 2D computational geometry
> algorithms.I took a look at the latest algorithm by Kaplan and Tarjan and
> quickly realized that it was hugely complicated if persistence is not needed.
s list: http://groups.yahoo.com/group/ocaml_beginners
> 

I didn't understand the connection between multithreading and
persistence, but it's probably too late and I've been working far too
much to follow you entirely. Let me just give you a couple eurocents of
industrial experience: side-effects are utterly bad. My Xcaml
application server was designed two years ago with one major flaw: one
global state variable. I'm still fighting with the execution engine to
take it away, but that won't happen before a major rewrite. I won't by
imperative programming for anything at all. And, yes, in my company the
mandated standard for deques is batched queues à la Okasaki.

Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[skaller]

On Fri, 2004-07-30 at 03:44, james woodyatt wrote:
> On 29 Jul 2004, at 07:58, brogoff wrote:

> And the good news is that the 
> algorithm is *not* patented as far as I know 

Australia does not allow algorithms to be patented anyhow .. :)

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



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[Corey O'Connor]

Is the connection due to persistance? 
So given a data structure is persistant across operations, let's say a
stack. Suppose if two threads are working with the same instance of a
data structure. One thread pushes a value onto the stack, the other
does not. Due to persistance the other thread's instance of the stack
is unaffected?

-Corey

On Fri, 30 Jul 2004 00:42:27 +0200, Alex Baretta <alex@baretta.com> wrote:
> 
> I didn't understand the connection between multithreading and
> persistence, but it's probably too late and I've been working far too
> much to follow you entirely. Let me just give you a couple eurocents of
> industrial experience: side-effects are utterly bad. My Xcaml
> application server was designed two years ago with one major flaw: one
> global state variable. I'm still fighting with the execution engine to
> take it away, but that won't happen before a major rewrite. I won't by
> imperative programming for anything at all. And, yes, in my company the
> mandated standard for deques is batched queues à la Okasaki.
> 
> Alex
> 
> 
> 
> -------------------
> To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
> Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> 


-- 
-Corey O'Connor

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[james woodyatt]

On 29 Jul 2004, at 13:01, brogoff wrote:
>
> What you've described so far is a queue. I guess I was really oblique  
> in my
> message, or I'm just being really obtuse, but what I am basically  
> asking for
> something that implements this signature (people who don't likw  
> modules, avert
> your gaze!)
>
> module type CatenableDeque =
>   sig
>     type 'a t
>     val empty : 'a t
>     val is_empty : 'a t -> bool
>
>     val push_first : 'a -> 'a t -> 'a t
>     val first : 'a t -> 'a
>     val rest : 'a t -> 'a t
>
>     val push_last : 'a -> 'a t -> 'a t
>     val last : 'a t -> 'a
>     val front : 'a t -> 'a t
>
>     val append : 'a t -> 'a t -> 'a t
>   end
>
> and I want to be able to efficiently add at both ends and catenate.  
> [...]
> and yes the implementation is a CS101 style doubly linked list,  
> fraught with
> peril. It may be mildly interesting to compare performance versus James
> Woodyatt's version using lazy. If I remember correctly, Kaplan and  
> Tarjan use
> the term purely functional to exclude lazy in one of their papers, and  
> just
> allow primitive list ops like car/cdr/cons etc.

They do.  Mine would be purely functional if it didn't have to support  
concatenation.  And it does not suffer from the limitations of the  
implementation Mr. Hurt is talking about in the recent addition to  
Extlib.

I would expect to pay a small price for the persistence.  With the  
imperative double-link list, the insert operation costs one allocation,  
a reference copy and the update to the links.  With my functional  
deque, the insert operation costs at least one allocation, possibly as  
many, in the worst-case, as 2/3 log[2] N allocations (where N is the  
number of elements in the deque), and the link update overhead.  The  
cost of all the other operations is similar in complexity.

Here is the module interface file...

(*---------------------------------------------------------------------- 
-----*
   INTERFACE  cf_deque.mli

   Copyright (c) 2003-2004, James H. Woodyatt
   All rights reserved.

   Redistribution and use in source and binary forms, with or without
   modification, are permitted provided that the following conditions
   are met:

     Redistributions of source code must retain the above copyright
     notice, this list of conditions and the following disclaimer.

     Redistributions in binary form must reproduce the above copyright
     notice, this list of conditions and the following disclaimer in
     the documentation and/or other materials provided with the
     distribution

   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
   FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
   COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
   INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
   (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
   SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
   STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
   ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
   OF THE POSSIBILITY OF SUCH DAMAGE.
   
*----------------------------------------------------------------------- 
----*)

(** A functional persistent double-ended catenable deque, with O{_  
avg}(1) cost
     for every operation.  Internally, this is a recursive data  
structure with
     height O(log N).
*)

(** The abstract type of a deque. *)
type +'a t

(** The empty deque. *)
val nil: 'a t

(** Returns [true] if the deque is the empty deque. *)
val empty: 'a t -> bool

(** Functions for operations on one of the two ends of a deque. *)
module type Direction_T = sig

     (** [push x d] adds the element [x] to the end of the deque [d].   
The
         average cost is constant.  Worst-case running time is O(log N),  
which
         happens once in every N operations.  Not tail-recursive.
     *)
     val push: 'a -> 'a t -> 'a t

     (** [pop d] returns [None] if [d] is the empty deque, otherwise it  
returns
         [Some (x, d')] where [x] is the element on the end of the  
deque, and
         [d'] is the remainder of [d] with the element [x] removed.  The  
average
         cost is constant.  Worst-case running time is O(log N), which  
happens
         once in every N operations.  Not tail-recursive.
     *)
     val pop: 'a t -> ('a * 'a t) option

     (** [head d] returns the element at the end of the deque [d].   
Raises
         [Not_found] if the deque is empty.  Not tail-recursive.
     *)
     val head: 'a t -> 'a

     (** [tail d] is discards the element at the end of the deque [d].   
Raises
         [Not_found] if the deque is empty.  Not tail-recursive.
     *)
     val tail: 'a t -> 'a t

     (** [to_seq d] returns a lazily evaluated sequence of the elements  
in the
         deque in the order they would appear by successive calls of  
[pop d].
     *)
     val to_seq: 'a t -> 'a Cf_seq.t

     (** [to_seq2 d] returns a lazily evaluated sequence of the pairs  
[(hd, tl)]
         obtained by successively calling of [pop d].
     *)
     val to_seq2: 'a t -> ('a * 'a t) Cf_seq.t
end

module A: Direction_T  (** Operations on the left end of a deque. *)
module B: Direction_T  (** Operations on the right end of a deque. *)

(** [iterate f d] applies [f] to every element in [d] in left-to-right
     order.  Not tail recursive.
*)
val iterate: ('a -> unit) -> 'a t -> unit

(** [predicate f d] returns [true] if the result of applying [f] to  
every
     element in the deque [d] is [true], or if [d] is the empty deque.   
The
     order in which elements are applied is left to right.  If [f]  
returns
     [false], then no more elements from [d] will be applied and the  
result
     will be returned immediately.  Not tail recursive.
*)
val predicate: ('a -> bool) -> 'a t -> bool

(** [fold f a0 d] is [f (... (f (f a0 e0) e1) ...) en] when [e0..en]  
are the
     elements of the deque [d] in left-to-right order.  Not tail  
recursive.
*)
val fold: ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b

(** [filter f d] returns a new deque composed by applying [f] to every  
element
     in [d], including only those elements for which the result is  
[true].  The
     function is applied to the elements in the deque in left-to-right  
order.
     Not tail recursive.
*)
val filter: ('a -> bool) -> 'a t -> 'a t

(** [map f d] returns a new deque composed by applying [f] to every  
element in
     [d] in left-to-right order.  Not tail recursive.
*)
val map: ('a -> 'b) -> 'a t -> 'b t

(** [optmap f d] returns a new deque composed by applying [f] to every  
element
     in [d] in left-to-right order, including only those elements of [d]
     for which [f] returns [Some] value.  Not tail recursive.
*)
val optmap: ('a -> 'b option) -> 'a t -> 'b t

(** [listmap f d] returns a new deque composed by applying [f] to every  
element
     in [d] in left-to-right order, taking all the resulting lists of
     elements in order.  Not tail recursive.
*)
val listmap: ('a -> 'b list) -> 'a t -> 'b t

(** [seqmap f d] returns a new deque composed by applying [f] to every  
element
     in [d] in left-to-right order, taking all the resulting sequences of
     elements in order.  Not tail recursive.
*)
val seqmap: ('a -> 'b Cf_seq.t) -> 'a t -> 'b t

(** [partition f s] returns two deques.  The first is the deque of
     elements in [d] for which applying [f] results in [true], and the  
second
     is the deque of elements for which applying [f] results in [false].  
  The
     elements are applied in left-to-right order.
*)
val partition: ('a -> bool) -> 'a t -> 'a t * 'a t

(** [length d] computes the number elements contained in the deque [d].  
  Not
     tail recursive.
*)
val length: 'a t -> int

(** [catenate d1 d2] returns a new deque composed by joining the right  
end of
     [d1] to the left end of [d2].  The average cost is constant.  Not
     tail-recursive.
*)
val catenate: 'a t -> 'a t -> 'a t

(*--- End of File [ cf_deque.mli ] ---*)

NOTE: it turns out that I will be changing the module in the next  
release, specifically to make the utility functions [iterate,  
predicate, filter, map, fold, etc.] apply their iterative function in  
left-to-right order, rather than an indeterminate order.  The  
right-to-left order will require converting the deque to a sequence and  
using the [Cf_seq] function of the same name.


-- 
j h woodyatt <jhw@wetware.com>
markets are only free to the people who own them.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[Alex Baretta]

Jon Harrop wrote:
> On Thursday 29 July 2004 23:42, you wrote:
> 
>>...I won't by
>>imperative programming for anything at all...
> 
> 
> What would you do if you wanted a data structure with O(1) lookup?

Such structures do not exists. Remember that complexity theory deals 
with *unbounded* input sizes. As you can well imagine, there exists no 
such thing as an indefinitely large datastructure with O(1) time 
complexity. Arrays are O(1) only if you preallocate them to the maximum 
size allowed by the application. But, in this case, even a binary search 
in Map.t is O(1): that is, bounded by a constant.

Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] looping recursion

[brogoff]

On Fri, 30 Jul 2004, Alex Baretta wrote:
> brogoff wrote:
> > On Thu, 29 Jul 2004, Alex Baretta wrote:
> >
> >>brogoff wrote:
> >
> > Some problems are just way easier to solve with imperative programming
> > though. Have you ever taken a look at purely functional catenable deques?
> > If you don't need persistence (if your deques are used in a single threaded
> > manner that is) would you use those instead of the obvious doubly linked
> > list implementation? That's not an abstract question either, catenable deques
> > come up quite naturally when implementing some 2D computational geometry
> > algorithms.I took a look at the latest algorithm by Kaplan and Tarjan and
> > quickly realized that it was hugely complicated if persistence is not needed.
> s list: http://groups.yahoo.com/group/ocaml_beginners
> >
>
> I didn't understand the connection between multithreading and
> persistence, but it's probably too late and I've been working far too
> much to follow you entirely.

I'm not using the terminology with regard to concurrent programming, but simply
saying only I don't need persistence. Maybe I picked up the terminology from
some discussion about versioned arrays (implementing functional arrays on top of
imperative ones) or from Clean.

> Let me just give you a couple eurocents of industrial experience: side-effects
> are utterly bad.

My two U.S. cents of industrial experience is that statement is utterly false.
Side effects are to be controlled and dealt with, but they are unavoidable.
But I don't feel like having a flamewar about it, no doubt we've all seen the
arguments and no one will offer anything new...

> My Xcaml
> application server was designed two years ago with one major flaw: one
> global state variable.

Sure, Dante's lowest level of Hell is reserved for those who abuse global state.

Ever look at the purely functional red black tree implementation in the SML/NJ
utils library? Last time I looked, the author used a local reference to store
some state in one of the calculation, rather than adding an argument to a bunch
of nested functions. Still purely functional to the observer though. What level
of Hell should he go to?

> I'm still fighting with the execution engine to
> take it away, but that won't happen before a major rewrite. I won't by
> imperative programming for anything at all.

Even monadic IO strikes me as imperative, so if you have IO, there's really no
way to avoid it.

> And, yes, in my company the
> mandated standard for deques is batched queues à la Okasaki.

I think of the respondents to my point about catenable deques, only James
Woodyatt seems to get what I mean. And given the fact that persistence is
not necessary in my application, I am willing to exercise extra care to get
that annoying imperative code right.

I would like to see an implementation of the catenable deques only
using simple list ops (not laziness) described by Kaplan and Tarjan,
in OCaml. If I remember, the algorithm was described using nonuniform
data types, so that's yet another plug for supporting this more directly in
OCaml, meaning, without having to use recursive modules, record field
polymorphism, or polymorphic records to work around the ability to
directly write such functions.

-- Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] kaplan-okasaki-tarjan deque (was "looping recursion")

[james woodyatt]

[-- Attachment #1: Type: text/plain, Size: 274 bytes --]

On 30 Jul 2004, at 10:07, brogoff wrote:
>
> I would like to see an implementation of the catenable deques only
> using simple list ops (not laziness) described by Kaplan and Tarjan,
> in OCaml.

Sure.  Here is the basic implementation I did for performance 
comparisons.

	

[-- Attachment #2: cf_kotdeque.ml --]
[-- Type: application/octet-stream, Size: 18773 bytes --]

(*---------------------------------------------------------------------------*
  IMPLEMENTATION  cf_kotdeque.ml

  Copyright (c) 2003, James H. Woodyatt
  All rights reserved.

  Redistribution and use in source and binary forms, with or without
  modification, are permitted provided that the following conditions
  are met:

    Redistributions of source code must retain the above copyright
    notice, this list of conditions and the following disclaimer.

    Redistributions in binary form must reproduce the above copyright
    notice, this list of conditions and the following disclaimer in
    the documentation and/or other materials provided with the
    distribution

  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
  INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  OF THE POSSIBILITY OF SUCH DAMAGE. 
 *---------------------------------------------------------------------------*)

type 'a buffer =
    | B1 of 'a
    | B2 of 'a * 'a
    | B3 of 'a * 'a * 'a
    | B4 of 'a * 'a * 'a * 'a
    | B5 of 'a * 'a * 'a * 'a * 'a
    | B6 of 'a * 'a * 'a * 'a * 'a * 'a
    | B7 of 'a * 'a * 'a * 'a * 'a * 'a * 'a
    | B8 of 'a * 'a * 'a * 'a * 'a * 'a * 'a * 'a

let pushBufferL x = function
    | B1 a -> B2 (x,a)
    | B2 (a,b) -> B3 (x,a,b)
    | B3 (a,b,c) -> B4 (x,a,b,c)
    | B4 (a,b,c,d) -> B5 (x,a,b,c,d)
    | B5 (a,b,c,d,e) -> B6 (x,a,b,c,d,e)
    | B6 (a,b,c,d,e,f) -> B7 (x,a,b,c,d,e,f)
    | B7 (a,b,c,d,e,f,g) -> B8 (x,a,b,c,d,e,f,g)
    | B8 _ as y -> assert (not true); y

let pushBufferR x = function
    | B1 a -> B2 (a,x)
    | B2 (a,b) -> B3 (a,b,x)
    | B3 (a,b,c) -> B4 (a,b,c,x)
    | B4 (a,b,c,d) -> B5 (a,b,c,d,x)
    | B5 (a,b,c,d,e) -> B6 (a,b,c,d,e,x)
    | B6 (a,b,c,d,e,f) -> B7 (a,b,c,d,e,f,x)
    | B7 (a,b,c,d,e,f,g) -> B8 (a,b,c,d,e,f,g,x)
    | B8 _ as y -> assert (not true); y

let popBufferL = function
    | B1 _ -> assert false
    | B2 (x,a) -> x, B1 a
    | B3 (x,a,b) -> x, B2 (a,b)
    | B4 (x,a,b,c) -> x, B3 (a,b,c)
    | B5 (x,a,b,c,d) -> x, B4 (a,b,c,d)
    | B6 (x,a,b,c,d,e) -> x, B5 (a,b,c,d,e)
    | B7 (x,a,b,c,d,e,f) -> x, B6 (a,b,c,d,e,f)
    | B8 (x,a,b,c,d,e,f,g) -> x, B7 (a,b,c,d,e,f,g)

let popBufferR = function
    | B1 _ -> assert false
    | B2 (a,x) -> x, B1 a
    | B3 (a,b,x) -> x, B2 (a,b)
    | B4 (a,b,c,x) -> x, B3 (a,b,c)
    | B5 (a,b,c,d,x) -> x, B4 (a,b,c,d)
    | B6 (a,b,c,d,e,x) -> x, B5 (a,b,c,d,e)
    | B7 (a,b,c,d,e,f,x) -> x, B6 (a,b,c,d,e,f)
    | B8 (a,b,c,d,e,f,g,x) -> x, B7 (a,b,c,d,e,f,g)

type 'a t =
    | Z
    | Y of 'a buffer
    | U of 'a buffer * 'a triple t * ('a * 'a) * 'a triple t * 'a buffer
and 'a triple =
    | T1 of 'a buffer
    | T2 of 'a buffer * 'a buffer
    | T3 of 'a buffer * 'a triple t * 'a buffer        

let popLeftNaive = function
    | Z ->
        assert false
    | Y (B1 x) ->
        x, Z
    | Y b ->
        let x, b = popBufferL b in x, Y b
    | U (pr, ld, mid, rd, sf) ->
        let x, pr = popBufferL pr in x, U (pr, ld, mid, rd, sf)

let popRightNaive = function
    | Z ->
        assert false
    | Y (B1 x) ->
        x, Z
    | Y b ->
        let x, b = popBufferR b in x, Y b
    | U (pr, ld, mid, rd, sf) ->
        let x, sf = popBufferR sf in x, U (pr, ld, mid, rd, sf)
           
let rec pushLeft x = function
    | Z ->
        Y (B1 x)
    | Y (B8 (a,b,c,d,e,f,g,h)) ->
        U (B4 (x,a,b,c), Z, (d,e), Z, B3 (f,g,h))
    | Y b ->
        Y (pushBufferL x b)
    | U (pr, ld, mid, rd, sf) as d ->
        match pr with
        | B6 _ ->
            let pr, ld, mid, rd, sf = greenLeft pr ld mid rd sf in
            U (pushBufferL x pr, ld, mid, rd, sf)
        | _ -> 
            U (pushBufferL x pr, ld, mid, rd, sf)

and pushRight x = function
    | Z ->
        Y (B1 x)
    | Y (B8 (a,b,c,d,e,f,g,h)) ->
        U (B3 (a,b,c), Z, (d,e), Z, B4 (f,g,h,x))
    | Y b ->
        Y (pushBufferR x b)
    | U (pr, ld, mid, rd, sf) as d ->
        match sf with
        | B6 _ ->
            let pr, ld, mid, rd, sf = greenRight pr ld mid rd sf in
            U (pr, ld, mid, rd, pushBufferR x sf)
        | _ -> 
            U (pr, ld, mid, rd, pushBufferR x sf)

and greenLeft pr ld mid rd sf =
    match pr with
    | B6 (e1,e2,e3,e4,e5,e6) ->
        let ld = (Obj.magic pushLeft) (T1 (B2 (e5,e6))) ld in
        B4 (e1,e2,e3,e4), ld, mid, rd, sf
    | B3 _ ->
        begin
            match ld, rd with
            | Y _, _
            | U _, _ ->
                let t, l =
                    let t, _ = popLeftNaive ld in
                    match t with
                    | T1 (B3 _)
                    | T2 (B3 _, _)
                    | T3 _ ->
                        popLeftNaive ld
                    | _ ->
                        match (Obj.magic popLeft) ld with
                        | Some (x,y) -> x, y
                        | None -> assert false
                in
                let (T1 x | T2 (x,_) | T3 (x,_,_)) = t in begin
                    match x with
                    | B3 (e1,e2,e3) ->
                        let p = pushBufferR e1 pr in
                        let x' = B2 (e2,e3) in
                        let l0 =
                            match t with
                            | T3 (_, d', y) -> T3 (x', d', y)
                            | T2 (_, y) -> T2 (x', y)
                            | T1 _ -> T1 x'
                        in
                        let ld = (Obj.magic pushLeft) l0 l in
                        p, ld, mid, rd, sf
                    | B2 (e1,e2) ->
                        let p = pushBufferR e2 (pushBufferR e1 pr) in
                        let l' =
                            match t with
                            | T3 (_, d', y) ->
                                let l = (Obj.magic pushLeft) (T1 y) l in
                                (Obj.magic catenate) d' l
                            | T1 _ ->
                                l
                            | _ ->
                                assert false
                        in
                        p, l', mid, rd, sf
                    | _ ->
                        assert false
                end
            | Z, Y _
            | Z, U _ ->
                let t, r =
                    let t, _ = popLeftNaive rd in
                    match t with
                    | T1 (B3 _)
                    | T2 (B3 _, _)
                    | T3 _ ->
                        popLeftNaive rd
                    | _ ->
                        match (Obj.magic popLeft) rd with
                        | Some (x,y) -> x, y
                        | None -> assert false
                in
                let m1, m2 = mid in
                let (T1 x | T2 (x,_) | T3 (x,_,_)) = t in begin
                    match x with
                    | B3 (e1,e2,e3) ->
                        let p = pushBufferR m1 pr in
                        let mid = m2, e1 in
                        let x' = B2 (e2,e3) in
                        let r0 =
                            match t with
                            | T3 (_, d', y) -> T3 (x', d', y)
                            | T2 (_, y) -> T2 (x', y)
                            | T1 _ -> T1 x'
                        in
                        let rd = (Obj.magic pushLeft) r0 r in
                        p, ld, mid, rd, sf
                    | B2 (e1,e2) ->
                        let p = pushBufferR m2 (pushBufferR m1 pr) in
                        let mid = e1, e2 in
                        let r' =
                            match t with
                            | T3 (_, d', y) ->
                                let r = (Obj.magic pushLeft) (T1 y) r in
                                (Obj.magic catenate) d' r
                            | T1 _ ->
                                r
                            | _ ->
                                assert false
                        in
                        p, Z, mid, r', sf
                    | _ ->
                        assert false
                end
            | _ ->
                assert false
        end
    | _ ->
        assert false

and greenRight pr ld mid rd sf =
    match sf with
    | B6 (e6,e5,e4,e3,e2,e1) ->
        let rd = (Obj.magic pushRight) (T1 (B2 (e6,e5))) rd in
        pr, ld, mid, rd, B4 (e4,e3,e2,e1)
    | B3 _ ->
        begin
            match ld, rd with
            | _, Y _
            | _, U _ ->
                let t, r =
                    let t, _ = popRightNaive rd in
                    match t with
                    | T1 (B3 _)
                    | T2 (_, B3 _)
                    | T3 _ ->
                        popRightNaive rd
                    | _ ->
                        match (Obj.magic popRight) rd with
                        | Some (x,y) -> x, y
                        | None -> assert false
                in
                let (T1 x | T2 (_,x) | T3 (_,_,x)) = t in begin
                    match x with
                    | B3 (e3,e2,e1) ->
                        let p = pushBufferL e1 sf in
                        let x' = B2 (e3,e2) in
                        let r0 =
                            match t with
                            | T3 (y, d', _) -> T3 (y, d', x')
                            | T2 (y, _) -> T2 (y, x')
                            | T1 _ -> T1 x'
                        in
                        let rd = (Obj.magic pushRight) r0 r in
                        pr, ld, mid, rd, p
                    | B2 (e2,e1) ->
                        let p = pushBufferL e2 (pushBufferL e1 sf) in
                        let r' =
                            match t with
                            | T3 (y, d', _) ->
                                let r = (Obj.magic pushRight) (T1 y) r in
                                (Obj.magic catenate) r d'
                            | T1 _ ->
                                r
                            | _ ->
                                assert false
                        in
                        pr, ld, mid, r', p
                    | _ ->
                        assert false
                end
            | Y _, Z
            | U _, Z ->
                let t, l =
                    let t, _ = popRightNaive ld in
                    match t with
                    | T1 (B3 _)
                    | T2 (_, B3 _)
                    | T3 _ ->
                        popRightNaive ld
                    | _ ->
                        match (Obj.magic popRight) ld with
                        | Some (x,y) -> x, y
                        | None -> assert false
                in
                let m2, m1 = mid in
                let (T1 x | T2 (_,x) | T3 (_,_,x)) = t in begin
                    match x with
                    | B3 (e3,e2,e1) ->
                        let p = pushBufferL m1 sf in
                        let mid = e1, m2 in
                        let x' = B2 (e3,e2) in
                        let l0 =
                            match t with
                            | T3 (y, d', _) -> T3 (y, d', x')
                            | T2 (y, _) -> T2 (y, x')
                            | T1 _ -> T1 x'
                        in
                        let ld = (Obj.magic pushRight) l0 l in
                        pr, ld, mid, rd, p
                    | B2 (e2,e1) ->
                        let p = pushBufferL m2 (pushBufferL m1 sf) in
                        let mid = e2, e1 in
                        let l' =
                            match t with
                            | T3 (y, d', _) ->
                                let l = (Obj.magic pushRight) (T1 y) l in
                                (Obj.magic catenate) l d'
                            | T1 _ ->
                                l
                            | _ ->
                                assert false
                        in
                        pr, l', mid, Z, p
                    | _ ->
                        assert false
                end
            | _ ->
                assert false
        end
    | _ ->
        assert false

and popLeft = function
    | Z ->
        None
    | Y (B1 x) ->
        Some (x, Z)
    | Y b ->
        let x, b = popBufferL b in
        Some (x, Y b)
    | U ((B4 _ | B5 _ | B6 _ as pr), ld, mid, rd, sf) ->
        let x, pr = popBufferL pr in
        Some (x, U (pr, ld, mid, rd, sf))
    | U ((B3 (x,e1,e2) as pr), Z, (m1,m2), Z, sf) ->
        let y =
            match sf with
            | B3 (f1,f2,f3) ->
                Y (B7 (e1,e2,m1,m2,f1,f2,f3))
            | _ ->
                let f', sf = popBufferL sf in
                U (B3 (e1,e2,m1), Z, (m2,f'), Z, sf)
        in
        Some (x, y)
    | U ((B3 _ as pr), ld, mid, rd, sf) ->
        let pr, ld, mid, rd, sf = greenLeft pr ld mid rd sf in
        Some (popLeftNaive (U (pr, ld, mid, rd, sf)))
    | _ ->
        assert false

and popRight = function
    | Z ->
        None
    | Y (B1 x) ->
        Some (x, Z)
    | Y b ->
        let x, b = popBufferR b in
        Some (x, Y b)
    | U (pr, ld, mid, rd, (B4 _ | B5 _ | B6 _ as sf)) ->
        let x, sf = popBufferR sf in
        Some (x, U (pr, ld, mid, rd, sf))
    | U (pr, Z, (m2,m1), Z, (B3 (e2,e1,x) as sf)) ->
        let y =
            match pr with
            | B3 (p3,p2,p1) ->
                Y (B7 (p3,p2,p1,m2,m1,e2,e1))
            | _ ->
                let f', pr = popBufferR pr in
                U (pr, Z, (f',m2), Z, B3 (m1,e2,e1))
        in
        Some (x, y)
    | U (pr, ld, mid, rd, (B3 _ as sf)) ->
        let pr, ld, mid, rd, sf = greenRight pr ld mid rd sf in
        Some (popRightNaive (U (pr, ld, mid, rd, sf)))
    | _ ->
        assert false

and catenate d1 d2 =
    match d1, d2 with
    | Z, _ ->
        d2
    | _, Z ->
        d1
    | Y b, _ ->
        begin
            match b with
            | B1 x -> pushLeft x d2
            | _ -> let x, b = popBufferR b in catenate (Y b) (pushLeft x d2)
        end
    | _, Y b ->
        begin
            match b with
            | B1 x -> pushRight x d1
            | _ -> let x, b = popBufferL b in catenate (pushRight x d1) (Y b)
        end
    | U (pr1, ld1, mid1, rd1, sf1), U (pr2, ld2, mid2, rd2, sf2) ->
        let y, pr2 = popBufferL pr2 and x, sf1 = popBufferR sf1 in
        let mid = x, y in
        let ld =
            let m1,m2 = mid1 in
            let pRight = Obj.magic pushRight in
            match sf1 with
            | B2 _
            | B3 _ ->
                pRight (T3 (B2 (m1,m2), rd1, sf1)) ld1
            | B4 (e1,e2,e3,e4) ->
                let ld'1 = pRight (T3 (B2 (m1,m2), rd1, B2 (e1,e2))) ld1 in
                pRight (T1 (B2 (e3,e4))) ld'1
            | B5 (e1,e2,e3,e4,e5) ->
                let s'1 = B3 (e1,e2,e3) in
                let ld'1 = pRight (T3 (B2 (m1,m2), rd1, s'1)) ld1 in
                pRight (T1 (B2 (e4,e5))) ld'1
            | _ ->
                assert false
        in
        let rd =
            let m2,m1 = mid2 in
            let pLeft = Obj.magic pushLeft in
            match pr2 with
            | B2 _
            | B3 _ ->
                pLeft (T3 (pr2, ld2, B2 (m2,m1))) rd2
            | B4 (e4,e3,e2,e1) ->
                let rd'1 = pLeft (T3 (B2 (e2,e1), ld2, B2 (m2,m1))) rd2 in
                pLeft (T1 (B2 (e4,e3))) rd'1
            | B5 (e5,e4,e3,e2,e1) ->
                let s'1 = B3 (e3,e2,e1) in
                let rd'1 = pLeft (T3 (s'1, ld2, B2 (m2,m1))) rd2 in
                pLeft (T1 (B2 (e5,e4))) rd'1
            | _ ->
                assert false
        in
        U (pr1, ld, mid, rd, sf2)

let nil = Z

module type Direction_T = sig
    val push: 'a -> 'a t -> 'a t
    val pop: 'a t -> ('a * 'a t) option
end

module A = struct
    let push = pushLeft
    let pop = popLeft
end

module B = struct
    let push = pushRight
    let pop = popRight
end

let sprintB ff = function
    | B1 a ->
        let a = ff a in
        Printf.sprintf "%s" a
    | B2 (a,b) ->
        let a = ff a in
        let b = ff b in
        Printf.sprintf "%s,%s" a b
    | B3 (a,b,c) ->
        let a = ff a in
        let b = ff b in
        let c = ff c in
        Printf.sprintf "%s,%s,%s" a b c
    | B4 (a,b,c,d) ->
        let a = ff a in
        let b = ff b in
        let c = ff c in
        let d = ff d in
        Printf.sprintf "%s,%s,%s,%s" a b c d
    | B5 (a,b,c,d,e) ->
        let a = ff a in
        let b = ff b in
        let c = ff c in
        let d = ff d in
        let e = ff e in
        Printf.sprintf "%s,%s,%s,%s,%s" a b c d e
    | B6 (a,b,c,d,e,f) ->
        let a = ff a in
        let b = ff b in
        let c = ff c in
        let d = ff d in
        let e = ff e in
        let f = ff f in
        Printf.sprintf "%s,%s,%s,%s,%s,%s" a b c d e f
    | B7 (a,b,c,d,e,f,g) ->
        let a = ff a in
        let b = ff b in
        let c = ff c in
        let d = ff d in
        let e = ff e in
        let f = ff f in
        let g = ff g in
        Printf.sprintf "%s,%s,%s,%s,%s,%s,%s" a b c d e f g 
    | B8 (a,b,c,d,e,f,g,h) ->
        let a = ff a in
        let b = ff b in
        let c = ff c in
        let d = ff d in
        let e = ff e in
        let f = ff f in
        let g = ff g in
        let h = ff h in
        Printf.sprintf "%s,%s,%s,%s,%s,%s,%s,%s" a b c d e f g h

let rec sprint f = function
    | Z ->
        "{}"
    | Y b ->
        Printf.sprintf "{%s}" (sprintB f b)
    | U (pr, ld, (m1,m2), rd, sf) ->
        let g = sprintT f in
        let pr = sprintB f pr in
        let ld = (Obj.magic sprint) g ld in
        let mid = sprintB f (B2 (m1,m2)) in
        let rd = (Obj.magic sprint) g rd in
        let sf = sprintB f sf in
        Printf.sprintf "{%s;%s;%s;%s;%s}" pr ld mid rd sf

and sprintT f = function
    | T1 b -> Printf.sprintf "<%s>" (sprintB f b)
    | T2 (b1,b2) -> Printf.sprintf "(%s/%s)" (sprintB f b1) (sprintB f b2)
    | T3 (b1,q,b2) ->
        let b1 = sprintB f b1 in
        let q = (Obj.magic sprint) (fun x -> sprintT f x) q in
        let b2 = sprintB f b2 in
        Printf.sprintf "[%s|%s|%s]" b1 q b2

(*--- End of File [ cf_kotdeque.ml ] ---*)

[-- Attachment #3: cf_kotdeque.mli --]
[-- Type: application/octet-stream, Size: 1845 bytes --]

(*---------------------------------------------------------------------------*
  INTERFACE  cf_kotdeque.mli

  Copyright (c) 2003, James H. Woodyatt
  All rights reserved.

  Redistribution and use in source and binary forms, with or without
  modification, are permitted provided that the following conditions
  are met:

    Redistributions of source code must retain the above copyright
    notice, this list of conditions and the following disclaimer.

    Redistributions in binary form must reproduce the above copyright
    notice, this list of conditions and the following disclaimer in
    the documentation and/or other materials provided with the
    distribution

  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
  INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  OF THE POSSIBILITY OF SUCH DAMAGE. 
 *---------------------------------------------------------------------------*)

type 'a t

val nil: 'a t

module type Direction_T = sig
    val push: 'a -> 'a t -> 'a t
    val pop: 'a t -> ('a * 'a t) option
end

module A: Direction_T
module B: Direction_T

val catenate: 'a t -> 'a t -> 'a t
val sprint: ('a -> string) -> 'a t -> string

(*--- End of File [ cf_kotdeque.mli ] ---*)

[-- Attachment #4: Type: text/plain, Size: 1593 bytes --]



> If I remember, the algorithm was described using nonuniform
> data types, so that's yet another plug for supporting this more 
> directly in
> OCaml, meaning, without having to use recursive modules, record field
> polymorphism, or polymorphic records to work around the ability to
> directly write such functions.

The structure uses "bootstrapping" and so does my [Cf_deque] structure. 
  I have handled bootstrapping in [Cf] with judicious use of [Obj.magic] 
to cast functions into the appropriate type at the recursion.

Note: My [Cf] library is loaded with calls to [Obj.magic].  There are 
lots of places where the only way I could solve a problem was by 
hammering something deeply weird into a shape that would fit into the 
Ocaml type system.   Mostly, that happens where I have an interface to 
C library stuff and I'm using shadow type annotations.  But the 
bootstrapped data structures are another place.  And the [Cf_gadget] 
module needs to do something similar (which was well known in the 
original Haskell code where that idea started).

Every time the Ocaml team updates the compiler, I'm worried they're 
going to change something that invalidates my assumptions about what 
[Obj.magic] can and cannot do for me.  I'm *not* saying they didn't 
warn me.  I knew the job was dangerous.

I'd be more exercised about the 'looping recursion' problem with 
List.map exploding on large data sets if I were not in the habit of 
using my [Cf] structures to avoid all that.


-- 
j h woodyatt <jhw@wetware.com>
that's my village calling... no doubt, they want their idiot back.

Re: [Caml-list] kaplan-okasaki-tarjan deque (was "looping recursion")

[brogoff]

On Fri, 30 Jul 2004, james woodyatt wrote:
> On 30 Jul 2004, at 10:07, brogoff wrote:
> >
> > I would like to see an implementation of the catenable deques only
> > using simple list ops (not laziness) described by Kaplan and Tarjan,
> > in OCaml.
>
> Sure.  Here is the basic implementation I did for performance
> comparisons.

Thanks. I emailed you back a version with the magic gone, using the recursive
module extension to bulldozer over your abuse of the type system ;-). It's the
least offensive (IMO of course) of the current workarounds. I wonder if the
implementors can tell us if there is any hope that we'll see some better
solutions in the near future?

BTW, what did your comparisons tell you?

-- Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] kaplan-okasaki-tarjan deque (was "looping recursion")

[james woodyatt]

On 30 Jul 2004, at 14:20, brogoff wrote:
>
> BTW, what did your comparisons tell you?

It told me that my implementation was enough faster that it was worth 
the price of having to convert between deques and lists in order to 
marshall them to disk or on the wire, with noticeable savings even 
after that.  I can't remember the numbers right now.

At one time, I thought it would be worth the effort of writing an 
academic paper on the subject, but I never learned how to write an 
academic paper so it will get published.  So I haven't tried.  Sigh.

One of the questions that remains unanswered is how much time my 
implementation of Kaplan-Okasaki-Tarjan wastes being inefficient about 
handling the fixed size buffers.  My gut tells me there's room for 
improvement there, but not enough to overcome the advantage my 
implementation has over it.  I need to measure that.


― ∴

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners