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 <reilith...@gmail.com> wrote: > 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 >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe