[Caml-list] "List.index" or "List.unique" functions?

[Caml-list] "List.index" or "List.unique" functions?

[Rahul Siddharthan]

I just discovered OCaml a week or so ago, and it really seems to be
the "holy grail" -- more concise and elegant that python, almost as
fast as C.  I wish I'd known of it a year ago.  Now I just need to get
used to the functional way of thinking...

I have a question: suppose I have a list l1, and I want to create a new
list l2 with only one copy of any repeated members of the first list
(eg, l1=[1;2;3;4;3;4;5;6;5] -> l2=[1;2;3;4;5;6])

In python, I can define a function to do this quite concisely, eg:

unique = lambda l: [l[n] for n in range(len(l)) if l.index(l[n])==n]

How do I do it in OCaml?  Are there functions equivalent to index
(return the position of the first matching element in the list) and
range (range n = [0;1;...;n-1]), or is there a cleaner way to do it?
The best I can come up with is:

let unique l = 
  let range n = 
    let rec rangen n lacc =
      if n<0 then lacc else rangen (n-1) (n::lacc)
    in rangen (n-1) []
  in
  let index a l =
    let rec indexn a l n =
      if n==(List.length l) then -1
      else if (List.nth l n) =a then n
      else indexn a l (n+1)
    in indexn a l 0
  in 
  List.map (fun n -> List.nth l n) (List.filter 
                                      (fun n -> n=(index (List.nth l n) l))   
                                      (range (List.length l)));;

(it would be more concise if range and index already exist, but even
then, the last line looks rather ugly to me...)

Thanks

Rahul

-------------------
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] "List.index" or "List.unique" functions?

[Martin Jambon]

On Fri, 30 Apr 2004, Rahul Siddharthan wrote:

> I just discovered OCaml a week or so ago, and it really seems to be
> the "holy grail" -- more concise and elegant that python, almost as
> fast as C.  I wish I'd known of it a year ago.  Now I just need to get
> used to the functional way of thinking...
>
> I have a question: suppose I have a list l1, and I want to create a new
> list l2 with only one copy of any repeated members of the first list
> (eg, l1=[1;2;3;4;3;4;5;6;5] -> l2=[1;2;3;4;5;6])

1) Naive O(n^2) solution:
let rec unique = function
    [] -> []
  | hd :: tl ->
      if List.mem hd tl then unique tl
      else hd :: unique tl

The result is not sorted.


2) With a hash table you can get something quite efficient (O(n)) and not
too difficult to write:

let unique l =
  let tbl = Hashtbl.create 10 in
  List.iter (fun i -> Hashtbl.replace tbl i ()) l;
  Hashtbl.fold (fun key data accu -> key :: accu) tbl []

The result is not sorted.
You can replace "10" with "List.length l" if really you don't have any
idea of the initial size of the table and want to avoid multiple resizings
of the table.

"fold" functions (List.fold_left, List.fold_right, Hashtbl.fold,
Array.fold_left...) are very useful, and are most of the time more
appropriate than imperative loops ("for" and "while").


3) With sort/simplify (O(n log n)) (I expect it to be much less
efficient than 2)):

let unique l =
  let rec simplify last l =
    match l with
	[] -> [last]
      | hd :: tl ->
	  if hd = last then
	    simplify last tl
	  else
	    last :: simplify hd tl in
  match List.sort compare l with
      [] -> []
    | hd :: tl ->
	simplify hd tl


Martin

-------------------
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] "List.index" or "List.unique" functions?

[Benjamin Geer]

Rahul Siddharthan wrote:
> I have a question: suppose I have a list l1, and I want to create a new
> list l2 with only one copy of any repeated members of the first list
> (eg, l1=[1;2;3;4;3;4;5;6;5] -> l2=[1;2;3;4;5;6])

Here's one way:

let unique ls =
   let uniq_aux new_ls old_elem =
     match new_ls with
       | [] -> [ old_elem ]
       | hd :: tl when hd = old_elem -> new_ls
       | _ -> old_elem :: new_ls
   in
   let sorted = List.sort compare ls in
     List.rev (List.fold_left uniq_aux [] sorted) ;;

Ben

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

Thanks Re: [Caml-list] "List.index" or "List.unique" functions?

[Rahul Siddharthan]

Thanks to all who replied, on- and off-list.  I got many nice answers.

Thanks also for those who let me know about the ocaml-beginners list.
It wasn't listed on www.ocaml.org, which I didn't realise was an 
unofficial page. 

Rahul

-------------------
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] "List.index" or "List.unique" functions?

[Karl Zilles]

Rahul Siddharthan wrote:
> I have a question: suppose I have a list l1, and I want to create a new
> list l2 with only one copy of any repeated members of the first list
> (eg, l1=[1;2;3;4;3;4;5;6;5] -> l2=[1;2;3;4;5;6])

let unique l = List.rev (List.fold_left (fun results x -> if 
List.mem x 		results then results else x::results) [] l);;

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

List.rev is not tail recursive, so you wouldn't want to use this 
function on industrial size lists.

You might want to check out the ocaml_beginners@yahoogroups.com mailing 
list.  That is a good place to ask questions like this.

-------------------
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] "List.index" or "List.unique" functions?

[Matthieu Sozeau]

On Fri, Apr 30, 2004 at 12:08:56PM -0700, Karl Zilles wrote:
> List.rev is not tail recursive, so you wouldn't want to use this 
> function on industrial size lists.

List.rev and List.rev_map are tail recursive, unlike map. It can be
really benefical sometimes to use an accumulator in a recursive
function and reverse it at the end (it certainly wouldn't if List.rev
was not tail recursive).
-- 
It's a small world, but I wouldn't want to have to paint it.
		-- Steven Wright

-------------------
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] "List.index" or "List.unique" functions?

[Karl Zilles]

Matthieu Sozeau wrote:
> On Fri, Apr 30, 2004 at 12:08:56PM -0700, Karl Zilles wrote:
> 
>>List.rev is not tail recursive, so you wouldn't want to use this 
>>function on industrial size lists.
> 
> 
> List.rev and List.rev_map are tail recursive, unlike map. It can be
> really benefical sometimes to use an accumulator in a recursive
> function and reverse it at the end (it certainly wouldn't if List.rev
> was not tail recursive).

You're right.  Not sure how that got into my head.  Thanks for the 
correction.

-------------------
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] "List.index" or "List.unique" functions?

[Remi Vanicat]

Karl Zilles <zilles@1969.ws> writes:

> Rahul Siddharthan wrote:
>> I have a question: suppose I have a list l1, and I want to create a new
>> list l2 with only one copy of any repeated members of the first list
>> (eg, l1=[1;2;3;4;3;4;5;6;5] -> l2=[1;2;3;4;5;6])
>
> let unique l = List.rev (List.fold_left (fun results x -> if List.mem
> x 		results then results else x::results) [] l);;
>
> unique [1;2;3;4;3;4;5;6;5];;
> - : int list = [1; 2; 3; 4; 5; 6]
>
> List.rev is not tail recursive, so you wouldn't want to use this
> function on industrial size lists.

List.rev is tail recursive...

[...]


-- 
Rémi Vanicat

-------------------
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] "List.index" or "List.unique" functions?

[JM Nunes]

Note that List.rev is not being useful in this case. 

> let unique l = List.rev (List.fold_left (fun results x -> if List.mem
> x 		results then results else x::results) [] l);;
>
> unique [1;2;3;4;3;4;5;6;5];;
> - : int list = [1; 2; 3; 4; 5; 6]

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

For sorting List.sort or other must be used.


-------------------
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] "List.index" or "List.unique" functions?

[Karl Zilles]

JM Nunes wrote:

> Note that List.rev is not being useful in this case. 

See below:

> 
>>let unique l = List.rev (List.fold_left (fun results x -> if List.mem
>>x 		results then results else x::results) [] l);;
>>
>>unique [1;2;3;4;3;4;5;6;5];;
>>- : int list = [1; 2; 3; 4; 5; 6]
> 
> 
> # unique [7;1;2;3;4;3;4;5;6;5];;
> - : int list = [7; 1; 2; 3; 4; 5; 6]

