Proposal: adding 'tailDropWhile' to Data.List

[Ben Millwood]

On Wed, Sep 28, 2011 at 3:06 PM, Ben Millwood <haskell at benmachine.co.uk> wrote:
> On Wed, Sep 28, 2011 at 10:19 AM, Kazu Yamamoto <kazu at iij.ad.jp> 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 at 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).