Re: Proposal: adding 'tailDropWhile' to Data.List

On Wed, Sep 28, 2011 at 3:06 PM, Ben Millwood wrote:

On Wed, Sep 28, 2011 at 10:19 AM, Kazu Yamamoto wrote:

...

Hello,

Many languages provide the 'chop' or 'trip' function but Data.List does not. I would like to add a new function called 'tailDropWhile' so that people can easily implement 'chop' for String:

chop :: String -> String chop = tailDropWhile isSpace

The definition of tailDropWhile is as follows:

{-  wren ng thornton's version. This is lazier than Aoe's one.  Out and inP implement push-down automata. -} tailDropWhile :: (a -> Bool) -> [a] -> [a] tailDropWhile p = out  where    out []        = []    out (x:xs)      | p x       = inP [x] xs      | otherwise = x : out xs    inP _ []      = []    inP ss (x:xs)      | p x       = inP (x:ss) xs      | otherwise = reverse ss ++ x : out xs

{- Mitsutoshi Aoe's version.   This is faster is many cases but more strict.   Just for reference. tailDropWhile :: (a -> Bool) -> [a] -> [a] tailDropWhile p = foldr go []  where    go x xs      | p x && null xs = []      | otherwise      = x:xs -}

For more information, please read:        http://www.mail-archive.com/haskell-cafe@haskell.org/msg93192.html

Discussion period: 2 weeks.

Regards,

--Kazu

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

I'd implement it as:

tailDropWhile :: (a -> Bool) -> [a] -> [a] tailDropWhile p xs = go id xs  where  go _ [] = []  go k (x:xs)    | p x = go (k . (x:)) xs    | otherwise = k (x : go id xs)

which is as lazy as possible and doesn't involve any reversing.

It's a function I've needed to use before, but I don't feel strongly about its inclusion particularly. While Ivan raises legitimate concerns, the version I've given above is a bit more streamy, and anyway many of us acknowledge the value of (!!) and related "bad" list functions in some circumstances.

Hmm. I wrote this attempting to satisfy the goals of "lazy and efficient", but on second thoughts it seems like Aoe's original function was both. You seem to be under the impression that it's more strict, but I think it's just as lazy as the others. Can you provide evidence of its strictness? (In my (admittedly crude) benchmarks it seems Aoe's was narrowly faster than mine, which was significantly faster than wren's).