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

[Ben]

isn't this what zippers are for?

b

On Aug 30, 2013, at 1:04 PM, Clark Gaebel wrote:

> 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
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe