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. |