Seth Gordon schrieb:
Joachim Durchholz wrote:
Trying to fully evaluate an infinite data structure will result in looping or memory exhaustion, and you have that possibilities in almost all languages. Yes, but I suspect that Haskell makes it easier to make that kind of bug. Worse, it's easy to introduce this kind of bug: just pass a list returned from function a to function b, not being aware that a may return an infinite list and that b may do something with it that requires that it's evaluated. In other words, this kind of bug can come into existence during code integration... and the type system doesn't warn you when you do it.
If you're worrying about some unexpected input causing a function never to terminate, don't you also have to worry about some unexpected input causing a function to become so glacially slow that from the user's perspective, it *might as well* never terminate?
I'm not really talking about bad algorithms. I'd talking about integrating two innocent functions and getting a result that doesn't terminate. That's a problem that doesn't exist in strict languages: feeding the output of one function into another function won't turn terminating functions into nonterminating ones. However, you're right that composing functions might drastically change their performance - simply because the inner function may return data structures that are expensive to evaluate, and the outer function insists on evaluating them. So, for a lazy language, nontermination is just one side of the coin, the other is unexpected performance effects. OT3H this kind of problem may occur whenever you're passing around executable stuff, whether it's in the form of unevaluated lazy thunks, strict-language streams, or (to add the perspective from a non-FPL camp) passing around polymorphic objects that carry functions of unknown space and time complexity. It's probably a question of how idiomatic code behaves. OT4H I know how to annotate code with space and time complexities in a strict language. I.e. a Sort typeclass should impose an O(N log N) complexity on the sort function, slower sorts don't really do what the programmer expects - and that's then a guarantee that callers of the sort function can build upon. And while I have an in-principle approach for strict languages, I don't have one for lazy languages. Is there any literature on the subject? Regards, Jo