[Haskell-cafe] Where is "minimumsBy"?

Frank Staals frank at fstaals.net
Fri Sep 28 07:30:53 UTC 2018


Christian Sternagel <c.sternagel at gmail.com> 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


More information about the Haskell-Cafe mailing list