How to compare infinite lists? 
Author Message
 How to compare infinite lists?

The recent thread on functional idioms for comparing finite arrays got
me thinking about the infinite case. To keep it simple, consider
comparing two infinite lists (in Haskell):

(cycle [3,4]) == (cycle [3,4])

Although the result should be true, the expression above never
terminates.  Is there any way at all to do such a test without resorting
to non-functional features (eg. pointer-equality)?

Thanks,

--
Louis.



Mon, 17 Mar 2003 08:24:07 GMT  
 How to compare infinite lists?

Quote:
> (cycle [3,4]) == (cycle [3,4])

> Although the result should be true, the expression above never
> terminates.  Is there any way at all to do such a test without
> resorting to non-functional features (eg. pointer-equality)?

No.

--

 \__/
  ^^                      SYGNATURA ZASTPCZA
QRCZAK



Mon, 17 Mar 2003 03:00:00 GMT  
 How to compare infinite lists?


Quote:
>> (cycle [3,4]) == (cycle [3,4])

>> Although the result should be true, the expression above never
>> terminates.  Is there any way at all to do such a test without
>> resorting to non-functional features (eg. pointer-equality)?

>No.

You could do it statically, at compile time, surely?

Cheers,

Nick.

--

Nick Williams
Software Engineer
Praxis Critical Systems Limited, Bath, UK



Mon, 17 Mar 2003 03:00:00 GMT  
 How to compare infinite lists?

Quote:

> (cycle [3,4]) == (cycle [3,4])
> Although the result should be true, the expression above never
> terminates.  Is there any way at all to do such a test without resorting
> to non-functional features (eg. pointer-equality)?

Well, I suppose you could rely on the compiler to infer that the two
expression are the same, and replace the test with 'True'.  Of course,
that would mean the behaviour of programs would change with different
compiler switches...

-kzm
--
If I haven't seen further, it is by standing in the footprints of giants



Mon, 17 Mar 2003 03:00:00 GMT  
 How to compare infinite lists?

Quote:
> >> (cycle [3,4]) == (cycle [3,4])

> >> Although the result should be true, the expression above never
> >> terminates.  Is there any way at all to do such a test without
> >> resorting to non-functional features (eg. pointer-equality)?

> >No.

> You could do it statically, at compile time, surely?

The language does not provide any mean for that.

--

 \__/
  ^^                      SYGNATURA ZASTPCZA
QRCZAK



Mon, 17 Mar 2003 03:00:00 GMT  
 How to compare infinite lists?


Quote:
>> (cycle [3,4]) == (cycle [3,4])
>> Although the result should be true, the expression above never
>> terminates.  Is there any way at all to do such a test without resorting
>> to non-functional features (eg. pointer-equality)?
>Well, I suppose you could rely on the compiler to infer that the two
>expression are the same, and replace the test with 'True'.  Of course,
>that would mean the behaviour of programs would change with different
>compiler switches...

Oh, no, please let's not go _there_ /again/...

Nick.

--

Nick Williams
Software Engineer
Praxis Critical Systems Limited, Bath, UK



Mon, 17 Mar 2003 03:00:00 GMT  
 How to compare infinite lists?

Quote:

> The recent thread on functional idioms for comparing finite arrays got
> me thinking about the infinite case. To keep it simple, consider
> comparing two infinite lists (in Haskell):

> (cycle [3,4]) == (cycle [3,4])

> Although the result should be true, the expression above never
> terminates.  Is there any way at all to do such a test without
> resorting to non-functional features (eg. pointer-equality)?

Pointer equality won't help - the two calls to 'cycle' could easily
return different objects, depending on the implementation.

Actually it's undecidable if you allow arbitrary functions on at least
one of the sides of the equality operator, because then the equality
operator could be used to solve the halting problem.

Proof sketch:
Assume this scenario,
  (cycle [0]) == number_of_steps (lazy a)
where 'number_of_steps' is the number of steps that 'a' needs to
evaluate, encoded with as many zeroes as there are evaluation steps and
a final 1.
The result of the expression will be False if 'a' can be evaluated in a
finite number of steps, True otherwise.

Of course, it might be possible to built a lot of heuristics into == to
solve the majority of questions. But even with nonrecursive function you
can get into {*filter*} exponential behaviour. For example, you could use
this equality to write down a function to test for equivalence of
boolean terms; that's a "hard" problem: there's no known algorithm that
does better than O(exp(number of free variables)). In fact finding such
an algorithm would be a major breakthrough (it would also immediately
give a non-exponential algorithm for all "hard" problems, such as the
Travelling Salesman or Breaking RSA).

Regards,
Joachim
--
This is not an official statement from my employer or from NICE.



Mon, 17 Mar 2003 03:00:00 GMT  
 How to compare infinite lists?

Quote:


> > The recent thread on functional idioms for comparing finite arrays got
> > me thinking about the infinite case. To keep it simple, consider
> > comparing two infinite lists (in Haskell):

> > (cycle [3,4]) == (cycle [3,4])

> > Although the result should be true, the expression above never
> > terminates.  Is there any way at all to do such a test without
> > resorting to non-functional features (eg. pointer-equality)?

> Pointer equality won't help - the two calls to 'cycle' could easily
> return different objects, depending on the implementation.

No, what I was thinking was that you could use pointer equality to
determine when you've reached back to the beginning of the list. eg.

same_items xs ys =
 let xs' = ... get items from xs up to the list back edge
     ys' = ... ditto for ys
     in
   xs' == ys'

To determine where the back edge is, compare the original list (via
pointer equality) with every remaining list as items are popped of.  I'm
not saying this is the most elegant way to do it, just one example of a
non-pure solution. [It does assume the list is circular ofcourse].

Quote:

> Actually it's undecidable if you allow arbitrary functions on at least
> one of the sides of the equality operator, because then the equality
> operator could be used to solve the halting problem.

> Proof sketch:
> Assume this scenario,
>   (cycle [0]) == number_of_steps (lazy a)
> where 'number_of_steps' is the number of steps that 'a' needs to
> evaluate, encoded with as many zeroes as there are evaluation steps and
> a final 1.
> The result of the expression will be False if 'a' can be evaluated in a
> finite number of steps, True otherwise.

Ah, thats a neat proof.

Quote:

> Of course, it might be possible to built a lot of heuristics into == to
> solve the majority of questions. But even with nonrecursive function you
> can get into {*filter*} exponential behaviour. For example, you could use
> this equality to write down a function to test for equivalence of
> boolean terms; that's a "hard" problem: there's no known algorithm that
> does better than O(exp(number of free variables)). In fact finding such
> an algorithm would be a major breakthrough (it would also immediately
> give a non-exponential algorithm for all "hard" problems, such as the
> Travelling Salesman or Breaking RSA).

Good point, though exponential is still far better than
non-terminating.  Moreover, the fact that you could use such tests to
solve hard problems could make the language very expressive.  Are there
any fp languages that support equivalence testing over even a limited
variety of infinite structures?

--
Louis.



Tue, 18 Mar 2003 07:58:14 GMT  
 How to compare infinite lists?

Quote:
> No, what I was thinking was that you could use pointer equality to
> determine when you've reached back to the beginning of the list.

It's easy to lose that point in transformations:

    cycle [1,2,3]          -- cycle of (:) pointers of length 3
    map id (cycle [1,2,3]) -- no cycle, only elements are shared

Moreover, pointer equality speculations are true for a straightforward
implementation, but are not mandated by the language and actually
compilers may do it in different ways. For example in GHC two values
may be not pointer-equal until garbage collection, where they suddenly
become pointer-equal.

--

 \__/
  ^^                      SYGNATURA ZASTPCZA
QRCZAK



Tue, 18 Mar 2003 03:00:00 GMT  
 How to compare infinite lists?

Quote:


> > No, what I was thinking was that you could use pointer equality to
> > determine when you've reached back to the beginning of the list.

> It's easy to lose that point in transformations:

>     cycle [1,2,3]          -- cycle of (:) pointers of length 3
>     map id (cycle [1,2,3]) -- no cycle, only elements are shared

> Moreover, pointer equality speculations are true for a straightforward
> implementation, but are not mandated by the language and actually
> compilers may do it in different ways. For example in GHC two values
> may be not pointer-equal until garbage collection, where they suddenly
> become pointer-equal.

Right, thats interesting - I'll keep well clear of pointer equality
then.  Some sort of monadically built circular list which explicitly
maintains the back edge point should work.  Whatever the approach, its
clear that it can't be purely functional.  I did imagine that was the
case, but I just thought I'd ask to be sure ...

--
Louis.