This is the correct output.

> 
> For sorting List.sort or other must be used.

I think what you're missing is that he's not actually looking to sort 
the list.  His python function was order preserving, as is my ocaml 
version.   His test case could have been chosen more carefully to 
demonstrate 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

[Caml-list] List.rev

[skaller]

On Sat, 2004-05-01 at 05:08, Karl Zilles wrote:
> Rahul Siddharthan wrote:

> List.rev is not tail recursive, so you wouldn't want to use this 
> function on industrial size lists.

But it should be. Why isn't it???

let rev lst = let r = ref [] in
  let rec aux lst = match lst with
  | [] -> !r
  | h::t -> r:= h :: !r; aux t
in aux lst

BTW: documentation that says a function is 'tail recursive'
is misguided. That's an implementation detail of no
possible use to a user of the function. The user may
benefit from knowing the complexity of the function
in terms of speed and auxilliary storage required.

-- 
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] List.rev

[Jon Harrop]

On Saturday 01 May 2004 02:59, skaller wrote:
> > List.rev is not tail recursive, so you wouldn't want to use this
> > function on industrial size lists.
>
> But it should be. Why isn't it???

I'm not sure that it isn't already tail-recursive. Doesn't the second argument 
in rev_append act as an accumulator?

> let rev lst = let r = ref [] in
>   let rec aux lst = match lst with
>
>   | [] -> !r
>   | h::t -> r:= h :: !r; aux t

let rev l = fold_left (fun t h -> h::t) [] l

=:-p

> BTW: documentation that says a function is 'tail recursive'
> is misguided. That's an implementation detail of no
> possible use to a user of the function. The user may
> benefit from knowing the complexity of the function
> in terms of speed and auxilliary storage required.

As "tail recursive" typically means less stack storage and more heap storage 
instead of the reverse, it is useful to a user and it does pertain to the 
complexity (although it obviously doesn't quantify the complexity of the heap 
storage).

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] List.rev

[brogoff]

On Fri, 1 May 2004, skaller wrote:
> BTW: documentation that says a function is 'tail recursive'
> is misguided. That's an implementation detail of no
> possible use to a user of the function. The user may
> benefit from knowing the complexity of the function
> in terms of speed and auxilliary storage required.

You couldn't be more wrong. When your program crashes because you've blown
stack and you're embarassed as all hell (you never expected the user to run
with *that* big of an input) you remember that documentation and curse your
own carelessness, rather than the OCaml team.

Since Ocaml optimizes tail calls, that info *is* about auxiliary storage.

On the same point, it would be a good thing if OCaml had a better solution
to these "tail recursion modulo cons" issues than writing set_cdr using
Obj functions. Better means "in the language" here; I'm aware that various
libraries have implemented the set_cdr approach.

There's only a handful of things that bug me about the OCaml language, and
this  makes the list. I'd append it to the list, but it might raise an
exception ;-).


-- 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] List.rev

[skaller]

On Sat, 2004-05-01 at 14:38, brogoff@speakeasy.net wrote:
> On Fri, 1 May 2004, skaller wrote:
> > BTW: documentation that says a function is 'tail recursive'
> > is misguided. That's an implementation detail of no
> > possible use to a user of the function. The user may
> > benefit from knowing the complexity of the function
> > in terms of speed and auxilliary storage required.
> 
> You couldn't be more wrong.

Due respect but I am quite correct and provably so.

Tail-rec is a property of an actual function implementation.

The term has no meaning without exhibiting implementation
code, and it is usual for libraries to quite pointedly
NOT do that: instead the behaviour is specified in
terms of input and output of the function, and also
side effects in terms of time and storage requirements
are sometimes thrown in for more detail.

Saying tail-rec is suggestive only if you have
an implementation in your minds-eye.

It is good the documentation says the function
is tail-rec, this is better than no performance
information

BUT IT IS STILL NOT A NORMATIVE SPECIFICATION.


-- 
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] List.rev

[William Lovas]

On Sat, May 01, 2004 at 03:12:57PM +1000, skaller wrote:
> The term has no meaning without exhibiting implementation
> code, and it is usual for libraries to quite pointedly
> NOT do that: instead the behaviour is specified in
> terms of input and output of the function, and also
> side effects in terms of time and storage requirements
> are sometimes thrown in for more detail.

In many functional languages, O'Caml included, it's assumed that tail calls
are optimized to jumps, so that tail recursive functions do not allocate
any stack space for each recursive call.  (I believe in Scheme this is even
included in the language specification.)

With that in mind, you can read "This function is not tail recursive" as a
behavioral specification, "This function might terminate abnormally due to
stack overflow" -- and that's a useful side effect to document.

William

-------------------
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] List.rev

[skaller]

On Sat, 2004-05-01 at 17:08, William Lovas wrote:

> In many functional languages, O'Caml included, it's assumed that tail calls
> are optimized to jumps, so that tail recursive functions do not allocate
> any stack space for each recursive call.  (I believe in Scheme this is even
> included in the language specification.)
> 
> With that in mind, you can read "This function is not tail recursive" as a
> behavioral specification, "This function might terminate abnormally due to
> stack overflow" -- and that's a useful side effect to document.

Indeed. I know that. But it is suboptimal.
There are better ways to write specifications
that (a) refer to an implementation that isn't exhibited
and (b) assume tail-rec implies no stack allocation

The first is called 'ill formed formula', and
the second is called 'unwarranted assumption'.

So the spec is (a) meaningless gibberish 
and (b) even if the implementation were exhibited
it says nothing about the performance.

Yet it is easy enough to say 

O(n) time and O(1) stack

and mean that this is a *requirement* on the implementation
and a guarrantee to the programmer.

That is the intent, why not say it?


-- 
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] List.rev

[Jon Harrop]

On Saturday 01 May 2004 09:10, skaller wrote:
> Yet it is easy enough to say
>
> O(n) time and O(1) stack

O(n) heap

But why restrict yourself to asymptotic complexities... ;-)

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] List.rev

[skaller]

On Sat, 2004-05-01 at 18:32, Jon Harrop wrote:
> On Saturday 01 May 2004 09:10, skaller wrote:
> > Yet it is easy enough to say
> >
> > O(n) time and O(1) stack
> 
> O(n) heap

Well, the output requires O(n) heap by nature of
the result..

> But why restrict yourself to asymptotic complexities... ;-)

Good question. one reason is that it's hard to do better
in a specification: you can't very well say 'this takes
1 second' :-)

However, perhaps you can say something for small n.

Usually this is a QOI issue. QOI = Quality of Implementation.
Meaning "not an issue for standardisation". QOI is important
of course -- we use Ocaml because of its high performance.

-- 
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] "List.index" or "List.unique" functions?

[Richard Jones]

On Fri, Apr 30, 2004 at 01:54:29PM -0400, Rahul Siddharthan wrote:
> I have a question: suppose I have a list l1, and I want to create a new
> list l2 with only one copy of any repeated members of the first list
> (eg, l1=[1;2;3;4;3;4;5;6;5] -> l2=[1;2;3;4;5;6])

This is actually another function which could be usefully added to
the standard library, along with:

frequency : 'a list -> (int * 'a) list     (requires input list to be sorted)

and group_by, defined by Isaac Trotts here:

http://groups.yahoo.com/group/ocaml_beginners/message/1556

Rich.

-- 
Richard Jones. http://www.annexia.org/ http://www.j-london.com/
Merjis Ltd. http://www.merjis.com/ - improving website return on investment
http://www.YouUnlimited.co.uk/ - management courses

-------------------
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] List.rev

[Richard Jones]

Are there automatic ways to transform non-tail-recursive functions
into tail-recursive ones?

Rich.

-- 
Richard Jones. http://www.annexia.org/ http://www.j-london.com/
Merjis Ltd. http://www.merjis.com/ - improving website return on investment
MAKE+ is a sane replacement for GNU autoconf/automake. One script compiles,
RPMs, pkgs etc. Linux, BSD, Solaris. http://www.annexia.org/freeware/makeplus/

-------------------
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] List.rev

[Nicolas Cannasse]

