Hi, I am curious to know if there is a function in Haskell to find if a certain value has already been evaluated. The function I need would have the type:
(?!) :: a -> Bool
And I expect it to be such that the following terminates after printing the first 101 fibonacci numbers.
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
main = do print $ fibs !! 100 print $ takeWhile (?!) fibs
Although I guess I can imagine the following not terminating:
print $ filter (?!) fibs
I would find such a function immensely useful in "printing out" my infinite lists. Thanks! nikhil
That strikes me as being bad in a "I'm violating the Halting Problem" sort of way- but I'm not sure how. Is there some contradictory construction that could be built from such a function? Nikhil Patil wrote:
Hi,
I am curious to know if there is a function in Haskell to find if a certain value has already been evaluated. The function I need would have the type:
(?!) :: a -> Bool
And I expect it to be such that the following terminates after printing the first 101 fibonacci numbers.
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
main = do print $ fibs !! 100 print $ takeWhile (?!) fibs
Although I guess I can imagine the following not terminating:
print $ filter (?!) fibs
I would find such a function immensely useful in "printing out" my infinite lists.
Thanks!
nikhil _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On May 8, 2009, at 01:33 , Joe Fredette wrote:
That strikes me as being bad in a "I'm violating the Halting Problem" sort of way- but I'm not sure how. Is there some contradictory construction that could be built from such a function?
I don't think it is; surely the Haskell runtime knows which thunks it has evaluated. It just explicitly violates referential transparency, and therefore must be in IO. You may be thinking that it would return a result for _|_, but as described if you fed it _|_ it could only produce False (if the _|_ has been evaluated you would not be able to reach the test). -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
That must have been the vibe I was getting. My haskell-spider senses were tingling, I just overshot RT and went for the Halting Problem. /Joe Brandon S. Allbery KF8NH wrote:
On May 8, 2009, at 01:33 , Joe Fredette wrote:
That strikes me as being bad in a "I'm violating the Halting Problem" sort of way- but I'm not sure how. Is there some contradictory construction that could be built from such a function?
I don't think it is; surely the Haskell runtime knows which thunks it has evaluated. It just explicitly violates referential transparency, and therefore must be in IO. You may be thinking that it would return a result for _|_, but as described if you fed it _|_ it could only produce False (if the _|_ has been evaluated you would not be able to reach the test).
Brandon S. Allbery KF8NH wrote:
On May 8, 2009, at 01:33 , Joe Fredette wrote:
That strikes me as being bad in a "I'm violating the Halting Problem" sort of way- but I'm not sure how. Is there some contradictory construction that could be built from such a function?
I don't think it is; surely the Haskell runtime knows which thunks it has evaluated. It just explicitly violates referential transparency, and therefore must be in IO. You may be thinking that it would return a result for _|_, but as described if you fed it _|_ it could only produce False (if the _|_ has been evaluated you would not be able to reach the test).
It could probably return True in GHC since you can catch exceptions. That still doesn't mean it solves the halting problem, of course. Ganesh =============================================================================== Please access the attached hyperlink for an important electronic communications disclaimer: http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html ===============================================================================
On May 8, 2009, at 13:08 , Sittampalam, Ganesh wrote:
Brandon S. Allbery KF8NH wrote:
and therefore must be in IO. You may be thinking that it would return a result for _|_, but as described if you fed it _|_ it could only produce False (if the _|_ has been evaluated you would not be able to reach the test).
It could probably return True in GHC since you can catch exceptions. That still doesn't mean it solves the halting problem, of course.
Unless it catches exceptions itself (which strikes me as a bad idea; it becomes a trivial way to ignore exceptions, leading to bad programming practices) either they're handled inside the _|_ (in which case it isn't _|_ from the standpoint of our test) or in an outer scope (in which case our test produces _|_ from the standpoint of the exception handler). -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
Brandon S. Allbery KF8NH wrote:
On May 8, 2009, at 13:08 , Sittampalam, Ganesh wrote:
Brandon S. Allbery KF8NH wrote:
and therefore must be in IO. You may be thinking that it would return a result for _|_, but as described if you fed it _|_ it could only produce False (if the _|_ has been evaluated you would not be able to reach the test).
It could probably return True in GHC since you can catch exceptions. That still doesn't mean it solves the halting problem, of course.
Unless it catches exceptions itself (which strikes me as a bad idea; it becomes a trivial way to ignore exceptions, leading to bad programming practices) either they're handled inside the _|_ (in which case it isn't _|_ from the standpoint of our test) or in an outer scope (in which case our test produces _|_ from the standpoint of the exception handler).
Surely it just needs to inspect the thunk to decide whether it's _|_ or not, rather than entering it? Ganesh =============================================================================== Please access the attached hyperlink for an important electronic communications disclaimer: http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html ===============================================================================
On May 8, 2009, at 16:31 , Sittampalam, Ganesh wrote:
Brandon S. Allbery KF8NH wrote:
Unless it catches exceptions itself (which strikes me as a bad idea; it becomes a trivial way to ignore exceptions, leading to bad programming practices) either they're handled inside the _|_ (in which case it isn't _|_ from the standpoint of our test) or in an outer scope (in which case our test produces _|_ from the standpoint of the exception handler).
Surely it just needs to inspect the thunk to decide whether it's _|_ or not, rather than entering it?
The point is it can never be given a thunk that is _|_ because exception handling will have either converted it to a non-_|_ or shunted past the test. And while my earlier com ent suggested that the test could conceivably itself do exception handling, you're right that all it does is inspect to see if a given thunk has been entered, so in fact exception handling shouldn't apply. In the end, when handed _|_ it can only produce False because a _|_ that has been entered cannot reach the test. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
Brandon S. Allbery KF8NH wrote:
On May 8, 2009, at 16:31 , Sittampalam, Ganesh wrote:
Brandon S. Allbery KF8NH wrote:
Unless it catches exceptions itself (which strikes me as a bad idea; it becomes a trivial way to ignore exceptions, leading to bad programming practices) either they're handled inside the _|_ (in which case it isn't _|_ from the standpoint of our test) or in an outer scope (in which case our test produces _|_ from the standpoint of the exception handler).
Surely it just needs to inspect the thunk to decide whether it's _|_ or not, rather than entering it?
The point is it can never be given a thunk that is _|_ because exception handling will have either converted it to a non-_|_ or shunted past the test.
You can set up a thunk in one place, enter it wrapped in a catch in another place, and then inspect it in a third place, e.g. (somewhat pseudo-code): do let x = if 1==1 then error "foo" else 3 y <- catch (evaluate x) (\_ -> 2) b <- isEvaluated x Cheers, Ganesh =============================================================================== Please access the attached hyperlink for an important electronic communications disclaimer: http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html ===============================================================================
Nikhil Patil wrote:
Hi,
I am curious to know if there is a function in Haskell to find if a certain value has already been evaluated. The function I need would have the type:
(?!) :: a -> Bool
I will call this function `evaluated', since it is not a binary operator.
The existence of such a function would violate referential transparency.
What would the value of
( evaluated (fibs !! 100), evaluated (fibs !! 100) )
be ? Suppose that I first print the `fst' of this tuple, then print the
101st Fibonacci nummber, and then print the `snd' of this tuple. By lazy
evaluation, one would expect that this yields
False
Andy Gill has been advocating programmatic access to the 'is evaluated' status bit for years now. 'seq' becomes cheaper, and we can write operational properties/assertions about strictness. -- Don jochem:
Nikhil Patil wrote:
Hi,
I am curious to know if there is a function in Haskell to find if a certain value has already been evaluated. The function I need would have the type:
(?!) :: a -> Bool
I will call this function `evaluated', since it is not a binary operator.
The existence of such a function would violate referential transparency.
What would the value of ( evaluated (fibs !! 100), evaluated (fibs !! 100) ) be ? Suppose that I first print the `fst' of this tuple, then print the 101st Fibonacci nummber, and then print the `snd' of this tuple. By lazy evaluation, one would expect that this yields
False
True but this violates referential transparency.
Cheers, -- Jochem Berndsen | jochem@functor.nl GPG: 0xE6FABFAB _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
But testing for something being evaluated has to be in the IO monad,
or else you're going to break the semantics.
On Fri, May 8, 2009 at 4:14 PM, Don Stewart
Andy Gill has been advocating programmatic access to the 'is evaluated' status bit for years now. 'seq' becomes cheaper, and we can write operational properties/assertions about strictness.
-- Don
jochem:
Nikhil Patil wrote:
Hi,
I am curious to know if there is a function in Haskell to find if a certain value has already been evaluated. The function I need would have the type:
(?!) :: a -> Bool
I will call this function `evaluated', since it is not a binary operator.
The existence of such a function would violate referential transparency.
What would the value of ( evaluated (fibs !! 100), evaluated (fibs !! 100) ) be ? Suppose that I first print the `fst' of this tuple, then print the 101st Fibonacci nummber, and then print the `snd' of this tuple. By lazy evaluation, one would expect that this yields
False
True but this violates referential transparency.
Cheers, -- Jochem Berndsen | jochem@functor.nl GPG: 0xE6FABFAB _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Nikhil Patil
I am curious to know if there is a function in Haskell to find if a certain value has already been evaluated. The function I need would have the type:
(?!) :: a -> Bool
Well, obviously you can't do this, it would violate referential transparency. Except if you define it as (?!) :: a -> Bool (?!) x = x `seq` True ..but that's probably not what you meant? :-)
And I expect it to be such that the following terminates after printing the first 101 fibonacci numbers.
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
main = do print $ fibs !! 100 print $ takeWhile (?!) fibs
The obvious problem is that the pure function "takeWhile (?!) fibs" would return different things depending on what has happened to "fibs" earlier in the program. The run-time system has information about evaluation status, so it might be possible to query it - but you'd need to do so in IO. I also seem to remember a debugger being able to display evaluated and unevaluated thunks? Also, you might be able to inspect evaluation by something like fibs2 = sequence' [ print ("evaluating:"++show x)) >> return x | x <- fibs ] where sequence' is a lazy version of sequence. This is a bit clunky, but occasionally useful. -k -- If I haven't seen further, it is by standing in the footprints of giants
participants (8)
-
Brandon S. Allbery KF8NH -
Don Stewart -
Jochem Berndsen -
Joe Fredette -
Ketil Malde -
Lennart Augustsson -
Nikhil Patil -
Sittampalam, Ganesh