[Caml-list] Recursive lists

[Caml-list] Recursive lists

[Luca Pascali]

Hi everyone.

I have a little question about the recursive lists.
In an application I needed to use a list composed by some elements 
(placed in the head of the list) and recursive element, like

let rec_list =
    let rec l2 = 100 :: l2 in
       [1;2;3;4;5] @ l2

in order to have the last elements periodically repeated.
In a list like this, I found that the map function goes in stack 
overflow. It seems that it is not aware of the recursive characteristics 
of the input list.
I had to write a version of the map function to support this in my 
software (I have to finalize something before posting it).

My questions are:
Can some functions of the List library support the use of the recursive 
lists?
I mean: can some scanning functions such as map, for_all, exists, mem, 
filter, and so on understand if they are working on recursive lists and 
act correctly without going in buffer overflow or infinite loops?
Did anyone already have a similar needing? And in which way did he/she work?

Thanks in advance to anyone

Luca


-- 
*********************************************************************
Luca Pascali
pasckosky2000@yahoo.it
luca@barettadeit.com
asxcaml-guru@barettadeit.com

http://www.barettadeit.com/
Baretta DE&IT
A division of Baretta SRL

tel. 02 370 111 55
fax. 02 370 111 54

Our technology:
http://www.asxcaml.org/
http://www.freerp.org/

-------------------
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] Recursive lists

[Keith Wansbrough]

> Can some functions of the List library support the use of the recursive 
> lists?
> I mean: can some scanning functions such as map, for_all, exists, mem, 
> filter, and so on understand if they are working on recursive lists and 
> act correctly without going in buffer overflow or infinite loops?

How could they do this?  It's just a list; there's nothing special
about it, except that it has no end.

You might be able to do it by keeping a list of all the nodes you've 
visited, and using physical equality to check if you have already 
visited a node.  But it would be better to design a more appropriate 
data structure for your application, one for which such tricks are not 
needed.

What are you trying to do?

--KW 8-)

-------------------
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] Recursive lists

[Sébastien Furic]

Luca Pascali wrote:

> Hi everyone.
> 
> I have a little question about the recursive lists.
> In an application I needed to use a list composed by some elements 
> (placed in the head of the list) and recursive element, like
> 
> let rec_list =
>    let rec l2 = 100 :: l2 in
>       [1;2;3;4;5] @ l2
> 
> in order to have the last elements periodically repeated.
> In a list like this, I found that the map function goes in stack 
> overflow. It seems that it is not aware of the recursive characteristics 
> of the input list.
> I had to write a version of the map function to support this in my 
> software (I have to finalize something before posting it).
> 
> My questions are:
> Can some functions of the List library support the use of the recursive 
> lists?
> I mean: can some scanning functions such as map, for_all, exists, mem, 
> filter, and so on understand if they are working on recursive lists and 
> act correctly without going in buffer overflow or infinite loops?
> Did anyone already have a similar needing? And in which way did he/she 
> work?
> 
> Thanks in advance to anyone
> 
> Luca
> 
> 

  You can use lazy lists to solve the problem. A lazy list delivers its 
elements on demand so you can manipulate infinite lists safely provided 
you don't print their whole contents for instance...
  See http://caml.inria.fr/archives/200304/msg00280.html to see how to 
implement them (they're not present in the OCaml distribution).

  Sébastien.

-------------------
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] Recursive lists

[sejourne_kevin]

Luca Pascali wrote:
> Hi everyone.
> 
> I have a little question about the recursive lists.
> In an application I needed to use a list composed by some elements 
> (placed in the head of the list) and recursive element, like
> 
> let rec_list =
>    let rec l2 = 100 :: l2 in
>       [1;2;3;4;5] @ l2
> 
> in order to have the last elements periodically repeated.
> In a list like this, I found that the map function goes in stack 
> overflow. It seems that it is not aware of the recursive characteristics 
> of the input list.
> I had to write a version of the map function to support this in my 
> software (I have to finalize something before posting it).
> 
> My questions are:
> Can some functions of the List library support the use of the recursive 
> lists?
> I mean: can some scanning functions such as map, for_all, exists, mem, 
> filter, and so on understand if they are working on recursive lists and 
> act correctly without going in buffer overflow or infinite loops?
> Did anyone already have a similar needing? And in which way did he/she 
> work?
> 
> Thanks in advance to anyone
> 
> Luca
> 
> 

(** Take a list and connect the end on the beginning
    Copyright : Kévin ;)
*)
let cycle l =
   let rl= ref l in
   let rec go_fin = function
       [] -> invalid_arg "cycle:[] can't be !"
     | [x] as f -> Obj.set_field (Obj.repr f) 1 (Obj.repr !rl);l
     | x::reste-> go_fin reste
   in go_fin l
;;
I haven't test GC issu.

-------------------
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] Recursive lists

[skaller]

On Fri, 2004-10-08 at 23:31, Keith Wansbrough wrote:
> > Can some functions of the List library support the use of the recursive 
> > lists?

> How could they do this?  

> You might be able to do it by keeping a list of all the nodes you've 
> visited, and using physical equality to check if you have already 
> visited a node.

I use that technique to perform recursive descent
on acyclic graphs, which the recursive list is.

For a list with the cycle *known* to be length 1,
this is very cheap, since you only need to compare
against previous element.

You can also use lazy evaluation.

An example of a stream (infinite list) being a *correct* 
data structure is a list of tokens with a cycle on 
the 'end of file' token.

Much easier to analyse with matches against substring
patterns .. since you don't have to worry about
the end of the list.

-- 
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] Recursive lists

[Alex Baretta]

Keith Wansbrough wrote:
> 
> How could they do this?  It's just a list; there's nothing special
> about it, except that it has no end.

Lists can be recursive. This means that the list type models a set of 
values which includes the cyclic lists. The ocaml type system allow both 
for such values and for functions manipulating them, so it's perfectly 
natural to expect the List module to treat cyclic lists correctly. 
Besides, the cyclicity of a list is a perfectly decidable property by 
virtue of the pumping lemma.

> You might be able to do it by keeping a list of all the nodes you've 
> visited, and using physical equality to check if you have already 
> visited a node.

Good point; however, we must keep a list of tails of visited nodes. 
Physical equality of nodes is a necessary but insufficient condition for 
recursiveness. On the other hand, if two nodes of the list have the same 
tail, then we have proven that the list is cyclic.