> Are there automatic ways to transform non-tail-recursive functions
> into tail-recursive ones?
>
> Rich.

You can have a look at ExtLib sources. We provide tail-recursive
implementations for each List operations (with same "little o" complexity).

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] List.rev

[Jon Harrop]

On Saturday 01 May 2004 11:07, Richard Jones wrote:
> Are there automatic ways to transform non-tail-recursive functions
> into tail-recursive ones?

Dunno - are we allowed to use IFS's student algorithm? ;-)

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] List.rev

[John Goerzen]

On Sat, May 01, 2004 at 11:59:10AM +1000, skaller wrote:
> BTW: documentation that says a function is 'tail recursive'
> is misguided. That's an implementation detail of no
> possible use to a user of the function. The user may
> benefit from knowing the complexity of the function
> in terms of speed and auxilliary storage required.

That wrong.  I really want to know whether or not I'm going to get a
stack overflow from using a function on a large list.

-------------------
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] List.rev

[skaller]

On Sun, 2004-05-02 at 02:41, John Goerzen wrote:
> On Sat, May 01, 2004 at 11:59:10AM +1000, skaller wrote:
> > BTW: documentation that says a function is 'tail recursive'
> > is misguided. That's an implementation detail of no
> > possible use to a user of the function. The user may
> > benefit from knowing the complexity of the function
> > in terms of speed and auxilliary storage required.
> 
> That wrong.  I really want to know whether or not I'm going to get a
> stack overflow from using a function on a large list.

Sigh. I agree. You want to know that. And saying
'tail-rec' DOES NOT TELL YOU. Saying O(1) stack does.
So I'd like to see those comments changed to actually
describe behaviour in abstract terms, rather than
just being a loose hint about the possible implementation,
leaving you to guess what the implication is.

-- 
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] List.rev

[Andreas Rossberg]

skaller <skaller@users.sourceforge.net> wrote:
>
> There are better ways to write specifications
> that (a) refer to an implementation that isn't exhibited
> and (b) assume tail-rec implies no stack allocation
>
> The first is called 'ill formed formula', and
> the second is called 'unwarranted assumption'.
>
> So the spec is (a) meaningless gibberish
> and (b) even if the implementation were exhibited
> it says nothing about the performance.
>
> Yet it is easy enough to say
>
> O(n) time and O(1) stack

Sorry, but isn't talking about a stack even less meaningful
implementation-driven "gibberish"? Usually, a functional language definition
does not mention anything like a stack. In fact, some major FP
implementations don't even use a stack.

Tail recursion at least is a clear syntactic property that can be defined
without referring to implementation techniques. That a tail-recursive
function uses constant space is then a well-understood QOI issue. No serious
FP implementation would dare not to meet this criterion.

Cheers,

  - Andreas

-------------------
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] List.rev

[skaller]

On Sun, 2004-05-02 at 22:07, Andreas Rossberg wrote:
> > Yet it is easy enough to say
> >
> > O(n) time and O(1) stack
> 
> Sorry, but isn't talking about a stack even less meaningful
> implementation-driven "gibberish"? 

That depends on the conformance model. One can certainly
speak of auxilliary storage requirements. In C++, one can
be definite about STL heap storage (because the store
is obtained by definite calls to an allocator).

> Usually, a functional language definition
> does not mention anything like a stack. 

A purely semantic definition may well not.
Such a definition is generally considered inadequate
for a library precisely because it doesn't include
performance requirements.

> In fact, some major FP
> implementations don't even use a stack.

Indeed .. Felix doesn't use the machine stack for 
procedure calls, its incompatible with high speed
context switching of control inverted algorithms 
on a typical Unix box.

However, Ocaml does, and, the distinction between heap
and stack is actually quite important to many clients:
many systems have a lot of potential heap, but only limited
stack. That doesn't mean distinguishing auxilliary heap
and stack is the right thing to do. I think it might be,
but I don't know, and there is a value judgement involved
deciding how much freedom an implementor should have.

It isn't necessary to specify performance: but I do believe
there is a consensus to do so. Certainly that belief
is *firmly* held in the C++ world now, since STL introduced
the idea to the committee that such requirements were an
integral part of a specification.

