dropWhileRev

Henning Thielemann

5 Aug 2005 5 Aug '05

9:28 a.m.

Is this function worth to be added to Data.List? {-| Remove the longest suffix of elements satisfying the predicate. In contrast to 'reverse . dropWhile p . reverse' this works for infinite lists, too. -} dropWhileRev :: (a -> Bool) -> [a] -> [a] dropWhileRev p = foldr (\x xs -> if p x && null xs then [] else x:xs) []

Show replies by date

Jonathan Cast

7 Aug 7 Aug

2:10 p.m.

Henning Thielemann wrote:

...

Is this function worth to be added to Data.List?

{-| Remove the longest suffix of elements satisfying the predicate. In contrast to 'reverse . dropWhile p . reverse' this works for infinite lists, too. -} dropWhileRev :: (a -> Bool) -> [a] -> [a] dropWhileRev p = foldr (\x xs -> if p x && null xs then [] else x:xs) []

Quick query: this function only delivers partial lists from partial lists; hence, it only returns partial lists and infinite lists from infinite lists (In particular, it is not true that, if (exists n. take n (dropWhileRev p xn) /= take n xn) then (dropWhileRev p xn `isPrefixOf` xn = True). Prelude> let dropWhileRev p = foldr (\x xs -> if p x && null xs then [] else x:xs) [] Prelude> dropWhileRev (const True) (repeat 'c') "*** Exception: stack overflow Prelude> dropWhileRev (\n -> n `mod` 2 == 0) ([1..3]++repeat 2) [1,2,3*** Exception: stack overflow Prelude> What do you mean by ``works for inifinite lists''? Jon Cast

David Roundy

6:39 p.m.

On Sun, Aug 07, 2005 at 09:10:03AM -0500, Jonathan Cast wrote:

...

Henning Thielemann wrote:

...
Is this function worth to be added to Data.List?

{-| Remove the longest suffix of elements satisfying the predicate. In contrast to 'reverse . dropWhile p . reverse' this works for infinite lists, too. -} dropWhileRev :: (a -> Bool) -> [a] -> [a] dropWhileRev p = foldr (\x xs -> if p x && null xs then [] else x:xs) [] ... What do you mean by ``works for inifinite lists''?

(I don't know if the following is what Hennig meant, but it's what I understood.) It "works for infinite lists that don't have an infinite sequence of matching elements". Even for such problematic lists the above will work until you hit that matching sequence. take 10 $ dropWhileRev (/= 2) ([1..]) works. But with the "obvious" implementation you'll *always* get failure on infinite lists. It even works "correctly" if you choose to define the meaning of the function to be that it removes the longest contiguous matching sequence that includes the end of the list. -- David Roundy http://www.darcs.net

Jonathan Cast

7:20 p.m.

David Roundy wrote:

...

On Sun, Aug 07, 2005 at 09:10:03AM -0500, Jonathan Cast wrote:

...
Henning Thielemann wrote:

...
Is this function worth to be added to Data.List?

{-| Remove the longest suffix of elements satisfying the predicate. In contrast to 'reverse . dropWhile p . reverse' this works for infinite lists, too. -} dropWhileRev :: (a -> Bool) -> [a] -> [a] dropWhileRev p = foldr (\x xs -> if p x && null xs then [] else x:xs) [] ... What do you mean by ``works for inifinite lists''?

(I don't know if the following is what Hennig meant, but it's what I understood.)

It "works for infinite lists that don't have an infinite sequence of matching elements". Even for such problematic lists the above will work until you hit that matching sequence.

take 10 $ dropWhileRev (/= 2) ([1..])

works. But with the "obvious" implementation you'll *always* get failure on infinite lists.

Ah. dropWhileRev p xn is not what I would expect (I would expect (take n xn where n = max n. forall i >= n. p (xn !! i))), but it is the most defined computable approximation to it. Jon Cast

7274

Age (days ago)

7276

Last active (days ago)

List overview

Download

3 comments

3 participants

participants (3)

David Roundy
Henning Thielemann
Jonathan Cast

dropWhileRev

Henning Thielemann

Jonathan Cast

David Roundy

Jonathan Cast

tags

participants (3)