* [Caml-list] Why is (@) written in O'Caml?
@ 2002-12-05 20:47 Oleg
2002-12-05 21:16 ` Pal-Kristian Engstad
0 siblings, 1 reply; 6+ messages in thread
From: Oleg @ 2002-12-05 20:47 UTC (permalink / raw)
To: caml-list
let rec (@) l1 l2 =
match l1 with
[] -> l2
| hd :: tl -> hd :: (tl @ l2)
The O'Caml implementation of (@) is recursive and not tail-recursive. All one
really has to do during "append" is copy l1 and set the last element's CDR to
l2. I can see why this can not be done in O'Caml itself, but since (@) is
such a common operation, I'm wondering why it was decided to implement it
inefficently in O'Caml itself?
Cheers,
Oleg
-------------------
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
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] Why is (@) written in O'Caml?
2002-12-05 20:47 [Caml-list] Why is (@) written in O'Caml? Oleg
@ 2002-12-05 21:16 ` Pal-Kristian Engstad
2002-12-05 21:24 ` Oleg
0 siblings, 1 reply; 6+ messages in thread
From: Pal-Kristian Engstad @ 2002-12-05 21:16 UTC (permalink / raw)
To: Oleg, caml-list
On Thursday 05 December 2002 12:47 pm, Oleg wrote:
> let rec (@) l1 l2 =
> match l1 with
> [] -> l2
>
> | hd :: tl -> hd :: (tl @ l2)
>
> The O'Caml implementation of (@) is recursive and not tail-recursive. All
> one really has to do during "append" is copy l1 and set the last element's
> CDR to l2. I can see why this can not be done in O'Caml itself, but since
> (@) is such a common operation, I'm wondering why it was decided to
> implement it inefficently in O'Caml itself?
You say you want to copy l1 and then set the last element of tail to l2? But,
that is _exactly_ what the function above does!
let copy l1 =
match l1 with
[] -> []
| hd :: tl -> hd :: copy tl
Right? So, the only change is the extra argument l2, that is being appended
onto the list when l1 is empty.
PKE.
--
_
\`. Pål-Kristian Engstad, Senior Software Engineer,
\ `| Naughty Dog, Inc., 1315 3rd Street Promenade,
__\ |`. Santa Monica, CA 90046, USA. (310) 752-1000 x799.
/ /o mailto:engstad@naughtydog.com http://www.naughtydog.com
/ '~ mailto:mrengstad@yahoo.com http://www.engstad.com
/ ,' Hang-gliding Rulez!
~'
-------------------
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
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] Why is (@) written in O'Caml?
2002-12-05 21:16 ` Pal-Kristian Engstad
@ 2002-12-05 21:24 ` Oleg
2002-12-05 21:55 ` Pal-Kristian Engstad
0 siblings, 1 reply; 6+ messages in thread
From: Oleg @ 2002-12-05 21:24 UTC (permalink / raw)
To: Pal-Kristian Engstad, caml-list
On Thursday 05 December 2002 04:16 pm, Pal-Kristian Engstad wrote:
> But, that is _exactly_ what the function above does!
It's not about *what* it does, but *how* (@) does it. (@) is recursive and not
tail-recursive.
Oleg
-------------------
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
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] Why is (@) written in O'Caml?
2002-12-05 21:24 ` Oleg
@ 2002-12-05 21:55 ` Pal-Kristian Engstad
2002-12-05 23:27 ` Oleg
0 siblings, 1 reply; 6+ messages in thread
From: Pal-Kristian Engstad @ 2002-12-05 21:55 UTC (permalink / raw)
To: Oleg, Pal-Kristian Engstad, caml-list
On Thursday 05 December 2002 01:24 pm, Oleg wrote:
> On Thursday 05 December 2002 04:16 pm, Pal-Kristian Engstad wrote:
> > But, that is _exactly_ what the function above does!
>
> It's not about *what* it does, but *how* (@) does it. (@) is recursive and
> not tail-recursive.
Okey - I see where you're coming from. Since we know that we're creating a new
copy of a list, we know there will be references to it elsewhere, hence we
may see it as a mutable list and do something like:
struct cell { value *hd; cell* tl; };
newlist = nil;
prev = nil;
list = l1;
/* copy l1 */
while (list != nil) {
pnew = alloc(list); /* Allocate new cell. */
if (!newlist) newlist = pnew; /* Mark first cell. */
pnew->hd = list->hd; /* Copy data at cell. */
pnew->tl = nil; /* Init to nil. */
if (prev) prev->tl = pnew; /* Link previous cell to this. */
prev = pnew; /* Update previous. */
list = list->tl; /* Get next l1 cell. */
}
if (prev) {
prev->tl = l2;
return newlist;
}
else {
return l2;
}
Is that what you mean?
PKE.
-------------------
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
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] Why is (@) written in O'Caml?
2002-12-05 21:55 ` Pal-Kristian Engstad
@ 2002-12-05 23:27 ` Oleg
2002-12-05 23:53 ` Pal-Kristian Engstad
0 siblings, 1 reply; 6+ messages in thread
From: Oleg @ 2002-12-05 23:27 UTC (permalink / raw)
To: Pal-Kristian Engstad, caml-list; +Cc: Pal-Kristian Engstad
On Thursday 05 December 2002 04:55 pm, Pal-Kristian Engstad wrote:
> Okey - I see where you're coming from. Since we know that we're creating a
> new copy of a list, we know there will be references to it elsewhere, hence
> we may see it as a mutable list
s/be/be not/
[...]
> Is that what you mean?
Yes
Oleg
P.S. I tried replying off the list (where "what do you mean" questions usually
belong), but your mail server is refusing access.
-------------------
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
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] Why is (@) written in O'Caml?
2002-12-05 23:27 ` Oleg
@ 2002-12-05 23:53 ` Pal-Kristian Engstad
0 siblings, 0 replies; 6+ messages in thread
From: Pal-Kristian Engstad @ 2002-12-05 23:53 UTC (permalink / raw)
To: Oleg; +Cc: caml-list
On Thursday 05 December 2002 03:27 pm, Oleg wrote:
> P.S. I tried replying off the list (where "what do you mean" questions
> usually belong), but your mail server is refusing access.
Hmm, that's odd - I get mails all the time. :-)
Btw, I had a look at it on the net, and apparently this would benefit from
"last call modulo constructor" optimization. In append we are returning
either Nil or Cons(hd, tl), and the compiler should be able to optimize
append, since the only call to the recursive function is in the Cons
constructor.
I'm not sure if Ocaml does this though.
PKE.
--
_
\`. Pål-Kristian Engstad, Senior Software Engineer,
\ `| Naughty Dog, Inc., 1315 3rd Street Promenade,
__\ |`. Santa Monica, CA 90046, USA. (310) 752-1000 x799.
/ /o mailto:engstad@naughtydog.com http://www.naughtydog.com
/ '~ mailto:mrengstad@yahoo.com http://www.engstad.com
/ ,' Hang-gliding Rulez!
~'
-------------------
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
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2002-12-05 23:51 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2002-12-05 20:47 [Caml-list] Why is (@) written in O'Caml? Oleg
2002-12-05 21:16 ` Pal-Kristian Engstad
2002-12-05 21:24 ` Oleg
2002-12-05 21:55 ` Pal-Kristian Engstad
2002-12-05 23:27 ` Oleg
2002-12-05 23:53 ` Pal-Kristian Engstad
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).