Hacker News Reader

Comment by jeremyjh | Hacker News Reader

This is something non-Haskellers worry about quite a lot, and Haskellers not much if at all. Others have mentioned that lazy I/O is not really a thing in real world Haskell. But its important to know that lazy by default has a lot of benefit in the composition of pure functions, e.g. `take 10 . sort`

View on HN

> a lot of benefit in the composition of pure functions, e.g. `take 10 . sort`

At the risk of catching HN's ire... this is not a good thing.

Haskell's type signature tells you almost nothing about whether this use-case is supported. If it's not, you've got yourself a nonlinear slowdown, potentially wrecking your performance. Readers can't know this without literally reading the documentation, except the documentation doesn't even tell you if this is OK.

Yet because people are being ‘clever’ like this, Haskell has ended up stuck with a sort a factor ~ten slower than Python (!!), and an incremental sort that's still a factor ~2 slower than Python's heapq-based incremental sort.

So you're using a sort in a way that you have no explicit language-level guarantees for, seemingly no documented guarantees for at all, and in a way that's incredibly harmful to the common case, but also—and this is a curse that's almost unique to Haskell—the language is also prevented from utilizing future improvements to sorting algorithms!

Because of this, and despite Haskell's ‘purity’, the internals of Haskell's sort are more observable and less open to change than is the case for almost any other language that I know of!

Indeed. It's bizarre that some Haskellers push this as an example of one of the benefits of Haskell when it's implicit behaviour, exactly what I use Haskell to avoid. If, on the other hand, sort were `[a] -> Stream (Of a) ()`, well, that would be something else ...

>this is a curse that's almost unique to Haskell—the language is also prevented from utilizing future improvements to sorting algorithms!

Back in reality of course, Haskell has fast, generic, linear-time sorting: https://hackage.haskell.org/package/discrimination

I've been a proponent of radix sort since long before I'd heard of this package, but I think you've completely missed my point.

Sorting has to operate on the entire input, how is laziness an advantage here?

Sure the entire input list will need to be consumed, but not every element of the output will need to be determined if we are only taking the top 10.

Laziness enables many compositions to work efficiently, whereas with a strict language, you'd have to fuse the operations to get the same efficiency. More examples here: http://augustss.blogspot.com/2011/05/more-points-for-lazy-ev...

If you are running a sort them you will need to compare each of the elements at least once which will mean you have to evaluate the whole list right?

You have to evaluate the whole input list (absent cheating by checking if you have enough elements equal to minBound), but you don't have to sort more elements than you need to produce, which can save you work.

Nope! Image sort is quicksort or heapsort. Then the work will be O(k log n) vs O(n log n)

I can see how this might be possible but does it actually work like this in practice?

Is your k here representing “take k . sort”?

Yes. Let's say sort here is quicksort (a reasonable choice). Quicksort works, as you know, by partitioning based on a pivot element, putting those smaller before the pivot and those larger after the pivot. It then recursively sorts the two partitions. In Haskell this recursive sort is deferred until the result is actually needed, and a smart haskeller implementing the quicksort would choose to do the smaller-than-pivot partition first--as is the default syntactic choice in any case when concatenating two lists. On each recursion the smaller-than-pivot branch is taken and the larger-than-pivot branch is deferred. As soon as condition is hit where the pivot is the smallest element, it is immediately returned to `take`. The `take` implementation then calls for another value if k>1, and it resumes from where it left of, recursing into the previously deferred larger-than-pivot partition at the bottom of the execution tree, and working itself up from there until `take` is satisfied. Once `k` elements are taken, there's still a partial tree of unexecuted continuations that is thrown away.

In other words, the very nature of Haskell's lazy-by-default semantics makes the straight-forward, seemingly strict implementation of quicksort, or other sorting algorithm, automatically optimized to improve performance through lazy execution.

because maybe later in the program you will deicide that that computation does not need to be executed at all.

Can you give an example of what you mean by this?

That’s the kind of thing you would use “if” for right?

One was given earlier in the thread: `take 10 . sort`

This should be read from right to left: it sorts an (implicit) list, then reads the first 10 elements from the beginning of the now-sorted list, and throws away the rest.

Except under the hood in Haskell, sort is not a function that takes a list and returns a list. It is a function that takes a list, and returns the smallest element of that list and a function to fetch the rest of the sorted list. (A function which actually returns the second-smallest element and a function that if called returns the third smallest element and another function, etc.)

These ephemeral functions / continuations / "thunks" are allowed to have internal state and thereby perform more complex sorting operations such as quicksort, and might actually be represented by an internal tree of branch points and their returned value or unexecuted thunks.

But all of this complexity is hidden by the compiler. It's not some special property of `sort` either, which might look like this:

    sort [] = []
    sort (x:xs) = sort small ++ (x : sort large)
        where small = [y | y <- xs, y <= x]
              large = [y | y <- xs, y > x]

"The sort of an empty list is the empty list. The sort of a non-empty list is the elements of the tail less than or equal to the head of the list, sorted, followed by the head of the list, followed by the elements of the tail greater than the head of the lest, sorted."

The Haskell compiler does the magic of turning this into a lazy-optimized implementation which in the case of `take 10 . sort` doesn't bother to calculate any remaining `sort large` partitions once the first 10 smallest elements have been found.

Reply on news.ycombinator.com