tail recursion

[stevewirts]

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]

[Jon Harrop]

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

[Martin Jambon]

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

[Karl Zilles]

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

[Fabrice Marchant-2]

On Mon, 10 Mar 2008 11:52:19 -0700
Karl Zilles <zilles@...> 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

[remi.vanicat]

Fabrice Marchant <fabrice.marchant@...> writes:
> 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];;
rappend [None] [];;

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.

>
>   It is the opportunity to ask this :
> I wonder if this later is perfectly equivalent to the former ?

Not sure

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

--
Rémi Vanicat

[Fabrice Marchant-2]

  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

[Jon Harrop]

On Tuesday 11 March 2008 20:23:50 Fabrice Marchant wrote:
> 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.
>
> 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 ( <<- ).

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

You might try bigger numbers (like 1e6 :-).

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

[Fabrice Marchant-2]

On Tue, 11 Mar 2008 22:26:19 +0000
Jon Harrop <jon@...> 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:
>
>   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.

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