Pre-proposal discussion: add a version of dropWhileEnd with different laziness properties to Data.List

newer
Proposal: change the Bits instance...

David Feuer

28 Sep 2014 28 Sep '14

4:39 p.m.

BACKGROUND: A somewhat common idiom I discovered digging around the GHC tree is the use of reverse . dropWhile p . reverse to remove some unwanted things from the end of a list. The lists involved tend to be short (e.g., file names, package names, lines of user input, etc.) and the amount removed from the end of the list tends to be short (a trailing newline, the last part of a filename, extra spaces, etc.). I initially intended to replace all of these with Data.List.dropWhileEnd p. Unfortunately, my benchmarking showed that this had a substantial negative impact on performance. Data.List.dropWhileEnd is defined like this: dropWhileEnd p = foldr (\x r -> if p x && null r then [] else x:r) [] This is lazy in the *spine* of the list--it can "flush its buffer" and produce list elements any time p x is found to be false. This is the best you can do if you need to process a very large list and don't want to have to load the whole thing into memory, and/or your predicate is *very* cheap. Unfortunately, it pays a steep price: for non-trivial p, it's strict in the *elements* of the list. This makes it unsuitable, from a performance standpoint, for most of the purposes for which I've seen reverse . dropWhile p . reverse used. CONCEPT: Add (by some name) a function that is lazy in the elements while strict in the spine: dropWhileEndLE :: (a -> Bool) -> [a] -> [a] -- specification: dropWhileEndLE p = reverse . dropWhile p . reverse dropWhileEndLE p = foldr (\x r -> if null r && p x then [] else x:r) [] This is a good bit faster than the double-reversing version, presumably because it presumably allocates its buffer stack on the GHC stack rather than spraying junk across the heap. If I were a Time Lord, I'd go back in time and add to the library, instead of dropWhileEnd as it is, a function with a name like takeUntilLastSatisfying p = dropWhileEnd (not . p) which has a name that explains better what it does, and I'd define dropWhileEnd to be dropWhileEndLE. But I'm not a Time Lord, so I'd like to hear what name or naming approach other people would recommend.

Attachments:

attachment.html (text/html — 2.4 KB)

Show replies by date

David Feuer

28 Sep 28 Sep

6:53 p.m.

One good option might be dropWhileR, to match Data.Sequence, but I'd only want to use that if the dropWhileEnd name were deprecated in favor of takeUntilLastSatisfying or whatever—otherwise it's just too confusing. On Sep 28, 2014 4:39 PM, "David Feuer" wrote:

...

BACKGROUND:

A somewhat common idiom I discovered digging around the GHC tree is the use of

reverse . dropWhile p . reverse

to remove some unwanted things from the end of a list. The lists involved tend to be short (e.g., file names, package names, lines of user input, etc.) and the amount removed from the end of the list tends to be short (a trailing newline, the last part of a filename, extra spaces, etc.). I initially intended to replace all of these with Data.List.dropWhileEnd p. Unfortunately, my benchmarking showed that this had a substantial negative impact on performance. Data.List.dropWhileEnd is defined like this:

dropWhileEnd p = foldr (\x r -> if p x && null r then [] else x:r) []

This is lazy in the *spine* of the list--it can "flush its buffer" and produce list elements any time p x is found to be false. This is the best you can do if you need to process a very large list and don't want to have to load the whole thing into memory, and/or your predicate is *very* cheap. Unfortunately, it pays a steep price: for non-trivial p, it's strict in the *elements* of the list. This makes it unsuitable, from a performance standpoint, for most of the purposes for which I've seen reverse . dropWhile p . reverse used.

CONCEPT:

Add (by some name) a function that is lazy in the elements while strict in the spine:

dropWhileEndLE :: (a -> Bool) -> [a] -> [a] -- specification: dropWhileEndLE p = reverse . dropWhile p . reverse dropWhileEndLE p = foldr (\x r -> if null r && p x then [] else x:r) []

This is a good bit faster than the double-reversing version, presumably because it presumably allocates its buffer stack on the GHC stack rather than spraying junk across the heap.

If I were a Time Lord, I'd go back in time and add to the library, instead of dropWhileEnd as it is, a function with a name like

takeUntilLastSatisfying p = dropWhileEnd (not . p)

which has a name that explains better what it does, and I'd define dropWhileEnd to be dropWhileEndLE. But I'm not a Time Lord, so I'd like to hear what name or naming approach other people would recommend.

Greg Weber

6:59 p.m.

Should the code be using Seq instead of a List? On Sun, Sep 28, 2014 at 3:53 PM, David Feuer wrote:

...

One good option might be dropWhileR, to match Data.Sequence, but I'd only want to use that if the dropWhileEnd name were deprecated in favor of takeUntilLastSatisfying or whatever—otherwise it's just too confusing. On Sep 28, 2014 4:39 PM, "David Feuer" wrote:

...
BACKGROUND:

A somewhat common idiom I discovered digging around the GHC tree is the use of

reverse . dropWhile p . reverse

to remove some unwanted things from the end of a list. The lists involved tend to be short (e.g., file names, package names, lines of user input, etc.) and the amount removed from the end of the list tends to be short (a trailing newline, the last part of a filename, extra spaces, etc.). I initially intended to replace all of these with Data.List.dropWhileEnd p. Unfortunately, my benchmarking showed that this had a substantial negative impact on performance. Data.List.dropWhileEnd is defined like this:

dropWhileEnd p = foldr (\x r -> if p x && null r then [] else x:r) []

This is lazy in the *spine* of the list--it can "flush its buffer" and produce list elements any time p x is found to be false. This is the best you can do if you need to process a very large list and don't want to have to load the whole thing into memory, and/or your predicate is *very* cheap. Unfortunately, it pays a steep price: for non-trivial p, it's strict in the *elements* of the list. This makes it unsuitable, from a performance standpoint, for most of the purposes for which I've seen reverse . dropWhile p . reverse used.

CONCEPT:

Add (by some name) a function that is lazy in the elements while strict in the spine:

dropWhileEndLE :: (a -> Bool) -> [a] -> [a] -- specification: dropWhileEndLE p = reverse . dropWhile p . reverse dropWhileEndLE p = foldr (\x r -> if null r && p x then [] else x:r) []

This is a good bit faster than the double-reversing version, presumably because it presumably allocates its buffer stack on the GHC stack rather than spraying junk across the heap.

If I were a Time Lord, I'd go back in time and add to the library, instead of dropWhileEnd as it is, a function with a name like

takeUntilLastSatisfying p = dropWhileEnd (not . p)

which has a name that explains better what it does, and I'd define dropWhileEnd to be dropWhileEndLE. But I'm not a Time Lord, so I'd like to hear what name or naming approach other people would recommend.

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

David Feuer

8:34 p.m.

That decision is up to the user. Data.List provides a number of sequence functions that aren't efficient for lists, including take, drop, splitAt, init, last, reverse, zip, unzip, and (!!). dropWhileEnd and dropWhileLE aren't any worse, I don't think. On Sun, Sep 28, 2014 at 6:59 PM, Greg Weber wrote:

...

Should the code be using Seq instead of a List?

On Sun, Sep 28, 2014 at 3:53 PM, David Feuer wrote:

...
One good option might be dropWhileR, to match Data.Sequence, but I'd only want to use that if the dropWhileEnd name were deprecated in favor of takeUntilLastSatisfying or whatever—otherwise it's just too confusing. On Sep 28, 2014 4:39 PM, "David Feuer" wrote:

...
BACKGROUND:

A somewhat common idiom I discovered digging around the GHC tree is the use of

reverse . dropWhile p . reverse

