[Haskell-cafe] Re: A suggestion for the next high profile Haskell
project [Was: Re: What is a hacker?]
jo at durchholz.org
Tue Dec 19 16:54:09 EST 2006
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
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
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?
More information about the Haskell-Cafe