Ich sah mich um StapelüberlaufNicht-Trivial Lazy Evaluation, was mich zu Keegan McAllisters Präsentation führte:Warum Haskell lernen?. In Folie 8 zeigt er die Minimalfunktion, definiert als:

minimum = head . sort

und gibt an, dass seine Komplexität O (n) ist. Ich verstehe nicht, warum die Komplexität linear sein soll, wenn die Sortierung nach Ersetzung O (nlog n) ist. Die Sortierung, auf die im Beitrag verwiesen wird, kann nicht linear sein, da sie nichts über die Daten annimmt, wie es für lineare Sortierungsmethoden wie Zählsortierung erforderlich wäre.

Spielt hier die faule Bewertung eine mysteriöse Rolle? Wenn ja, welche Erklärung steckt dahinter?