to remove some unwanted things from the end of a list. The lists involved tend to be short (e.g., file names, package names, lines of user input, etc.) and the amount removed from the end of the list tends to be short (a trailing newline, the last part of a filename, extra spaces, etc.). I initially intended to replace all of these with Data.List.dropWhileEnd p. Unfortunately, my benchmarking showed that this had a substantial negative impact on performance. Data.List.dropWhileEnd is defined like this:

dropWhileEnd p = foldr (\x r -> if p x && null r then [] else x:r) []

This is lazy in the *spine* of the list--it can "flush its buffer" and produce list elements any time p x is found to be false. This is the best you can do if you need to process a very large list and don't want to have to load the whole thing into memory, and/or your predicate is *very* cheap. Unfortunately, it pays a steep price: for non-trivial p, it's strict in the *elements* of the list. This makes it unsuitable, from a performance standpoint, for most of the purposes for which I've seen reverse . dropWhile p . reverse used.

CONCEPT:

Add (by some name) a function that is lazy in the elements while strict in the spine:

dropWhileEndLE :: (a -> Bool) -> [a] -> [a] -- specification: dropWhileEndLE p = reverse . dropWhile p . reverse dropWhileEndLE p = foldr (\x r -> if null r && p x then [] else x:r) []

This is a good bit faster than the double-reversing version, presumably because it presumably allocates its buffer stack on the GHC stack rather than spraying junk across the heap.

If I were a Time Lord, I'd go back in time and add to the library, instead of dropWhileEnd as it is, a function with a name like

takeUntilLastSatisfying p = dropWhileEnd (not . p)

which has a name that explains better what it does, and I'd define dropWhileEnd to be dropWhileEndLE. But I'm not a Time Lord, so I'd like to hear what name or naming approach other people would recommend.

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

Carter Schonwald

9:11 p.m.

on the flip side, how can we encourage more usage of Data.Sequence ? :) On Sun, Sep 28, 2014 at 8:34 PM, David Feuer wrote:

...

That decision is up to the user. Data.List provides a number of sequence functions that aren't efficient for lists, including take, drop, splitAt, init, last, reverse, zip, unzip, and (!!). dropWhileEnd and dropWhileLE aren't any worse, I don't think.

On Sun, Sep 28, 2014 at 6:59 PM, Greg Weber wrote:

...
Should the code be using Seq instead of a List?

On Sun, Sep 28, 2014 at 3:53 PM, David Feuer wrote:

...
One good option might be dropWhileR, to match Data.Sequence, but I'd only want to use that if the dropWhileEnd name were deprecated in favor of takeUntilLastSatisfying or whatever—otherwise it's just too confusing. On Sep 28, 2014 4:39 PM, "David Feuer" wrote:

...
BACKGROUND:

A somewhat common idiom I discovered digging around the GHC tree is the use of

reverse . dropWhile p . reverse

to remove some unwanted things from the end of a list. The lists involved tend to be short (e.g., file names, package names, lines of user input, etc.) and the amount removed from the end of the list tends to be short (a trailing newline, the last part of a filename, extra spaces, etc.). I initially intended to replace all of these with Data.List.dropWhileEnd p. Unfortunately, my benchmarking showed that this had a substantial negative impact on performance. Data.List.dropWhileEnd is defined like this:

dropWhileEnd p = foldr (\x r -> if p x && null r then [] else x:r) []

This is lazy in the *spine* of the list--it can "flush its buffer" and produce list elements any time p x is found to be false. This is the best you can do if you need to process a very large list and don't want to have to load the whole thing into memory, and/or your predicate is *very* cheap. Unfortunately, it pays a steep price: for non-trivial p, it's strict in the *elements* of the list. This makes it unsuitable, from a performance standpoint, for most of the purposes for which I've seen reverse . dropWhile p . reverse used.

CONCEPT:

Add (by some name) a function that is lazy in the elements while strict in the spine:

