Difference between revisions of "Infinity and efficiency"
Jump to navigation
Jump to search
m (minor edit) |
Tomjaguarpaw (talk | contribs) (Deleting page that hasn't been edited for over 10 years) |
||
| Line 1: | Line 1: | ||
| − | [[Category:Idioms]] |
||
| − | |||
| − | In this article we demonstrate how to check the 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 about its correctness. |
||
| − | In fact, in Haskell inefficient implementations sometimes turn out to be wrong implementations. |
||
| − | |||
| − | A very simple example is the function <code>reverse . reverse</code> which seems to be an inefficient implementation of <code>id</code>. |
||
| − | In a language with [[strict semantics]], these two functions are the same. |
||
| − | But since the [[non-strict semantics]] of Haskell allows infinite data structures, there is a subtle difference, |
||
| − | because for an infinite input list, the function <code>reverse . reverse</code> is undefined, whereas <code>id</code> is defined. |
||
| − | |||
| − | Now let's consider a more complicated example. |
||
| − | Say we want to program a function that removes elements from the end of a list, |
||
| − | just like <code>dropWhile</code> removes elements from the beginning of a list. |
||
| − | We want to call it <code>dropWhileRev</code>. |
||
| − | (As a more concrete example, imagine a function which removes trailing spaces.) |
||
| − | A simple implementation is |
||
| − | <haskell> |
||
| − | dropWhileRev :: (a -> Bool) -> [a] -> [a] |
||
| − | dropWhileRev p = reverse . dropWhile p . reverse |
||
| − | </haskell> |
||
| − | You probably have already guessed that it also does not work for infinite input lists. |
||
| − | Incidentally, it is also inefficient, because <code>reverse</code> requires to compute all list nodes |
||
| − | (although it does not require to compute the values stored in the nodes). |
||
| − | Thus the full list skeleton must be held in memory. |
||
| − | However, it is possible to implement <code>dropWhileRev</code> in a way that works for more kinds of inputs. |
||
| − | <haskell> |
||
| − | dropWhileRev :: (a -> Bool) -> [a] -> [a] |
||
| − | dropWhileRev p = |
||
| − | foldr (\x xs -> if p x && null xs then [] else x:xs) [] |
||
| − | </haskell> |
||
| − | Here, <code>foldr</code> formally inspects the list from right to left, |
||
| − | but it actually processes data from left to right. |
||
| − | Whenever a run of elements that matches the condition <code>p</code> occurs, these elements are held until the end of the list is encountered (then they are dropped), |
||
| − | or when a non-matching list element is found (then they are emitted). |
||
| − | The crux is the part <code>null xs</code>, which requires to do recursive calls within <code>foldr</code>. |
||
| − | This works in many cases, but it fails if the number of matching elements becomes too large. |
||
| − | The maximum memory consumption depends on the length of the runs of non-matching elements, |
||
| − | which is much more efficient than the naive implementation above. |
||