> But it would be better to design a more appropriate 
> data structure for your application, one for which such tricks are not 
> needed.

There is no more appropriate data structure than a cyclic list to model 
a possibily infinite (cyclic) sequence of input data. Have you ever seen 
type schemas like the following:
# type 'a t = 'a -> 'a t;;
type 'a t = 'a -> 'a t
This is a perfectly sensible use of recursive data structures: there is 
no other way to model a type whose expanded representation is infinite.
type 'a t = 'a -> 'a -> 'a -> ...

> What are you trying to do?

We are modelling an optimization problem where a finite number of 
requests must be served, as efficiently as possible, from a possibly 
infinite set of instances of a finite number of classes of resources. 
Each resource class is modelled by a list element. The cyclicity of the 
resource list can be used to express no limits on the amount of 
resources available. Yet, the optimization program must know better than 
simply scan the list sequentially, or unsatisfiable constraint sets 
cannot be identified in finite time.

Our algorithm works now, so we do not depend on the availability of 
cyclic-list aware standard library. We are simply trying to point out 
that the current List module is very naif about infinite lists. I would 
like to start a discussion as to whether the List module ought to 
correctly handle cyclic lists or not. I argue that since they are 
legimitate citizens of the language, the standard library should handle 
them correctly. We are willing to contribute our code, so that this 
might not weigh on the Caml breeders.

Alex

-------------------
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] Recursive lists

[Alex Baretta]

Sébastien Furic wrote:
> 
>  You can use lazy lists to solve the problem. A lazy list delivers its 
> elements on demand so you can manipulate infinite lists safely provided 
> you don't print their whole contents for instance...
>  See http://caml.inria.fr/archives/200304/msg00280.html to see how to 
> implement them (they're not present in the OCaml distribution).
> 
>  Sébastien.

Lazy lists or streams are not good enough in the general scenario. We 
don't need to exhaustively explore the cyclic data structures. The 
properties we are interested in can be proven in finite time by 
analyzing the list structure with the physical equality operator.

Alex

-------------------
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] Recursive lists

[Jon Harrop]

On Friday 08 October 2004 15:44, Alex Baretta wrote:
> Lazy lists or streams are not good enough in the general scenario. We 
> don't need to exhaustively explore the cyclic data structures.

Yes.

> The 
> properties we are interested in can be proven in finite time by
> analyzing the list structure with the physical equality operator.

No. I think you'll want "physical comparison operators" to do this 
efficiently, e.g. to build a set of visited nodes, otherwise you'll have to 
loop through all the possible ones giving you a search complexity of O(n) 
instead of O(ln n).

As "physical comparison operators" don't exist, I think you'd be better off 
using a directed cyclic graph with the notion of "physical" replaced with a 
notion of "index", so you number the nodes. Then you can build a set of 
visited nodes and search it to check for cyclic bits.

> I argue that since they are
> legimitate citizens of the language, the standard library should handle
> them correctly. We are willing to contribute our code, so that this
> might not weigh on the Caml breeders.

IMHO, this should certainly not go in the core library. These functions are 
much more specialised that the current code and are likely to be 
significantly slower. Perhaps the library documentation should state which 
functions assume a non-cyclic list.

Also, I'd be surprised if the required functionality didn't already exist in a 
graph library, although perhaps not specialized to one root and one edge out 
of each vertex.

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] Recursive lists

[james woodyatt]

On 08 Oct 2004, at 07:05, Sébastien Furic wrote:
> Luca Pascali wrote:
>> Can some functions of the List library support the use of the 
>> recursive lists?
>> I mean: can some scanning functions such as map, for_all, exists, 
>> mem, filter, and so on understand if they are working on recursive 
>> lists and act correctly without going in buffer overflow or infinite 
>> loops?
>> Did anyone already have a similar needing? And in which way did 
>> he/she work?
>> Thanks in advance to anyone
>> Luca
>
>  You can use lazy lists to solve the problem. A lazy list delivers its 
> elements on demand so you can manipulate infinite lists safely 
> provided you don't print their whole contents for instance...
>  See http://caml.inria.fr/archives/200304/msg00280.html to see how to 
> implement them (they're not present in the OCaml distribution).

My Cf library (in the OCNAE project on SF.Net) contains a full suite of 
functions for constructing and manipulating lazy lists (the Cf_seq 
module).  It also contains lots of other goodies.  The code has BSD 
license, is documented with Ocamldoc, and has no dependencies on 
anything other than Markus Mottl's Ocamlfind (for building and 
installing).

	<http://sf.net/projects/ocnae/>

(Note: you can even print the contents of an infinite lazy list if it's 
the last thing your program does before it receives SIGINT or SIGTERM, 
e.g. when printing to a pipe connected to the input of another 
program.)


-- 
j h woodyatt <jhw@wetware.com>
markets are only free to the people who own them.
-------------------
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] Recursive lists

[David Brown]

On Fri, Oct 08, 2004 at 04:42:44PM +0200, Alex Baretta wrote:
> Keith Wansbrough wrote:
> >
> >How could they do this?  It's just a list; there's nothing special
> >about it, except that it has no end.
> 
> Lists can be recursive. This means that the list type models a set of 
> values which includes the cyclic lists. The ocaml type system allow both 
> for such values and for functions manipulating them, so it's perfectly 
> natural to expect the List module to treat cyclic lists correctly. 
> Besides, the cyclicity of a list is a perfectly decidable property by 
> virtue of the pumping lemma.

I doubt that most users of list operations want the extra overhead needed
to check for cycles.  Recursive lists are fairly rare in strict languages.

Dave

-------------------
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] Recursive lists

[Wolfgang Lux]

Alex Baretta wrote:

> Lists can be recursive. This means that the list type models a set of 
> values which includes the cyclic lists. The ocaml type system allow 
> both for such values and for functions manipulating them, so it's 
> perfectly natural to expect the List module to treat cyclic lists 
> correctly.

IMHO it is absolutely not natural to expect this in a language with 
eager
evaluation. After all, a cyclic list is semantically equivalent to an 
infinite
value, i.e., it is equivalent to bottom. And we all know that f bottom 
= bottom
in a strict language.

In addition, have a look at the manual which clearly states (Sect. 
6.7.1) that
the behavior of let rec for non-functional values like
   let rec l2 = 100 :: l2
