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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
