[Caml-list] still puzzled on generic types

[Caml-list] still puzzled on generic types

[Walter Cazzola]

Dear all,
waiting for some hints on my other issue for functors and generic I was
playing with an enumerate function (with tail recursion):

   let rec enumerate ?(l':((int * 'a) list)=[]) ?(n=0) l =
     match l with
          h::l1 -> enumerate (l'@[(n,h)]) (n+1) l1
     |  [] -> l'

this should just take a list and return a list of couple whose first
entry is the position in the list of the element; to be clearer:

   enumerate ['a'; 'b'; 'c'] -> [(0,'a'); (1,'b'); (2,'c')];

but this doesn't work as by type mismatch:

  Error: This expression has type (int * 'a) list
         but an expression was expected of type 'a list

Doesn't a matter if I've annotated the type (int * 'a) list
to the optional argument l' when I try to call the function with the new
value it says that the two things don't have the same type.

I'm quite puzzled by this behavior, any explanation/help is welcome as
usual.

Walter
-- 

RE: [Caml-list] still puzzled on generic types

[David Allsopp]

Walter Cazzola wrote:
> Dear all,
> waiting for some hints on my other issue for functors and generic I was
> playing with an enumerate function (with tail recursion):
> 
>    let rec enumerate ?(l':((int * 'a) list)=[]) ?(n=0) l =
>      match l with
>           h::l1 -> enumerate (l'@[(n,h)]) (n+1) l1
>      |  [] -> l'
> 
> this should just take a list and return a list of couple whose first entry
> is the position in the list of the element; to be clearer:
> 
>    enumerate ['a'; 'b'; 'c'] -> [(0,'a'); (1,'b'); (2,'c')];
> 
> but this doesn't work as by type mismatch:
> 
>   Error: This expression has type (int * 'a) list
>          but an expression was expected of type 'a list

I think it's probably something to do with optional arguments not behaving as you expect. But this is a bad use for optional arguments - you should instead use a nested function to pass the accumulator values. This works fine:

let enumerate l =
  let rec enumerate acc n = function
    h::ls -> enumerate ((n, h)::acc) (n + 1) ls
  | [] -> List.rev acc
  in
    enumerate [] 0 l

Concatenating lists is also expensive in terms of the left list so your function is about as slow as possible! Much better when aiming for tail recursion, accumulate a reversed list and then reverse it in the basis case.


David

RE: [Caml-list] still puzzled on generic types

[Walter Cazzola]

On Thu, 29 Sep 2011, David Allsopp wrote:

> I think it's probably something to do with optional arguments not
> behaving as you expect.

uhm, would be interesting to see what is wrong on my use of the optional
arguments.

> But this is a bad use for optional arguments - you should instead use
> a nested function to pass the accumulator values. This works fine:

yes my first attempt was implemented with nested functions but ,,,

> let enumerate l =
>  let rec enumerate acc n = function
>    h::ls -> enumerate ((n, h)::acc) (n + 1) ls
>  | [] -> List.rev acc
>  in
>    enumerate [] 0 l

... my nested function had a different name than the nextee function and
I was passing l to it too. Could you explain me why your code works? in
particular where does it take the list to enumerate? Silly question I
know but it seems magic to me written in such a way

> Concatenating lists is also expensive in terms of the left list so
> your function is about as slow as possible! Much better when aiming
> for tail recursion, accumulate a reversed list and then reverse it in
> the basis case.

Ok, thanks for the note, but efficiency issues are still far in my
learning curve ;-)

Walter

-- 

RE: [Caml-list] still puzzled on generic types

[David Allsopp]

Walter Cazzola wrote:
> On Thu, 29 Sep 2011, David Allsopp wrote:
> 
> > I think it's probably something to do with optional arguments not
> > behaving as you expect.
> 
> uhm, would be interesting to see what is wrong on my use of the optional
> arguments.

Separately answered...

> > But this is a bad use for optional arguments - you should instead use
> > a nested function to pass the accumulator values. This works fine:
> 
> yes my first attempt was implemented with nested functions but ,,,
> 
> > let enumerate l =
> >  let rec enumerate acc n = function
> >    h::ls -> enumerate ((n, h)::acc) (n + 1) ls
> >  | [] -> List.rev acc
> > in
> >    enumerate [] 0 l
> 
> ... my nested function had a different name than the nextee function and I
> was passing l to it too. Could you explain me why your code works? in
> particular where does it take the list to enumerate? Silly question I know
> but it seems magic to me written in such a way

OCaml allows a name to hide a previous use of a name in the scope chain. The closest name moving up the "let .. in .." chains will always be the one used. Very occasionally that can cause some weird bugs but as the types will often differ, it's a clearer way of writing (rather than inventing arbitrary new names or using lots of prime symbols). I defined the innermost [enumerate] using the [function] keyword. You could equivalently write:

let rec enumerate acc n l =
  match l with
    h::ls -> ...

but the function keyword gives you that for free (it's the keyword for introducing an anonymous function with match and simply gives you a match over a single anonymous parameter).

> > Concatenating lists is also expensive in terms of the left list so
> > your function is about as slow as possible! Much better when aiming
> > for tail recursion, accumulate a reversed list and then reverse it in
> > the basis case.
> 
> Ok, thanks for the note, but efficiency issues are still far in my
> learning curve ;-)

Learning not to concatenate lists is part of learning tail recursion - it should be higher up your list ;o)

HTH,


David

Re: [Caml-list] still puzzled on generic types

[Pierre Chopin]

You need to explicitly name the optional arguments you are passing, 
otherwise the interpreter thinks you are trying to pass l, which should be 'a list : 

 let rec enumerate ?(l'=[]) ?(n=0) l =
   match l with
        h::l1 -> enumerate  ~l':(l'@[(n,h)]) ~n:(n+1) l1
   |  [] -> l'


-Pierre


Le 29 sept. 2011 à 11:07, Walter Cazzola a écrit :

> Dear all,
> waiting for some hints on my other issue for functors and generic I was
> playing with an enumerate function (with tail recursion):
> 
>  let rec enumerate ?(l':((int * 'a) list)=[]) ?(n=0) l =
>    match l with
>         h::l1 -> enumerate (l'@[(n,h)]) (n+1) l1
>    |  [] -> l'
> 
> this should just take a list and return a list of couple whose first
> entry is the position in the list of the element; to be clearer:
> 
>  enumerate ['a'; 'b'; 'c'] -> [(0,'a'); (1,'b'); (2,'c')];
> 
> but this doesn't work as by type mismatch:
> 
> Error: This expression has type (int * 'a) list
>        but an expression was expected of type 'a list
> 
> Doesn't a matter if I've annotated the type (int * 'a) list
> to the optional argument l' when I try to call the function with the new
> value it says that the two things don't have the same type.
> 
> I'm quite puzzled by this behavior, any explanation/help is welcome as
> usual.
> 
> Walter
> -- 
> 
> -- 
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 

Re: [Caml-list] still puzzled on generic types

[Walter Cazzola]

On Thu, 29 Sep 2011, Pierre Chopin wrote:

> You need to explicitly name the optional arguments you are passing,
> otherwise the interpreter thinks you are trying to pass l, which should be 'a list :

> let rec enumerate ?(l'=[]) ?(n=0) l =
>   match l with
>        h::l1 -> enumerate  ~l':(l'@[(n,h)]) ~n:(n+1) l1
>   |  [] -> l'

great point, you are right (what a silly error), thanks a lot.

Walter
--