Tue, 18 Mar 2003 03:00:00 GMT  
 How to compare infinite lists?

Quote:

>> (cycle [3,4]) == (cycle [3,4])
>> Although the result should be true, the expression above never
>> terminates.  Is there any way at all to do such a test without resorting
>> to non-functional features (eg. pointer-equality)?
> Well, I suppose you could rely on the compiler to infer that the two
> expression are the same, and replace the test with 'True'.  Of course,
> that would mean the behaviour of programs would change with different
> compiler switches...

I'd strongly discourage such transformations, because they change the
meaning of programs! The operational semantics clearly specifies that in

  if x == y then e1
  else e2

you have to compare the *values* of x and y, which means, you have to
*evaluate* them. The operational semantics does not tell you anything about
handling semantically equivalent terms.

Your transformation would transform

  if bottom == bottom then unreachable1
  else unreachable2

into "unreachable1" - which is clearly against the operational semantics.
The program must not terminate.

Currently, the "if"-statement allows you to evaluate terms in a strict way
by writing, e.g.

  if x == x then e1
  else unreachable

This wouldn't be possible with your trick anymore. (Actually, the
if-statement has a funny dual in strict languages: there they introduce
laziness, because only one alternative will be evaluated).

Note, btw., that in strict languages you *can* get rid of the if-statement
and (if the language is pure) of the inefficiency of evaluating the term
twice without changing the semantics, whereas you can't in lazy ones
(unless you introduce a primitive "strict"-function as in Haskell). E.g.:

  if maybe_bottom () = maybe_bottom () then maybe_reachable
  else unreachable

-->

  let _ = maybe_bottom () in maybe_reachable

Of course, in strict languages it is always safe to eliminate the choice
induced by if-statements if the condition is known to be a value and if the
"mathematical equivalence" is known.

Best regards,
Markus Mottl

--



Tue, 18 Mar 2003 03:00:00 GMT  
 How to compare infinite lists?

Quote:


...
> > Pointer equality won't help - the two calls to 'cycle' could
> > easily return different objects, depending on the implementation.

> No, what I was thinking was that you could use pointer equality to
> determine when you've reached back to the beginning of the list. eg.

So, for the restricted class of 'rational' (i.e. not 'transcendent')
infinite lists which are 'finally periodic', the "only" thing that
is needed in order to be able to decide (and implement) "==" would
be to know the boundaries of the members of the periodic tail of
such lists. (That's what your idea of 'pointer comparison' is all
about, it seems.)

    Thus, if one were willing to interlace the data of the list
with something like "period markers", then "==" would be easily
implementable for 'rational' infinite lists. (Though, handed
two copies of the *same* 'transcendent' (i.e. non-'rational')
infinite list, the algorithm would loop, of course.)

    To have "==" restricted to the class of 'rational' infinite
lists need not be completely worthless either. Rational lists
are closed under quite a few interesting transformations
and combinations. And if you push a rational infinite list
through a finite transducer, the infinite output list is,
again, rational (establishing the proper period marks
for the tail of the output sequence may require a bit of
fancy footwork, though).

Christian Stapfer



Tue, 18 Mar 2003 03:00:00 GMT  
 How to compare infinite lists?

Quote:



> > > The recent thread on functional idioms for comparing finite arrays
> > > got me thinking about the infinite case. To keep it simple,
> > > consider comparing two infinite lists (in Haskell):

> > > (cycle [3,4]) == (cycle [3,4])

> > > Although the result should be true, the expression above never
> > > terminates.  Is there any way at all to do such a test without
> > > resorting to non-functional features (eg. pointer-equality)?

> > Pointer equality won't help - the two calls to 'cycle' could easily
> > return different objects, depending on the implementation.

> No, what I was thinking was that you could use pointer equality to
> determine when you've reached back to the beginning of the list.

Yeah, that's simple.
But it doesn't work for the general case. As soon as you reach a closure
in the list (or a lazily unevaluated subexpression), you're back in
undecidability land.
Example: Assume that "pi" returns the digits of the number pi (which is
an infinite sequence for which well-established algorithms exist), and
"maybe_pi" returns the digits of some other expression for which a
conjecture exists that it returns the digits of pi but where a
mathematical proof is missing.
To evaluate
  pi == maybe_pi
the language would have to prove (or disprove) the conjecture.

Quote:
> [It does assume the list is circular ofcourse].