is implementation dependent.

Regards
Wolfgang

-------------------
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] Recursive lists

[Alex Baretta]

David Brown wrote:
> On Fri, Oct 08, 2004 at 04:42:44PM +0200, Alex Baretta wrote:
> 
>>Keith Wansbrough wrote:
> 
> I doubt that most users of list operations want the extra overhead needed
> to check for cycles.  Recursive lists are fairly rare in strict languages.

I agree. They are very rarely of any use.

> Dave

I agree. I would not want the overhead in general, unless I knew 
beforehand that cyclic list are possible. But this is an optimization we 
can count on so long as we can prove the invariant that our structures 
are not cyclic. This is obvious in the core language (no Obj), but might 
not be so if functions linke cycle are available. When the invariant 
cannot be proven valid for all meaningful input, or when it is known 
that the input can reasonably be cyclic, then I argue that the standard 
library should provide some means to manipulate the such structures 
safely. Of course, a separate Cyclic_list module could be defined to 
access the cyclic-safe functions, but from an abstract point of view 
such functions logically belong to List.

Alex

-------------------
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] Recursive lists

[Alex Baretta]

sejourne_kevin wrote:

> 
> (** Take a list and connect the end on the beginning
>    Copyright : Kévin ;)
> *)
> let cycle l =
>   let rl= ref l in
>   let rec go_fin = function
>       [] -> invalid_arg "cycle:[] can't be !"
>     | [x] as f -> Obj.set_field (Obj.repr f) 1 (Obj.repr !rl);l
>     | x::reste-> go_fin reste
>   in go_fin l
> ;;
> I haven't test GC issu.
> 

Nice code. So clean. So idiomatic. So type-safe... Well, it's really 
this Obj stuff is the best we can do with the current intuition of 
recursive values implemented in the Ocaml compiler.

Let me suggest a slightly safer version:

let cycle l =
   let l = List.rev (List.rev l) in
   let rl= ref l in
   let rec go_fin = function
       [] -> invalid_arg "cycle:[] can't be !"
     | [x] as f -> Obj.set_field (Obj.repr f) 1 (Obj.repr !rl);
     | x::reste-> go_fin reste
   in go_fin l

This first duplicates the original list so that aliasing is not an issue.

BTW, I've just discovered that List.append is safe with respect to an 
infinite second argurment, which is a totally desirable property. It is 
open to discussion as to whether append should analyze l1 for cyclicity

Alex

-------------------
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] Recursive lists

[skaller]

On Sat, 2004-10-09 at 03:19, Alex Baretta wrote:
> Of course, a separate Cyclic_list module could be defined to 
> access the cyclic-safe functions, but from an abstract point of view 
> such functions logically belong to List.

No they don't. List is an inductive data type,
and it is always finite. A data structure with
a cyclic pointer chain cannot represent a list.

A cyclic list is actually an instance of a 
coinductive data type, and this particular
one is called a stream.

In fact the List module is already *faulty*
because it supplies hd and tl, which are not
list operators at all -- they're the characteristic
functions of streams (just as Cons and Empty characterise
lists).

So there is actually a good argument for a Stream
module with hd and tl functions (and lazy map ..)

-- 
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] Recursive lists

[Keith Wansbrough]

Alex Baretta wrote:
> David Brown wrote:
> > On Fri, Oct 08, 2004 at 04:42:44PM +0200, Alex Baretta wrote:
> > 
> >>Keith Wansbrough wrote:
> > 
> > I doubt that most users of list operations want the extra overhead needed
> > to check for cycles.  Recursive lists are fairly rare in strict languages.

Please be careful with your attributions.  I did not write this
comment; David Brown did.  I do entirely agree, though.  And I
reiterate my earlier point - if you have an algorithm that uses a
potentially-cyclic datastructure and depends on detecting cycles, you
should build in some cycle-detection into the datastructure.  You
should not depend on fragile and underspecified operations like
pointer equality.

Alex, I didn't understand your earlier point about needing to compare
*tails* of visited nodes - why is just comparing nodes not sufficient?
Surely if two nodes compare physically equal, their tails must also be
equal.

--KW 8-)

-------------------
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] Recursive lists

[Keith Wansbrough]

> So there is actually a good argument for a Stream
> module with hd and tl functions (and lazy map ..)

Even lazy map shouldn't do cycle-detection, though: I would expect a
cyclic stream to be mapped to an infinite one.

--KW 8-)

-------------------
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] Recursive lists

[skaller]

On Sat, 2004-10-09 at 18:35, Keith Wansbrough wrote:
> > So there is actually a good argument for a Stream
> > module with hd and tl functions (and lazy map ..)
> 
> Even lazy map shouldn't do cycle-detection, though: I would expect a
> cyclic stream to be mapped to an infinite one.

Yes, what I meant was that for a data type s:'a stream,
and a function f: 'a -> 'b, the function

	map f s : 'b stream

creates a new stream represented by the pair

	(f,s)

with hd (f,s) = f (hd s). In other words, the map is only
applied when you fetch an element.

-- 
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] Recursive lists

[Brian Hurt]

Sorry for the late reply.

On Fri, 8 Oct 2004, Keith Wansbrough wrote:

> 
> > Can some functions of the List library support the use of the recursive 
> > lists?
> > I mean: can some scanning functions such as map, for_all, exists, mem, 
> > filter, and so on understand if they are working on recursive lists and 
> > act correctly without going in buffer overflow or infinite loops?
> 
> How could they do this?  It's just a list; there's nothing special
> about it, except that it has no end.

You can detect circular lists in O(N) thusly:

let is_circular lst =
    let rec loop p1 p2 =
        match p1, p2 with
            | (a :: t1), (b :: c :: t2) ->
                if (a == b) || (a == c) then
                    true
                else
                    loop t1 t2
            | _ -> false
    in
    match lst with
        | _ :: t -> loop lst t
        | [] -> false
;;

let circular_part lst =
    let rec find_an_element p1 p2 =
       (* find an element in the circular part of the list *)
       match p1, p2 with
           | (a :: t1), (b :: c :: t2) ->
               if (a == b) || (a == b) then
                   p1
               else
                   find_and_element t1 t2
           | _ -> []
    in
    let find_circular_length lst =
        (* find the number of elements in the circular part of the list *)
        let rec loop c p =
            if lst == p then 
                c
            else
                match p with
                    | _ :: t -> loop (c+1) t
                    | [] -> 0
        in
        match lst with
            | _ :: t -> loop 1 t
            | [] -> 0
    in
    let rec nth_tail cnt lst =
        if cnt == 0 then
            lst
        else
            nth_tail (cnt-1) (List.tl lst)
    in
    let rec find_loop p1 p2 =
        if (p1 == p2) then
            p1
        else
            find_loop (List.tl p1) (List.tl p2)
    in
    match lst with
        | [] -> []
        | _ :: t ->
            match find_an_elem lst t with
                | [] -> []
                | cirelem ->
                   let cirlen = find_circular_length cirelem in
                   let p = nth_tail cirlen lst in
                   find_loop lst p
;;

Note: I haven't tested the above functions, but they give you the idea of 
how to handle circular lists.

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

Re: [Caml-list] Recursive lists

[William Lovas]

On Sun, Oct 10, 2004 at 07:44:25PM -0500, Brian Hurt wrote:
> You can detect circular lists in O(N) thusly:
> 
> let is_circular lst =
>     let rec loop p1 p2 =
>         match p1, p2 with
>             | (a :: t1), (b :: c :: t2) ->
>                 if (a == b) || (a == c) then
>                     true
>                 else
>                     loop t1 t2
>             | _ -> false
>     in
>     match lst with
>         | _ :: t -> loop lst t
>         | [] -> false
> ;;

# is_circular [true; true; true];;
- : bool = true

> [...]
>
> Note: I haven't tested the above functions, but they give you the idea of 
> how to handle circular lists.

... and this isn't it :)  I think Alex was more on the right track with the
idea of maintaining a list of tails...

cheers,
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] Recursive lists

[Ville-Pertti Keinonen]

William Lovas wrote:

>On Sun, Oct 10, 2004 at 07:44:25PM -0500, Brian Hurt wrote:
>  
>
>>You can detect circular lists in O(N) thusly:
>>
>>let is_circular lst =
>>    let rec loop p1 p2 =
>>        match p1, p2 with
>>            | (a :: t1), (b :: c :: t2) ->
>>                if (a == b) || (a == c) then
>>                    true
>>                else
>>                    loop t1 t2
>>            | _ -> false
>>    in
>>    match lst with
>>        | _ :: t -> loop lst t
>>        | [] -> false
>>;;
>>    
>>
>
># is_circular [true; true; true];;
>- : bool = true
>  
>
This can be fixed by comparing the list node pointers rather than the 
contents.  I'm sure Brian meant the match in the above to look like:

match p1, p2 with
  | (_ :: t1), (_ :: (_ :: t2) as p3) ->
    if p1 == p2 or p1 == p3 then
      true
    else
      loop t1 t2
  | _ -> false

>... and this isn't it :)  I think Alex was more on the right track with the
>idea of maintaining a list of tails...
>  
>
There's no need for such a thing, at least for determining circularity, 
the "tortoise and hare" algorithm is well-known and works just fine, as 
long as it's implemented correctly.

-------------------
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] Recursive lists

[Jean-Christophe Filliatre]

sejourne_kevin wrote:
> 
> (** Take a list and connect the end on the beginning
>    Copyright : Kévin ;)
> *)
> let cycle l =
>   let rl= ref l in
>   let rec go_fin = function
>       [] -> invalid_arg "cycle:[] can't be !"
>     | [x] as f -> Obj.set_field (Obj.repr f) 1 (Obj.repr !rl);l
>     | x::reste-> go_fin reste
>   in go_fin l
> ;;
> I haven't test GC issu.

This shouldn't be advised, and not even posted on this list.

This main property of Ocaml's lists is to be _immutable_ and therefore
to  implement a  _persistent_ data  type. This  is full  of  very nice
consequences  for the  programmer.  (Read  Okasaki's book  or previous
posts on this list explaining what persistence is.)

But  if you  start mutating  lists, you  break this  property  and you
endanger your code.  If you need to mutate lists, why  don't you use a
mutable  data  structure,  such  as regular  (mutable)  chained  lists
exactly as  in traditional  imperative programming? (See  for instance
Ocaml's Queue implementation.)

-- 
Jean-Christophe Filliâtre (http://www.lri.fr/~filliatr)

PS: 

If you read French, I have an ocaml tutorial on my web page I recently
wrote for students,  where a chapter is dedicated  to persistence: see
http://www.lri.fr/~filliatr/publis/ipf.ps.gz

This  is a  rather modest  contribution (compared  to  Richard Jones's
tutorial for instance)  and it does not even  describe all features of
ocaml, but at least it explains why you shouldn't mutate lists.

-------------------
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] Recursive lists

[Keith Wansbrough]

> On Fri, 8 Oct 2004, Keith Wansbrough wrote:
[..]
> > How could they do this?  It's just a list; there's nothing special
> > about it, except that it has no end.
> 
> You can detect circular lists in O(N) thusly:
> 
> let is_circular lst =

Yes, of course (and this is quite neat - I knew there was a
reasonable-space algorithm but couldn't recall it off the top of my
head).  But this is hardly something you want built into List.map and
List.fold_{left,right}.  (as others have pointed out)

--KW 8-)

-------------------
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] Recursive lists

[Diego Olivier Fernandez Pons]

    Bonjour,

> This shouldn't be advised, and not even posted on this list.

I even think that it is a mistake of some libraries (namely ExtLib) to
give handling functions for mutable lists via the Obj module just to
win a few seconds on typical data.


        Diego Olivier

-------------------
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] About Obj (was Recursive lists)

[Christophe Raffalli]

[-- Attachment #1: Type: text/plain, Size: 2865 bytes --]

Jean-Christophe Filliatre wrote:
> sejourne_kevin wrote:
> 
>>(** Take a list and connect the end on the beginning
>>   Copyright : Kévin ;)
>>*)
>>let cycle l =
>>  let rl= ref l in
>>  let rec go_fin = function
>>      [] -> invalid_arg "cycle:[] can't be !"
>>    | [x] as f -> Obj.set_field (Obj.repr f) 1 (Obj.repr !rl);l
>>    | x::reste-> go_fin reste
>>  in go_fin l
>>;;
>>I haven't test GC issu.
> 
> 
> This shouldn't be advised, and not even posted on this list.
> 

And how do you write a tail recursive map doing only one structure 
traversal (which is important with the penalty for memory access) on 
immutable list without the Obj module ?

However, using Obj you can write once for all some functions to 
construct a list starting with its head, for instance with the following 
interface (you can write an implmentation with Stack but the "extract" 
function will not be in constant time):

type 'a prelist (* mutable type of a list under construction *)

val start : unit -> 'a prelist
val extract : 'a prelist -> 'a list
val cons : 'a -> 'a prelist -> unit

Then, map can be rewritten

let map f l =
   let pl = start () in
   let rec fn = function
     [] -> extract pl
   | a::l -> cons (f a) pl; fn l
   in
   fn l

This kind of code is not that intolerable and you can advise people to 
use Obj module to write an implementation of the above signature (if 
they are sure they really need it).
Since use of the Obj module is restricted to a small module, it will be 
easy to adapt to follow the evolution of the language.

The presence of the Obj module in the standard distribution itself tells 
that it is necessary and not only for C interface (this is not its main 
usage anyway, its main usage is to compile code typable only with 
dependent type).

Here is a possible implementation of the above module (I think it could 
be use to improve the actual implementation of map and fold_right in the 
standard library)

type 'a prelist = { mutable start : 'a list; mutable current : 'a list}

let start () = { start = []; current = []}

let cons a pl = match pl.current with
   [] -> let l = [a] in pl.current <- l; pl.start <- l
| l ->
	let l' = [a] in Obj.set_field (Obj.repr l) 1 (Obj.repr l');
         pl.current <- l'

let extract pl =
   let r = pl.start in
   pl.current <- []; pl.start <- [];
   (* to guaranty that we can not mute the list once it has been
   extracted *)
   r

-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature
---------------------------------------------

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

[Caml-list] Re: About Obj (was Recursive lists)

[Christophe Raffalli]

[-- Attachment #1: Type: text/plain, Size: 762 bytes --]


> Here is a possible implementation of the above module (I think it could 
> be use to improve the actual implementation of map and fold_right in the 
> standard library)

Let me correct my statement: it could be used after some improvment, 
because it is two times slower on small lists (after some timing)


-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature
---------------------------------------------

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

Re: [Caml-list] About Obj (was Recursive lists)

[Jon Harrop]

On Monday 11 October 2004 14:38, Christophe Raffalli wrote:
> Jean-Christophe Filliatre wrote:
> > This shouldn't be advised, and not even posted on this list.

Yes, why is "Brandon" in the filter but "Obj" isn't? :-)

> And how do you write a tail recursive map doing only one structure
> traversal (which is important with the penalty for memory access) on
> immutable list without the Obj module?

You avoid the use of Obj magic at all costs! Then you are much more likely to 
get programs which work. Finally, you optimise them in terms of what you can 
do in the language.

> Let me correct my statement: it could be used after some improvment,
> because it is two times slower on small lists (after some timing)

Yes, your Obj implementation is substantially bigger, more complicated, more 
error prone and more costly on small lists. Just forget this whole thread 
ever happened and consider using a different data structure. :-)

Can Obj not be hidden so that people can't use it so easily?

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] About Obj (was Recursive lists)

[Richard Jones]

[-- Attachment #1: Type: text/plain, Size: 615 bytes --]

On Mon, Oct 11, 2004 at 04:33:03PM +0100, Jon Harrop wrote:
> Can Obj not be hidden so that people can't use it so easily?

Nooo!!! If I wanted a language which saved me from myself, I'd be
using Java ...

Rich.

-- 
Richard Jones. http://www.annexia.org/ http://www.j-london.com/
Merjis Ltd. http://www.merjis.com/ - improving website return on investment
MONOLITH is an advanced framework for writing web applications in C, easier
than using Perl & Java, much faster and smaller, reusable widget-based arch,
database-backed, discussion, chat, calendaring:
http://www.annexia.org/freeware/monolith/

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] About Obj (was Recursive lists)

[james woodyatt]

On 11 Oct 2004, at 06:38, Christophe Raffalli wrote:
> Jean-Christophe Filliatre wrote [quite sensibly]:
>>
>> [...]
>> This shouldn't be advised, and not even posted on this list.
>
> And how do you write a tail recursive map doing only one structure 
> traversal (which is important with the penalty for memory access) on 
> immutable list without the Obj module ?

By using a more appropriate data structure, e.g. a lazy list.  It's a 
pay-me-now-or-pay-me-later sort of game you're playing here.

Rather than whack on the immutable list, maybe you should consider 
doing this:

	type 'a mlist = N | C of 'a mcell
	and 'a mcell = { mutable cdr: 'a; mutable car: 'a mlist }

No need to thank me.


-- 
j h woodyatt <jhw@wetware.com>
markets are only free to the people who own them.

-------------------
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] About Obj

[Yamagata Yoriyuki]

From: Jon Harrop <jon@jdh30.plus.com>
Subject: Re: [Caml-list] About Obj (was Recursive lists)
Date: Mon, 11 Oct 2004 16:33:03 +0100

> Yes, your Obj implementation is substantially bigger, more complicated, more 
> error prone and more costly on small lists. Just forget this whole thread 
> ever happened and consider using a different data structure. :-)
> 
> Can Obj not be hidden so that people can't use it so easily?

Yes, it would be nice to have a compiler option which disable all
causes of the evil (Obj.magic, Array.unsafe_get, external etc).  Then
we can control where unsafe operations are used.
--
Yamagata Yoriyuki


-------------------
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] About Obj (was Recursive lists)

[brogoff]

On Mon, 11 Oct 2004, james woodyatt wrote:
> On 11 Oct 2004, at 06:38, Christophe Raffalli wrote:
> > Jean-Christophe Filliatre wrote [quite sensibly]:
> >>
> >> [...]
> >> This shouldn't be advised, and not even posted on this list.
> >
> > And how do you write a tail recursive map doing only one structure
> > traversal (which is important with the penalty for memory access) on
> > immutable list without the Obj module ?
>
> By using a more appropriate data structure, e.g. a lazy list.  It's a
> pay-me-now-or-pay-me-later sort of game you're playing here.

Count me among those entirely unswayed by this.

You could also respectfully request that the implementors provide a safe
way to get this well known optimization WITHOUT having to resort to Obj
usage, and, until it is provided, use the safe solution provided a few times
already (and used in ExtLib I believe).

