[Haskell-cafe] Performance of delete-and-return-last-element

[Clark Gaebel]

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 <reilithion at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130830/b1776413/attachment.htm>