I don't think a really smart compiler can make that transformation. It
looks like an exponential-time algorithm would be required, but I can't
prove that.
GHC definitely won't...
For this specific example, though, I'd probably do:
darle :: [a] -> (a, [a])
darle xs =
case reverse xs of
[] -> error "darle: empty list"
(x:xs) -> (x, reverse xs)
- Clark
On Fri, Aug 30, 2013 at 2:18 PM, Lucas Paul
Suppose I need to get an element from a data structure, and also modify the data structure. For example, I might need to get and delete the last element of a list:
darle xs = ((last xs), (rmlast xs)) where rmlast [_] = [] rmlast (y:ys) = y:(rmlast ys)
There are probably other and better ways to write rmlast, but I want to focus on the fact that darle here, for lack of a better name off the top of my head, appears to traverse the list twice. Once to get the element, and once to remove it to produce a new list. This seems bad. Especially for large data structures, I don't want to be traversing twice to do what ought to be one operation. To fix it, I might be tempted to write something like:
darle' [a] = (a, []) darle' (x:xs) = let (a, ys) = darle' xs in (a, (x:ys))
But this version has lost its elegance. It was also kind of harder to come up with, and for more complex data structures (like the binary search tree) the simpler expression is really desirable. Can a really smart compiler transform/optimize the first definition into something that traverses the data structure only once? Can GHC?
- Lucas
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe