Personal tools

Infinity and efficiency

From HaskellWiki

Revision as of 20:27, 18 September 2008 by Lemming (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search


In this article we want to demonstrate how to check efficiency of an implementation by checking for proper results for infinite input. In general it is harder to reason about time and memory complexity of an implementation than on its correctness. In fact in Haskell inefficient implementations sometimes turn out to be wrong implementations. A very simple examples is the function reverse . reverse which seems to be an inefficient implementation of id. But if you look closer it is not exactly equivalent to id, because for infinite input list, the function reverse . reverse is undefined, whereas id is defined.