dropWhileEndLE :: (a -> Bool) -> [a] -> [a] -- specification: dropWhileEndLE p = reverse . dropWhile p . reverse dropWhileEndLE p = foldr (\x r -> if null r && p x then [] else x:r) []

This is a good bit faster than the double-reversing version, presumably because it presumably allocates its buffer stack on the GHC stack rather than spraying junk across the heap.

If I were a Time Lord, I'd go back in time and add to the library, instead of dropWhileEnd as it is, a function with a name like

takeUntilLastSatisfying p = dropWhileEnd (not . p)

which has a name that explains better what it does, and I'd define dropWhileEnd to be dropWhileEndLE. But I'm not a Time Lord, so I'd like to hear what name or naming approach other people would recommend.

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

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

David Feuer

9:26 p.m.

I think the Foldable/Traversable work for 7.10 will help with a lot of these issues. Beyond that: make it faster if possible, make less-capable versions that are faster, and make it easier to find the right version for the job. A complicated way might be to use the "bundle" approach that the vector fusion folks have pioneered, but there are surely other ways. But I don't think any of that discussion takes away from the need to have really great list support. On Sun, Sep 28, 2014 at 9:11 PM, Carter Schonwald < carter.schonwald@gmail.com> wrote:

...

on the flip side, how can we encourage more usage of Data.Sequence ? :)

On Sun, Sep 28, 2014 at 8:34 PM, David Feuer wrote:

...
That decision is up to the user. Data.List provides a number of sequence functions that aren't efficient for lists, including take, drop, splitAt, init, last, reverse, zip, unzip, and (!!). dropWhileEnd and dropWhileLE aren't any worse, I don't think.

On Sun, Sep 28, 2014 at 6:59 PM, Greg Weber wrote:

...
Should the code be using Seq instead of a List?

On Sun, Sep 28, 2014 at 3:53 PM, David Feuer wrote:

...
One good option might be dropWhileR, to match Data.Sequence, but I'd only want to use that if the dropWhileEnd name were deprecated in favor of takeUntilLastSatisfying or whatever—otherwise it's just too confusing. On Sep 28, 2014 4:39 PM, "David Feuer" wrote:

...
BACKGROUND:

A somewhat common idiom I discovered digging around the GHC tree is the use of

reverse . dropWhile p . reverse

to remove some unwanted things from the end of a list. The lists involved tend to be short (e.g., file names, package names, lines of user input, etc.) and the amount removed from the end of the list tends to be short (a trailing newline, the last part of a filename, extra spaces, etc.). I initially intended to replace all of these with Data.List.dropWhileEnd p. Unfortunately, my benchmarking showed that this had a substantial negative impact on performance. Data.List.dropWhileEnd is defined like this:

dropWhileEnd p = foldr (\x r -> if p x && null r then [] else x:r) []

This is lazy in the *spine* of the list--it can "flush its buffer" and produce list elements any time p x is found to be false. This is the best you can do if you need to process a very large list and don't want to have to load the whole thing into memory, and/or your predicate is *very* cheap. Unfortunately, it pays a steep price: for non-trivial p, it's strict in the *elements* of the list. This makes it unsuitable, from a performance standpoint, for most of the purposes for which I've seen reverse . dropWhile p . reverse used.

CONCEPT:

Add (by some name) a function that is lazy in the elements while strict in the spine:

dropWhileEndLE :: (a -> Bool) -> [a] -> [a] -- specification: dropWhileEndLE p = reverse . dropWhile p . reverse dropWhileEndLE p = foldr (\x r -> if null r && p x then [] else x:r) []

This is a good bit faster than the double-reversing version, presumably because it presumably allocates its buffer stack on the GHC stack rather than spraying junk across the heap.

If I were a Time Lord, I'd go back in time and add to the library, instead of dropWhileEnd as it is, a function with a name like

takeUntilLastSatisfying p = dropWhileEnd (not . p)

