How to compare infinite lists?
Author 
Message 
Louis Mado #1 / 16

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 nonfunctional features (eg. pointerequality)? Thanks,  Louis.

Mon, 17 Mar 2003 08:24:07 GMT 


Marcin 'Qrczak' Kowalcz #2 / 16

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 nonfunctional features (eg. pointerequality)?
No. 
\__/ ^^ SYGNATURA ZASTPCZA QRCZAK

Mon, 17 Mar 2003 03:00:00 GMT 


Nick Willia #3 / 16

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 nonfunctional features (eg. pointerequality)? >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 


Ketil Z Mald #4 / 16

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 nonfunctional features (eg. pointerequality)?
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 


Marcin 'Qrczak' Kowalcz #5 / 16

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 nonfunctional features (eg. pointerequality)? > >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 


Nick Willia #6 / 16

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 nonfunctional features (eg. pointerequality)? >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 


Joachim Durchhol #7 / 16

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 nonfunctional features (eg. pointerequality)?
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 nonexponential 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 


Louis Mado #8 / 16

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 nonfunctional features (eg. pointerequality)? > 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 nonpure 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 nonexponential algorithm for all "hard" problems, such as the > Travelling Salesman or Breaking RSA).
Good point, though exponential is still far better than nonterminating. 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 


Marcin 'Qrczak' Kowalcz #9 / 16

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 pointerequal until garbage collection, where they suddenly become pointerequal. 
\__/ ^^ SYGNATURA ZASTPCZA QRCZAK

Tue, 18 Mar 2003 03:00:00 GMT 


Louis Mado #10 / 16

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 pointerequal until garbage collection, where they suddenly > become pointerequal.
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 


Markus Mott #11 / 16

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 nonfunctional features (eg. pointerequality)? > 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 ifstatement 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 ifstatement 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 ifstatements 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 


Christian Stapfe #12 / 16

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 


Joachim Durchhol #13 / 16

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 nonfunctional features (eg. pointerequality)? > > 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 wellestablished 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 pointerinequal structures that are interfaceequal, 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 nonexponential > > algorithm for all "hard" problems, such as the > > Travelling Salesman or Breaking RSA). > Good point, though exponential is still far better than > nonterminating.
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 runtime. 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 


Fergus Henders #14 / 16

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 


Louis Mado #15 / 16

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


Page 1 of 2

[ 16 post ] 

Go to page:
[1]
[2] 