When I asked one of the implementors about this, I received the response that
this would be nice to have but not at the head of the queue in terms of
upcoming desireable features. That seems like a reasonable response, considering
that there are a number of not so bad workarounds, including use of Obj. I'd
rather have GCaml extensions sooner anyways...

I think Clean now provides some solution for the tail recursion modulo cons
stuff. Anyone know other language/implementations which do?

-- 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] About Obj (was Recursive lists)

[james woodyatt]

On 11 Oct 2004, at 09:46, brogoff wrote:
> On Mon, 11 Oct 2004, james woodyatt wrote:
>> On 11 Oct 2004, at 06:38, Christophe Raffalli wrote:
>>> Jean-Christophe Filliatre wrote [quite sensibly]:
>>>>
>>>> [...]
>>>> This shouldn't be advised, and not even posted on this list.
>>>
>>> And how do you write a tail recursive map doing only one structure
>>> traversal (which is important with the penalty for memory access) on
>>> immutable list without the Obj module ?
>>
>> By using a more appropriate data structure, e.g. a lazy list.  It's a
>> pay-me-now-or-pay-me-later sort of game you're playing here.
>
> Count me among those entirely unswayed by this.
>
> You could also respectfully request that the implementors provide a 
> safe
> way to get this well known optimization WITHOUT having to resort to Obj
> usage [...]

Okay.  It's a pay-now-pay-later-or-pay-INRIA sort of game.  <smile/>

Yes, it would be nice to have tail-recursion-modulo-cons.  It's not 
killing me to have to wait for it though-- a lazy list does the job 
nicely for me.  However, you can count me as one of the people who 
would like to see this and GCaml be the main features of OCaml 3.09.


-- 
j h woodyatt <jhw@wetware.com>
markets are only free to the people who own them.

-------------------
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] About Obj (was Recursive lists)

[skaller]

On Tue, 2004-10-12 at 03:24, james woodyatt wrote:
> On 11 Oct 2004, at 09:46, brogoff wrote:

>  However, you can count me as one of the people who 
> would like to see this and GCaml be the main features of OCaml 3.09.

Well I'd like to see a variable length array.

In this the choice of data structure may be a performance 
or convenience issue, but having made that choice
an implementation without magic is impossible.

The requirement is to construct such an array starting
at length zero and append elements as required
which  can't be done in a GC safe way without magic 
and knowledge of implementation details.

-- 
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] Recursive lists

[sejourne_kevin]

Jean-Christophe Filliatre wrote:
> sejourne_kevin wrote:
> 
>>(** Take a list and connect the end on the beginning
>>   Copyright : Kévin ;)
>>*)
>>let cycle l =
>>  let rl= ref l in
>>  let rec go_fin = function
>>      [] -> invalid_arg "cycle:[] can't be !"
>>    | [x] as f -> Obj.set_field (Obj.repr f) 1 (Obj.repr !rl);l
>>    | x::reste-> go_fin reste
>>  in go_fin l
>>;;
>>I haven't test GC issu.
> 
> 
> This shouldn't be advised, and not even posted on this list.
> 
> This main property of Ocaml's lists is to be _immutable_ and therefore
> to  implement a  _persistent_ data  type. This  is full  of  very nice
> consequences  for the  programmer.  (Read  Okasaki's book  or previous
> posts on this list explaining what persistence is.)
> 
> But  if you  start mutating  lists, you  break this  property  and you
> endanger your code.  If you need to mutate lists, why  don't you use a
> mutable  data  structure,  such  as regular  (mutable)  chained  lists
> exactly as  in traditional  imperative programming? (See  for instance
> Ocaml's Queue implementation.)
> 
With the modification of Alex Baretta this function can be be view as 
returning a _new_ list. So the list is immutable. When I right this 
function it was for _fun_. So if Obj don't exist I use a C primitive.

I can have a cycle using '[]' and '::' syntaxe this a great thing.
I think a improvement for Ocaml3.09 that allow
let ([]) = ...  and (::) = ...
is a better way and simpler.


-------------------
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] About Obj (was Recursive lists)

[Christophe Raffalli]

james woodyatt wrote:
> On 11 Oct 2004, at 06:38, Christophe Raffalli wrote:
> 
>> Jean-Christophe Filliatre wrote [quite sensibly]:
>>
>>>
>>> [...]
>>> This shouldn't be advised, and not even posted on this list.
>>
>>
>> And how do you write a tail recursive map doing only one structure 
>> traversal (which is important with the penalty for memory access) on 
>> immutable list without the Obj module ?
> 
> 
> By using a more appropriate data structure, e.g. a lazy list.  It's a 
> pay-me-now-or-pay-me-later sort of game you're playing here.
> 
> Rather than whack on the immutable list, maybe you should consider doing 
> this:
> 
>     type 'a mlist = N | C of 'a mcell
>     and 'a mcell = { mutable cdr: 'a; mutable car: 'a mlist }

This data structure uses 5 words and 2 indirection per cons cell 
(instead of 3 and 1 for standard list). So it will be slower on all 
operations. Moreover you may want immutable list with tail recursive and 
  one mono-traversal map and fold_right.




-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature
---------------------------------------------

-------------------
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] Recursive lists

[Alex Baretta]

William Lovas wrote:
> On Sun, Oct 10, 2004 at 07:44:25PM -0500, Brian Hurt wrote:

>>
>>Note: I haven't tested the above functions, but they give you the idea of 
>>how to handle circular lists.
> 
> 
> ... and this isn't it :)  I think Alex was more on the right track with the
> idea of maintaining a list of tails...
> 
> cheers,
> William

Exactly: physical equality of nodes has nothing to do with the physical 
equality of lists. Ocaml allows sharing, so the same object can appear 
in more than one position even in an ordinary list or in any other Ocaml 
datastructure.

e.g.

let l =
   let x = <...> in
   let y = <...> in
     [x; y; y; x; ...]

Here the first and fourth element are physically equal, as well as the 
second and third.

Alex

-------------------
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] Recursive lists

[Alex Baretta]