which has a name that explains better what it does, and I'd define dropWhileEnd to be dropWhileEndLE. But I'm not a Time Lord, so I'd like to hear what name or naming approach other people would recommend.

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

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

John Lato

9:38 p.m.

I don't think we should be encouraging the use of Data.Sequence for file paths. An opaque OS-specific structure seems like the natural choice IMHO. (Incidentally I'd like to develop this as a userland library, if anyone would step forward to help with the Windows-specific stuff) On Mon, Sep 29, 2014 at 9:11 AM, Carter Schonwald < carter.schonwald@gmail.com> wrote:

...

on the flip side, how can we encourage more usage of Data.Sequence ? :)

On Sun, Sep 28, 2014 at 8:34 PM, David Feuer wrote:

...
That decision is up to the user. Data.List provides a number of sequence functions that aren't efficient for lists, including take, drop, splitAt, init, last, reverse, zip, unzip, and (!!). dropWhileEnd and dropWhileLE aren't any worse, I don't think.

On Sun, Sep 28, 2014 at 6:59 PM, Greg Weber wrote:

...
Should the code be using Seq instead of a List?

On Sun, Sep 28, 2014 at 3:53 PM, David Feuer wrote:

...
One good option might be dropWhileR, to match Data.Sequence, but I'd only want to use that if the dropWhileEnd name were deprecated in favor of takeUntilLastSatisfying or whatever—otherwise it's just too confusing. On Sep 28, 2014 4:39 PM, "David Feuer" wrote:

...
BACKGROUND:

A somewhat common idiom I discovered digging around the GHC tree is the use of

reverse . dropWhile p . reverse

to remove some unwanted things from the end of a list. The lists involved tend to be short (e.g., file names, package names, lines of user input, etc.) and the amount removed from the end of the list tends to be short (a trailing newline, the last part of a filename, extra spaces, etc.). I initially intended to replace all of these with Data.List.dropWhileEnd p. Unfortunately, my benchmarking showed that this had a substantial negative impact on performance. Data.List.dropWhileEnd is defined like this:

dropWhileEnd p = foldr (\x r -> if p x && null r then [] else x:r) []

This is lazy in the *spine* of the list--it can "flush its buffer" and produce list elements any time p x is found to be false. This is the best you can do if you need to process a very large list and don't want to have to load the whole thing into memory, and/or your predicate is *very* cheap. Unfortunately, it pays a steep price: for non-trivial p, it's strict in the *elements* of the list. This makes it unsuitable, from a performance standpoint, for most of the purposes for which I've seen reverse . dropWhile p . reverse used.

CONCEPT:

Add (by some name) a function that is lazy in the elements while strict in the spine:

dropWhileEndLE :: (a -> Bool) -> [a] -> [a] -- specification: dropWhileEndLE p = reverse . dropWhile p . reverse dropWhileEndLE p = foldr (\x r -> if null r && p x then [] else x:r) []

This is a good bit faster than the double-reversing version, presumably because it presumably allocates its buffer stack on the GHC stack rather than spraying junk across the heap.

If I were a Time Lord, I'd go back in time and add to the library, instead of dropWhileEnd as it is, a function with a name like

takeUntilLastSatisfying p = dropWhileEnd (not . p)

which has a name that explains better what it does, and I'd define dropWhileEnd to be dropWhileEndLE. But I'm not a Time Lord, so I'd like to hear what name or naming approach other people would recommend.

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

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

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

Felipe Lessa

29 Sep 29 Sep

9:19 a.m.

On 28-09-2014 22:38, John Lato wrote:

...

I don't think we should be encouraging the use of Data.Sequence for file paths. An opaque OS-specific structure seems like the natural choice IMHO.

