"ocaml_beginners"::[] tail recursion

could anyone tell me if this is tail recursive?

let append l1 l2 =
let rl1 = List.rev l1 in
let rec rappend l1 l2 =
if l1 = [] then l2
else
let hd = List.hd l1 in
let tl = List.tl l1 in
let larger = hd :: l2 in
rappend tl larger
in rappend rl1 l2;;

# append [1;2;3] [4;5;6];;
- : int list = [1; 2; 3; 4; 5; 6]
--
View this message in context: http://www.nabble.com/tail-recursion-tp15950911p15950911.html
Sent from the Ocaml Beginner mailing list archive at Nabble.com.

Messages in this topic (29) Reply (via web post) | Start a new topic

.

On Monday 10 March 2008 17:49:06 stevewirts wrote:
> could anyone tell me if this is tail recursive?
>
> let append l1 l2 =
> let rl1 = List.rev l1 in
> let rec rappend l1 l2 =
> if l1 = [] then l2
> else
> let hd = List.hd l1 in
> let tl = List.tl l1 in
> let larger = hd :: l2 in
> rappend tl larger
> in rappend rl1 l2;;
>;
> # append [1;2;3] [4;5;6];;
> - : int list = [1; 2; 3; 4; 5; 6]

That is tail recursive but you can write it much more elegantly using pattern
matching:

let rec rev_append l1 l2 =
match l1, l2 with
| [], l2 -> l2
| hd::tl, l2 -> rev_append tl (hd::l2);;

let append l1 l2 =
rev_append (List.rev l1) l2;;

Note that you already have:

# [1;2;3] [4;5;6];;
- : int list = [1; 2; 3; 4; 5; 6]

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e

Messages in this topic (30) Reply (via web post) | Start a new topic

.

Jon Harrop wrote:
> let rec rev_append l1 l2 =
> match l1, l2 with
>; | [], l2 -> l2
> | hd::tl, l2 -> rev_append tl (hd::l2);;

Or, less verbosely...

let rec rev_append l1 l2 =

match l1 with

| [] -> l2
| hd::tl -> rev_append tl (hd::l2);;

Messages in this topic (31) Reply (via web post) | Start a new topic

.

On Mon, 10 Mar 2008, Jon Harrop wrote:

> On Monday 10 March 2008 17:49:06 stevewirts wrote:
>> could anyone tell me if this is tail recursive?
>>
>> let append l1 l2 =
>> let rl1 = List.rev l1 in
>> let rec rappend l1 l2 =
>> if l1 = [] then l2
>> else
>> let hd = List.hd l1 in
>> let tl = List.tl l1 in
>> let larger = hd :: l2 in
>> rappend tl larger
>> in rappend rl1 l2;;
>;>
>;> # append [1;2;3] [4;5;6];;
>> - : int list = [1; 2; 3; 4; 5; 6]
>
> That is tail recursive but you can write it much more elegantly using pattern
> matching:
>
> let rec rev_append l1 l2 =
> match l1, l2 with
>; | [], l2 -> l2
> | hd::tl, l2 -> rev_append tl (hd::l2);;
>
> let append l1 l2 =
> rev_append (List.rev l1) l2;;

Or even:

let append l1 l2 =
rev_append (rev_append l1 []) l2;;

Martin
--
http://wink.com/profile/mjambon
http://martin.jambon.free.fr

Messages in this topic (32) Reply (via web post) | Start a new topic

.

On Mon, 10 Mar 2008 11:52:19 -0700
Karl Zilles < zilles%401969web.com">zilles1969web.com> wrote:

> let rec rev_append l1 l2 =
>
> match l1 with
>
> | [] -> l2
> | hd::tl -> rev_append tl (hd::l2);;

Yes, it's list.ml source.

I do not say the following code is better, but jff throw away the two parameters lists :

let id x = x

let cons a d = a::d

let ( <<- ) f g x = f (g x)

let append =
let rec rappend = function
[] -> id
| h::t -> rappend t <<- (cons h) in
rappend <<- List.rev

It is the opportunity to ask this :
I wonder if this later is perfectly equivalent to the former ?
Is it absolutely true that the 3 tiny functions id, cons and ( <<- ) will be inlined without any efficiency loss ?

Thanks,

Fabrice

Messages in this topic (33) Reply (via web post) | Start a new topic

.

Thanks a lot,

> > let append =
> > let rec rappend = function
> > [] -> id
> > | h::t -> rappend t <<- (cons h) in
> > rappend <<- List.rev
>
> There is a problem on this code: it is not polymorphic enough, just
>; try
>
> rappend [2] [3];;
This works.

> rappend [None] [];;
Yes, I discover you are right.

The type of this expression,
'_a option list -> '_a option list -> '_a option list,
contains type variables that cannot be generalized