Ville-Pertti Keinonen wrote:
> William Lovas wrote:
> 
>> On Sun, Oct 10, 2004 at 07:44:25PM -0500, Brian Hurt wrote:
>>
> This can be fixed by comparing the list node pointers rather than the 
> contents.  I'm sure Brian meant the match in the above to look like:
> 
> match p1, p2 with
>  | (_ :: t1), (_ :: (_ :: t2) as p3) ->
>    if p1 == p2 or p1 == p3 then
>      true
>    else
>      loop t1 t2
>  | _ -> false
> 
>> ... and this isn't it :)  I think Alex was more on the right track 
>> with the
>> idea of maintaining a list of tails...
>>  
>>
> There's no need for such a thing, at least for determining circularity, 
> the "tortoise and hare" algorithm is well-known and works just fine, as 
> long as it's implemented correctly.

You can't say that there is no need for it. Think of a monadic 
composition of this algorithm with a list traversal which actually gets 
some work done. The need to maintain the list of tails appears in this 
context, where I know that only *some tails* are worth stacking into the 
cycle detection list, depending on the result of processing the single node.

Besides the tortoise and hare algorithm is not really any better than 
mine, at least in terms of asymptotic worst case complexity, except that 
it allocates less.

Alex

-------------------
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] About Obj (was Recursive lists)

[Alex Baretta]

james woodyatt wrote:
me-now-or-pay-me-later sort of game you're playing here.
> 
> Rather than whack on the immutable list, maybe you should consider doing 
> this:
> 
>     type 'a mlist = N | C of 'a mcell
>     and 'a mcell = { mutable cdr: 'a; mutable car: 'a mlist }
> 
> No need to thank me.

This point of view is simply wrong. We use immutable lists, which can be 
infinite. This data structure, or I should say this module interface, 
perfectly models our program's needs. However, as I discussed with 
Xavier, we must guarantee that the algorithm which scans this list will, 
at some point terminate, whether the list is finite or not. This can be 
done because cycle detection is decidable and it's complexity in 
realistic scenarios (ours, as far as I'm concerned) is O(1), the 
constant complexity being achieved through the tail-stacking algorithm 
which only stacks a small number of nodes, number which is indipendent 
of the problem size.

The need for a List (or Cyclic_list) module encapsulating the 
abstraction of a cyclic list emerges when we try to build an input 
data-structure to feed our algorithm. The use of Obj within a specific 
module is perfectly acceptable so long as it is needed to implement 
functionality which cannot be achieved in the core language. The example 
of the tail recursive implementation of List.map is pertinent, and shows 
the point.

You might have noticed that Caml breeders use Obj fairly liberally when 
it is needed to achieve a higher of abstraction which cannot be modeled 
in the core language.

Alex

-------------------
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] About Obj

[Alex Baretta]

Yamagata Yoriyuki wrote:
> From: Jon Harrop <jon@jdh30.plus.com>
> Subject: Re: [Caml-list] About Obj (was Recursive lists)
> Date: Mon, 11 Oct 2004 16:33:03 +0100
> 
> 
>>Yes, your Obj implementation is substantially bigger, more complicated, more 
>>error prone and more costly on small lists. Just forget this whole thread 
>>ever happened and consider using a different data structure. :-)
>>
>>Can Obj not be hidden so that people can't use it so easily?
> 
> 
> Yes, it would be nice to have a compiler option which disable all
> causes of the evil (Obj.magic, Array.unsafe_get, external etc).  Then
> we can control where unsafe operations are used.
> --
> Yamagata Yoriyuki



Your proposal is reasonable and sound; however, I really think Xavier 
has more important stuff to do. Consider the following issues:
1) Your request cannot be satisfied in general because you'd never dream 
of disabling the use of Obj in the standard library.
2) You can easily achieve the same behavior by using camlp4 or possibly 
a custom preprocessor which throughs an extension upon identifying calls 
to the Obj module.



Alex

-------------------
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] About Obj (was Recursive lists)

[brogoff]

On Wed, 13 Oct 2004, Alex Baretta wrote:
> The need for a List (or Cyclic_list) module encapsulating the
> abstraction of a cyclic list emerges when we try to build an input
> data-structure to feed our algorithm. The use of Obj within a specific
> module is perfectly acceptable so long as it is needed to implement
> functionality which cannot be achieved in the core language. The example
> of the tail recursive implementation of List.map is pertinent, and shows
> the point.

I remembered shortly after I asked that Alice ML also provides a way to handle
these tail recursive (modulo cons) functions by providing a library for
Prologish logical variables called "promises" in that dialect. Neat idea, and
useful for more than tail recursive lists, but I wonder how efficient the
implementations are.

> You might have noticed that Caml breeders use Obj fairly liberally when
> it is needed to achieve a higher of abstraction which cannot be modeled
> in the core language.

Good point, but I hope every Caml fan accepts these uses as being neccesary
compromises of the moment that can one day be eliminated by a stronger core
language.

-- 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] About Obj (was Recursive lists)

[Andreas Rossberg]

brogoff wrote:
> 
> I remembered shortly after I asked that Alice ML also provides a way to handle
> these tail recursive (modulo cons) functions by providing a library for
> Prologish logical variables called "promises" in that dialect. Neat idea, and
> useful for more than tail recursive lists, but I wonder how efficient the
> implementations are.

Promises surely would be overkill for just tail recursion. And I'm 
afraid that the general overhead their presence introduces may well be 
larger than the bit of efficiency you can squeeze out by making List.map 
tail recursive. (It is similar to laziness, and Alice uses reflective 
just-in-time compilation to avoid redundant tests for promised values.)

Promises, and more generally futures, have been introduced for 
light-weight concurrent programming with implicit dataflow 
synchronisation. They enable coding all kinds of concurrency 
abstractions. You can also use promises to e.g. construct data 
structures top-down (of which tail recursive map or append functions are 
simple instances), but that rather is a neat side effect and not their 
primary motivation.

	- Andreas

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

Let's get rid of those possible thingies!  -- TB

-------------------
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] About Obj (was Recursive lists)

[brogoff]

On Thu, 14 Oct 2004, Andreas Rossberg wrote:
> brogoff wrote:
> >
> > I remembered shortly after I asked that Alice ML also provides a way to handle
> > these tail recursive (modulo cons) functions by providing a library for
> > Prologish logical variables called "promises" in that dialect. Neat idea, and
> > useful for more than tail recursive lists, but I wonder how efficient the
> > implementations are.
>
> Promises surely would be overkill for just tail recursion. And I'm
> afraid that the general overhead their presence introduces may well be
> larger than the bit of efficiency you can squeeze out by making List.map
> tail recursive. (It is similar to laziness, and Alice uses reflective
> just-in-time compilation to avoid redundant tests for promised values.)
>
> Promises, and more generally futures, have been introduced for
> light-weight concurrent programming with implicit dataflow
> synchronisation. They enable coding all kinds of concurrency
> abstractions. You can also use promises to e.g. construct data
> structures top-down (of which tail recursive map or append functions are
> simple instances), but that rather is a neat side effect and not their
> primary motivation.