(Incidentally I'd like to develop this as a userland library, if anyone would step forward to help with the Windows-specific stuff)

Do you mean system-filepath [1]? Cheers, [1] http://hackage.haskell.org/package/system-filepath -- Felipe.

John Lato

4:47 p.m.

On Sep 29, 2014 6:19 AM, "Felipe Lessa" wrote:

...

On 28-09-2014 22:38, John Lato wrote:

...
I don't think we should be encouraging the use of Data.Sequence for file paths. An opaque OS-specific structure seems like the natural choice

IMHO.

...

...
(Incidentally I'd like to develop this as a userland library, if anyone would step forward to help with the Windows-specific stuff)

Do you mean system-filepath [1]?

No. The api is ok, but performance is terrible because everything is a String. Traversing large directories in Haskell is orders of magnitude slower than it should be (unless you use posix-paths, which obviously isn't portable). I mean something that internally uses a RawFilePath on posix systems and some windows-specific thing on Windows.

Greg Weber

5:31 p.m.

...

...
Do you mean system-filepath [1]?

No. The api is ok, but performance is terrible because everything is a String. Traversing large directories in Haskell is orders of magnitude slower than it should be (unless you use posix-paths, which obviously isn't portable). I mean something that internally uses a RawFilePath on posix systems and some windows-specific thing on Windows.

I don't know how to reconcile this statement with how find-conduit was benchmarked to operate about as fast as GNU grep since it uses system-filepath. I am probably missing something important. http://hackage.haskell.org/package/find-conduit-0.4.1/docs/Data-Conduit-Find...

...

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

Bardur Arantsson

5:50 p.m.

On 2014-09-29 23:31, Greg Weber wrote:

...

...
...
Do you mean system-filepath [1]?

No. The api is ok, but performance is terrible because everything is a String. Traversing large directories in Haskell is orders of magnitude slower than it should be (unless you use posix-paths, which obviously isn't portable). I mean something that internally uses a RawFilePath on posix systems and some windows-specific thing on Windows.

I don't know how to reconcile this statement with how find-conduit was benchmarked to operate about as fast as GNU grep since it uses system-filepath. I am probably missing something important. http://hackage.haskell.org/package/find-conduit-0.4.1/docs/Data-Conduit-Find...

I'm not seeing exactly what "grep" has to do with "find"...? Did you mean to compare GNU find with "find-conduit"? Regards,

Greg Weber

6:11 p.m.

Yep, I didn't understand what was going on. The fast version of find-conduit was using a raw file path — Sent from Mailbox On Mon, Sep 29, 2014 at 2:50 PM, Bardur Arantsson wrote:

...

On 2014-09-29 23:31, Greg Weber wrote:

...
...
...
Do you mean system-filepath [1]?

No. The api is ok, but performance is terrible because everything is a String. Traversing large directories in Haskell is orders of magnitude slower than it should be (unless you use posix-paths, which obviously isn't portable). I mean something that internally uses a RawFilePath on posix systems and some windows-specific thing on Windows.

I don't know how to reconcile this statement with how find-conduit was benchmarked to operate about as fast as GNU grep since it uses system-filepath. I am probably missing something important. http://hackage.haskell.org/package/find-conduit-0.4.1/docs/Data-Conduit-Find...

I'm not seeing exactly what "grep" has to do with "find"...? Did you mean to compare GNU find with "find-conduit"? Regards, _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

John Lato

6:18 p.m.

So I'm understanding this properly, there is a fast version of find-conduit that uses RawFilePath, and the regular find-conduit that uses system-filepath? Are there benchmarks published that compare the two? On Sep 29, 2014 3:11 PM, "Greg Weber" wrote:

...

Yep, I didn't understand what was going on. The fast version of find-conduit was using a raw file path — Sent from Mailbox https://www.dropbox.com/mailbox

On Mon, Sep 29, 2014 at 2:50 PM, Bardur Arantsson wrote:

...
...
...
...
Do you mean system-filepath [1]?

No. The api is ok, but performance is terrible because everything is a String. Traversing large directories in Haskell is orders of magnitude slower than it should be (unless you use posix-paths, which obviously

isn't

...
portable). I mean something that internally uses a RawFilePath on

On 2014-09-29 23:31, Greg Weber wrote: posix

...
...
systems and some windows-specific thing on Windows.

I don't know how to reconcile this statement with how find-conduit was benchmarked to operate about as fast as GNU grep since it uses system-filepath. I am probably missing something important.

http://hackage.haskell.org/package/find-conduit-0.4.1/docs/Data-Conduit-Find...

...
I'm not seeing exactly what "grep" has to do with "find"...?

Did you mean to compare GNU find with "find-conduit"?

Regards,

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

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

David Feuer

12:20 a.m.

Since so many people like to see benchmarks, I figured I'd give you some. I tested nf (unlines . dropWhile__ isSpace . lines) li__ li1 is a lorem ipsum produced by an online lorem ipsum generator. li4 is the same thing, but with each space replaced by a bunch of spaces. dwr is dropWhileEndLE isSpace rdr is reverse . dropWhile isSpace . reverse dwe is dropWhileEnd isSpace The poor performance of dwe compared to rdr in li1 seems most likely to be caused by excessive use of isSpace, which takes quite a few tests to determine that a character is *not* a space. The prevalence of ' ' characters in li4 makes this less substantial. The difference between dwr and rdr is relatively small in li1, but it jumps way up in li4. I'm guessing this is because rdr sprays the entire string onto the heap before filtering out most of it, whereas dwr pushes everything onto the stack and only puts what it actually produces onto the heap. In any case, I think these demonstrate the practical utility of dropWhileEndLE for code that chooses to use lists for such purposes. benchmarking li1/dwr time 4.436 ms (4.405 ms .. 4.465 ms) 1.000 R² (0.999 R² .. 1.000 R²) mean 4.483 ms (4.481 ms .. 4.487 ms) std dev 9.562 μs (6.414 μs .. 14.38 μs) benchmarking li1/rdr time 5.061 ms (5.053 ms .. 5.071 ms) 1.000 R² (1.000 R² .. 1.000 R²) mean 5.062 ms (5.059 ms .. 5.069 ms) std dev 15.05 μs (7.515 μs .. 24.65 μs) benchmarking li1/dwe time 8.448 ms (8.441 ms .. 8.460 ms) 1.000 R² (1.000 R² .. 1.000 R²) mean 8.450 ms (8.444 ms .. 8.464 ms) std dev 24.61 μs (10.83 μs .. 46.48 μs) benchmarking li4/dwr time 19.52 ms (17.23 ms .. 21.93 ms) 0.919 R² (0.861 R² .. 0.983 R²) mean 18.11 ms (17.16 ms .. 19.46 ms) std dev 2.683 ms (1.772 ms .. 3.495 ms) variance introduced by outliers: 67% (severely inflated) benchmarking li4/rdr time 29.63 ms (27.63 ms .. 31.69 ms) 0.980 R² (0.955 R² .. 0.993 R²) mean 30.03 ms (28.31 ms .. 32.27 ms) std dev 4.152 ms (2.719 ms .. 5.921 ms) variance introduced by outliers: 57% (severely inflated) benchmarking li4/dwe time 28.52 ms (27.40 ms .. 29.72 ms) 0.994 R² (0.990 R² .. 0.997 R²) mean 27.99 ms (26.08 ms .. 28.94 ms) std dev 2.961 ms (1.437 ms .. 5.016 ms) variance introduced by outliers: 43% (moderately inflated)

3887

Age (days ago)

3888

Last active (days ago)

List overview

Download

13 comments

6 participants

participants (6)

Bardur Arantsson
Carter Schonwald
David Feuer
Felipe Lessa
Greg Weber
John Lato

Pre-proposal discussion: add a version of dropWhileEnd with different laziness properties to Data.List

tags

participants (6)