Re: [Haskell-cafe] Where is "minimumsBy"?

Christian Sternagel writes:

That is interesting. Is anybody aware of a more detailed justification of how lazy evaluation makes this happen? - chris

There might be a more formal argument written down somewhere, but the gist of it should be: Think of the recursion tree of merge sort; leaves correspond to singleton lists, internal nodes correspond to merges of two sorted lists. To determine the minimum element of the merged result you need to consider only the first elements of both these lists. Hence, every node can be charged at most O(1) times. Since the tree has size O(n) the running time is linear. -- - Frank