It's not too difficult to generalize the pointer equality algorithm for
arbitrary structures.
Unfortunately, this won't help with this problem. You can have
pointer-inequal structures that are interface-equal, and that's exactly
the point where undecidability kicks in.

Quote:
> > Actually it's undecidable if you allow arbitrary functions on at
> > least one of the sides of the equality operator, because then the
> > equality operator could be used to solve the halting problem.

> > Proof sketch:
> > [...]

> Ah, thats a neat proof.

Not my inventions - it's a standard technique for proving
undecidability.
Theory of computing can indeed be helpful for practical problems. It's
rare, but it does happen :)

Quote:
> > Of course, it might be possible to built a lot of heuristics into ==
> > to solve the majority of questions. But even with nonrecursive
> > function you can get into {*filter*} exponential behaviour. For example,
> > you could use this equality to write down a function to test for
> > equivalence of boolean terms; that's a "hard" problem: there's no
> > known algorithm that does better than O(exp(number of free
> > variables)). In fact finding such an algorithm would be a major
> > breakthrough (it would also immediately give a non-exponential
> > algorithm for all "hard" problems, such as the
> > Travelling Salesman or Breaking RSA).

> Good point, though exponential is still far better than
> non-terminating.

Er, from a theoretical point of view, yes. If I wish to see the result
before I die, then even O(N^3) is a bit far on the slow side.

Quote:
> Moreover, the fact that you could use such tests to
> solve hard problems could make the language very expressive.

Expressive, but it would also introduce potentially exponential
behaviour into either the compiler or the run-time. That's not a viable
option in practice. And it would directly counteract arguments that
functional languages are "fast enough", so it would be unwise to promote
such facilities.

Quote:
> Are
> there any fp languages that support equivalence testing over even a
> limited variety of infinite structures?

It would be possible to have equality over infinite lists if the type
system made sure that the programmer provided enough hints to the system
to solve equality for every case that might arise.
I know of no language that does such things. Of course that doesn't mean
that no such languages do exist.

Regards,
Joachim
--
This is not an official statement from my employer or from NICE.



Thu, 20 Mar 2003 03:00:00 GMT  
 How to compare infinite lists?

Quote:

>Are there
>any fp languages that support equivalence testing over even a limited
>variety of infinite structures?

Many logic programming languages support equivalence testing (and more
generally unification) of rational terms (a.k.a. regular terms).  See
the recent discussion on comp.lang.prolog with subject line containg
"cyclic terms".

Some of these languages, e.g. BinProlog, also provide some support for
functional syntax.  I don't know if any of these support lazy
evaluation, though.  One language that might support functional
syntax, lazy evaluation, and rational term unification is Curry,
a combined logic/functional language.

--

WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"



Fri, 21 Mar 2003 14:08:59 GMT  
 How to compare infinite lists?

Quote:


> >Are there
> >any fp languages that support equivalence testing over even a limited
> >variety of infinite structures?

> Many logic programming languages support equivalence testing (and more
> generally unification) of rational terms (a.k.a. regular terms).  See
> the recent discussion on comp.lang.prolog with subject line containg
> "cyclic terms".

> Some of these languages, e.g. BinProlog, also provide some support for
> functional syntax.  I don't know if any of these support lazy
> evaluation, though.  One language that might support functional
> syntax, lazy evaluation, and rational term unification is Curry,
> a combined logic/functional language.

Thanks for the info. I hadn't known about Curry; I was suprised to find
that it's very Haskell-like (the main ommission seems to be type classes
but they say that is being considered for a future version). Its unclear
whether it supports equivalence of cyclic terms, I tried a simple test
but it didn't terminate.  Nonetheless, it looks _very_ interesting - a
good way for me to get a feel for logic programming since I can leverage
my Haskell experience.

--
Louis.



Fri, 21 Mar 2003 03:00:00 GMT  
 
 [ 16 post ]  Go to page: [1] [2]

 Relevant Pages 

1. transpose of an infinite list of lists

2. comparing infinite terms

3. infinite lists in clean

4. Beginner: infinite fibonacci list ?

5. Acyclic infinite lists and Kantor

6. Laziness and infinite lists...

7. Infinite lists

8. Infinite lists?

9. representation of infinite lists

10. Infinite lists and generators

11. comparing all values of a list to regex

12. comparing lists

 

 
Powered by phpBB® Forum Software