Difference between revisions of "Infinity and efficiency"
Jump to navigation
Jump to search
(introduction) |
(No difference)
|
Revision as of 20:27, 18 September 2008
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.