Infinity and efficiency
Jump to navigation Jump to 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
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.