Thanks, I suspected as much, but wasn't sure. Alice looks like an interesting
language, but I suspect (given it's Mozart/Oz heritage) that the implementation
would appeal to me less than OCaml on performance and convenience issues.

I'd like to be able to write those list functions in the core language and have
performance equivalent to the Obj using versions or their equivalents. Nope,
not a huge annoyance given the workarounds (Obj, or a slower implementation
which has to reverse) but a "nice to have".  String and array size restrictions
are more annoying.

-- 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] About Obj (was Recursive lists)

[Alex Baretta]

brogoff wrote:
> On Wed, 13 Oct 2004, Alex Baretta wrote:

>>You might have noticed that Caml breeders use Obj fairly liberally when
>>it is needed to achieve a higher of abstraction which cannot be modeled
>>in the core language.
> 
> 
> Good point, but I hope every Caml fan accepts these uses as being neccesary
> compromises of the moment that can one day be eliminated by a stronger core
> language.
> 
> -- Brian

Not necessarily. You certainly don't mean to say that the C FFI is a 
necessary compromise to be removed one day? We already have a very 
strong core language, which is fully type safe. Extensions to this core 
language, library-wise, can be achieved by linking to C code or, 
depending on the application, to Obj-aware Ocaml libraries.

Apart from such extensions, which most of the core libraries build upon, 
no code should directly call C code or Obj code directly. This is the 
contract between the Caml and its riders.

Alex

-------------------
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] About Obj (was Recursive lists)

[brogoff]

On Fri, 15 Oct 2004, Alex Baretta wrote:
> > On Wed, 13 Oct 2004, Alex Baretta wrote:
>
> >>You might have noticed that Caml breeders use Obj fairly liberally when
> >>it is needed to achieve a higher of abstraction which cannot be modeled
> >>in the core language.
> >
> >
> brogoff wrote:
> > Good point, but I hope every Caml fan accepts these uses as being neccesary
> > compromises of the moment that can one day be eliminated by a stronger core
> > language.
> >
> > -- Brian
>
> Not necessarily. You certainly don't mean to say that the C FFI is a
> necessary compromise to be removed one day?

No. It's clear that when you're interfacing to C or any unsafe language that
you have to tolerate, well, unsafe features.

I am saying that there are places where the core language doesn't allow you to
express something which you'd like to express conveniently or at all.

A type system example is polymorphic recursion. Of course, you can handle it
easier since we got polymorphic methods and recursive mdules and all that, but
it is IMO just one of those things you want to be able to do easily. Using Obj
for this is repugnant, or at least, aesthetically deficient.

A non type system example might be laziness. "lazy" features are added to core
ML to make some kinds of programming more convenient. `

> We already have a very strong core language, which is fully type safe.

So, the core language should be frozen in its current state?

Is marshalling part of the core language? If so, then the core is not fully
type safe.

I like the fact that the language is undergoing a fairly slow (well, lightning
fast by SML standards!) evolution.

-- Brian

PS: "core" is overloaded in the ML world. I think when a lot of MLers talk about
the "core ML" they don't include the module system. When I speak of core Caml,
I mean something like Caml Special Light. ML means Modular Language in my
lexicon :-)

-------------------
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] About Obj (was Recursive lists)

[Alex Baretta]

brogoff wrote:
> On Fri, 15 Oct 2004, Alex Baretta wrote:
> 
> 
>>We already have a very strong core language, which is fully type safe.
> 
> 
> So, the core language should be frozen in its current state?

Most definitely not! I'm trying to point out that part of the evolution 
of Ocaml-as-a-tool depends on the evolution of its libraries, which by 
all means are entitled to make use of Obj and C-FFI, especially if the 
author, a typically professional Caml breeder, makes the effort of 
making the correctness proofs where the type-checker accepts code by a 
leap of faith.

> Is marshalling part of the core language? If so, then the core is not fully
> type safe.

The Marshal module is not really *core*. It's a hack worth having until 
the compiler will support type reflection to the extent of recognizing 
whether a marshalled module is or is not compatibile with the value 
being defined. Again, my point is that it's better to have an unsafe 
feature than not have the feature at all. I am one of those who complain 
with Xavier about marshalling, and I'm waiting for the revised 
implementation. But, meanwhile, with some care on my part, my software 
already compiles and runs.

Alex

-------------------
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] About Obj (was Recursive lists)

[Greg K]

GCaml? Are you saying that the GCaml extensions are in the INRIA queue for 
some future version of OCaml? I was under the impression that it had fallen 
off the active list when Jun Furuse left for Tokyo. Is that not true?

Greg

At 09:46 AM 10/11/2004, brogoff wrote:
>On Mon, 11 Oct 2004, james woodyatt wrote:
> > On 11 Oct 2004, at 06:38, Christophe Raffalli wrote:
> > > Jean-Christophe Filliatre wrote [quite sensibly]:
> > >>
> > >> [...]
> > >> This shouldn't be advised, and not even posted on this list.
> > >
> > > And how do you write a tail recursive map doing only one structure
> > > traversal (which is important with the penalty for memory access) on
> > > immutable list without the Obj module ?
> >
> > By using a more appropriate data structure, e.g. a lazy list.  It's a
> > pay-me-now-or-pay-me-later sort of game you're playing here.
>
>Count me among those entirely unswayed by this.
>
>You could also respectfully request that the implementors provide a safe
>way to get this well known optimization WITHOUT having to resort to Obj
>usage, and, until it is provided, use the safe solution provided a few times
>already (and used in ExtLib I believe).
>
>When I asked one of the implementors about this, I received the response that
>this would be nice to have but not at the head of the queue in terms of
>upcoming desireable features. That seems like a reasonable response, 
>considering
>that there are a number of not so bad workarounds, including use of Obj. I'd
>rather have GCaml extensions sooner anyways...
>
>I think Clean now provides some solution for the tail recursion modulo cons
>stuff. Anyone know other language/implementations which do?
>
>-- 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

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