Or maybe the lack of polymorphism you spoke about is related to these two lines taken together ?

It's not the first time I run into problems ditching last parameters.
Please what are the things to think to, to detect that kind of problem ?

>; if you want a fully polymorphic version, you need to wrote it as :
> let append l =
> let rec rappend = function
> [] -> id
> | h::t -> rappend t <<- (cons h) in
> (rappend <<- List.rev) l
>
> which defeat your goal.
A harsh term for half a failure : just one parameter is yet kept !

>; > Is it absolutely true that the 3 tiny functions id, cons and ( <<- )
> > will be inlined without any efficiency loss ?
>
> Not sure, well, not with bytecode, I don't know with ocamlopt, you
> should test (option -S to ask ocamlopt for the assembly code).

Looking at the generated code for comparison ( ugly 'as' syntax ) :
I've programmed several assemblers, 8086 too, but this compiler output - as often - is pretty unreadable.

However, I love the 'id' code : just 'ret' !

I cannot be assertive but this indirect call, depending on what lies on camlTrop+... :

movl %eax, 0(%esp)
movl camlTrop + 4, %ebx
movl (%eax), %eax
movl (%ebx), %ecx
call *%ecx

doesn't seem to refer to an OCaml internal but more probably to a not inlined function.

Adding a -inline 1 (or 2) option doesn't affect generated code.

Ciao,

Fabrice

Messages in this topic (35) Reply (via web post) | Start a new topic

.

On Tuesday 11 March 2008 20:23:50 Fabrice Marchant wrote:
&gt; It's not the first time I run into problems ditching last parameters.
> Please what are the things to think to, to detect that kind of problem ?

This is the value restriction. Basically, you can cancel arguments from both
sides of a function definition except for the last argument in impure
languages like OCaml:

let f x y z = g 3 x y z
let f x y = g 3 x y
let f x = g 3 x

but not:

let f = g 3

>; > if you want a fully polymorphic version, you need to wrote it as :
> > let append l =
> > let rec rappend = function
> > [] -> id
> >
>; > | h::t -> rappend t <<- (cons h) in
> >
>; > (rappend <<- List.rev) l
> >
>; > which defeat your goal.
&gt;
> A harsh term for half a failure : just one parameter is yet kept !

You might prefer:

let append =
...
fun l -> (rappend <<- List.rev) l

>; > > Is it absolutely true that the 3 tiny functions id, cons and ( <<- )
> > > will be inlined without any efficiency loss ?

I believe function arguments to higher-order functions are not inlined. So
List.rev will not be inlined into ( <<- ).

&gt; Looking at the generated code for comparison ( ugly 'as' syntax ) :
> I've programmed several assemblers, 8086 too, but this compiler output - as
> often - is pretty unreadable.
>
> However, I love the 'id' code : just 'ret' !
>
> I cannot be assertive but this indirect call, depending on what lies on
> camlTrop+... :
>
> movl %eax, 0(%esp)
> movl camlTrop + 4, %ebx
>; movl (%eax), %eax
>; movl (%ebx), %ecx
>; call *%ecx
&gt;
> doesn't seem to refer to an OCaml internal but more probably to a not
> inlined function.
>
&gt; Adding a -inline 1 (or 2) option doesn't affect generated code.

You might try bigger numbers (like 1e6 .

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e

Messages in this topic (36) Reply (via web post) | Start a new topic

.

On Tue, 11 Mar 2008 22:26:19 +0000
Jon Harrop < jon%40ffconsultancy.com">jonffconsultancy.com&gt; wrote:

> This is the value restriction. Basically, you can cancel arguments from both
> sides of a function definition except for the last argument in impure
> languages like OCaml:
&gt;
> let f x y z = g 3 x y z
> let f x y = g 3 x y
> let f x = g 3 x
>
> but not:
>;
> let f = g 3

Thanks a lot for the explanations.

&gt; > > if you want a fully polymorphic version, you need to wrote it as :
> > > let append l =
> > > let rec rappend = function
> > > [] -> id
> > >
>; > > | h::t -> rappend t <<- (cons h) in
> > >
>; > > (rappend <<- List.rev) l

>; You might prefer:
>
> let append =
> ...
> fun l -> (rappend <<- List.rev) l

This doesn't seems to change a lot at first glance, however yes, imho this is nicer this way, because the two 'l' are located closer.

Regards,

Fabrice

http://caml.inria.fr/cgi-bin/hump.en.cgi?contrib=626
http://caml.inria.fr/cgi-bin/hump.en.cgi?contrib=627
http://caml.inria.fr/cgi-bin/hump.en.cgi?contrib=619

Messages in this topic (37) Reply (via web post) | Start a new topic

.