[There is actually a story here: there was concern that
the requirements on STL Sort were so high that NO known
implementation could meet them bar one: the one Stepanov
provided, which was subject to a Patent held by HP.
HP was asked to relinquish its intellectual property rights
and did.]

So, I'm not desiring to force my view on what conformance
model should be used, and how tight the specs are,
only that if specs are given, they be normative
well formed coherent requirements.

Its quite possible to *define* the term 'tail-rec'
in the library preable and thereby avoid the current
problem that the requirement doesn't mean anything.

> Tail recursion at least is a clear syntactic property 

Yes. I agree. But the standard library isn't defined
in Ocaml but a more abstract semantics. Clearly one
wishes to allow for Ocaml implementations, C implementations,
and even machine code implementations.

The usual technique is to specify a machine abstraction,
define semantics in terms of that, and then bind the
compiler performance to the abstraction.

> That a tail-recursive
> function uses constant space is then a well-understood QOI issue. No serious
> FP implementation would dare not to meet this criterion.

First, Ocaml isn't a FP. One can certainly introduce
O(n) auxilliary store in a loop (or tail rec function)
using mutable state.

Second, I do agree that one expects a tail recursive calls
to be implemented as loops. This is a serious problem
in Felix because it generates C: procedures are easily
optimised: they never use C-stack except transiently, 
functions are not quite so easy because they do.

Third, tail-rec in Ocaml isn't quite so clear due to
exception handling (still well defined though).

Fourth, it is quite possible for a code to contain
both tail calls and non-tail calls: use linear stack,
instead of quadradic for example. Tail-rec or not
is too black and white.

Fifth: a tail rec function can still be high complexity.
It depends on the actual implementation. You CAN
sort a list using a tail-rec bubble sort... or a tail
rec function allocating n copies of the list for fun .. 
(yeah it still wouldn't blow the stack ..)

So generally, I do agree that the fact the Ocaml docs
now say 'tail-rec' where before there was no annotation at all:
this is a Good Thing (TM).

I don't want the implication removed from the library!
I'd just like to see it stated more normatively.
No hurry either. Just a note to think about, because there
are more and more people using Ocaml, and that does tend
to make any imprecision come out, especially new users
not familiar with the 'common understanding' about things
like 'tail-rec'.

BTW: for some STL algorithms, the EXACT number of calls
the algorithm makes to the copy constructor is mandated.
(The copy algorithm). The question arose if an implementation
was permitted to make a copy like this:

	tmp = *p++
	*q++ = tmp

and the answer is NO, that is banned. Exactly n calls are 
allowed and no more. Each object is copied *exactly* once.
No 'O' notation about it.

-- 
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] List.rev

[Brian Hurt]

On Sat, 1 May 2004, Nicolas Cannasse wrote:

> > Are there automatic ways to transform non-tail-recursive functions
> > into tail-recursive ones?
> >
> > Rich.
> 
> You can have a look at ExtLib sources. We provide tail-recursive
> implementations for each List operations (with same "little o" complexity).
> 

This is actually quite bad advice (sorry, Nicolas)- many of the "tricks" 
we do in Ext-Lib are not for newbies.  I'm thinking specifically of the 
Obj.magic stuff.  If you find yourself doing this anywhere else, you are 
almost certainly screwing up.

There is a fairly standard set of tricks I use to turn non-tail-recursive 
functions into tail-recursive functions.  The two most important ones are:

1) build lists backwards, then reverse them when they're done.  For 
example, List.append could be implemented:
	let append alist blist =
		let revlist = List.rev_append blist (List.rev alist) in
		List.rev revlist
	;;

2) Hoist recursive calls out of try/catch clauses, introducing variables
to detect when an exception was thrown.  For example, to read all the 
lines of a channel into a list of strings, do:
	let readfile chan = 
		let rec loop accum =
			let eof, line = 
				try
					false, (input_line chan)
				with
					| End_of_file ->
						true, ""
			in
			if (eof) then
				List.rev accum
			else
				loop (line :: accum)
		in
		loop []
	;;


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