Proposal: Add foldrWithIndex and foldlWithIndex to Data.List - Libraries - Haskell.org

newer
[PROPOSAL] Adding Generics-based...

Proposal: Add foldrWithIndex and foldlWithIndex to Data.List

older
Future of "Text.Show.Functions"...

David Feuer

16 Oct 2014 16 Oct '14

5:14 p.m.

These functions can be lifted pretty much straight out of Data.Sequence. In particular, foldrWithIndex makes for a particularly nice expression of a fusing findIndices function, as is present in Data.Sequence.

Attachments:

attachment.html (text/html — 235 bytes)

Reply

Sign in to reply online Use email software

Show replies by date

David Feuer

16 Oct 16 Oct

5:21 p.m.

Actually, that proposal is firmly in the past. Let's *move* foldrWithIndex and foldlWithIndex from Data.Sequence to Data.Foldable! On Thu, Oct 16, 2014 at 1:14 PM, David Feuer wrote:

These functions can be lifted pretty much straight out of Data.Sequence. In particular, foldrWithIndex makes for a particularly nice expression of a fusing findIndices function, as is present in Data.Sequence.

Reply

Sign in to reply online Use email software

Edward Kmett

7:31 p.m.

I'm a pretty strong -1 on moving foldrWithIndex into Data.Foldable. Why? The only index Foldable can provide is an ordinal index starting at 0. The one folks _expect_ in many cases from Map k, IntMap and the like is the key. This introduces a huge source of potential confusion and new name conflicts for marginal benefit. -Edward On Thu, Oct 16, 2014 at 1:21 PM, David Feuer wrote:

Actually, that proposal is firmly in the past. Let's *move* foldrWithIndex and foldlWithIndex from Data.Sequence to Data.Foldable!

On Thu, Oct 16, 2014 at 1:14 PM, David Feuer wrote:

...
These functions can be lifted pretty much straight out of Data.Sequence. In particular, foldrWithIndex makes for a particularly nice expression of a fusing findIndices function, as is present in Data.Sequence.

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

Reply

Sign in to reply online Use email software

Alexander Berntsen

17 Oct 17 Oct

7:16 a.m.

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

On 16/10/14 21:31, Edward Kmett wrote:
> -1 on moving foldrWithIndex into Data.Foldable.
- -1 here too.

0 on moving it to Data.List. Not sure there's any benefit.

- -- 
Alexander
alexander@plaimi.net
https://secure.plaimi.net/~alexander
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/

iF4EAREIAAYFAlRAwlgACgkQRtClrXBQc7XE9wD8DFB1uYmBqUq2GPXv0zq3F1BS
I3FFKdQqbp7/mWpjxwgBAKQ/19mF4kDci0D8godYWzBRttMnIz0LqUJzecm78+6d
=YCzV
-----END PGP SIGNATURE-----

Reply

Sign in to reply online Use email software

Ganesh Sittampalam

22 Oct 22 Oct

7:13 p.m.

On 16/10/2014 18:14, David Feuer wrote:

These functions can be lifted pretty much straight out of Data.Sequence. In particular, foldrWithIndex makes for a particularly nice expression of a fusing findIndices function, as is present in Data.Sequence.

Do these do anything better than just adding indicies first with the standard zip [0..] idiom? Cheers, Ganesh

Reply

Sign in to reply online Use email software

David Feuer

7:19 p.m.

Yes, they do. In particular, the zip can only fuse with one of the two lists so the Ints could be unboxed, or fusion optimizations could happen with the list folded over, but not both. The fold_WithIndex function can manage both at once. That said, I think there have been some pretty good arguments against adding these, or at least against adding them with these names. On Oct 22, 2014 3:13 PM, "Ganesh Sittampalam" wrote:

On 16/10/2014 18:14, David Feuer wrote:

...
These functions can be lifted pretty much straight out of Data.Sequence. In particular, foldrWithIndex makes for a particularly nice expression of a fusing findIndices function, as is present in Data.Sequence.

Do these do anything better than just adding indicies first with the standard zip [0..] idiom?

Cheers,

Ganesh

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

Reply

Sign in to reply online Use email software

Ganesh Sittampalam

8:40 p.m.

I see, thanks. Could this be done via a rewrite rule from that idiom to an internal implementation function instead? On 22/10/2014 20:19, David Feuer wrote:

Yes, they do. In particular, the zip can only fuse with one of the two lists so the Ints could be unboxed, or fusion optimizations could happen with the list folded over, but not both. The fold_WithIndex function can manage both at once. That said, I think there have been some pretty good arguments against adding these, or at least against adding them with these names.

On Oct 22, 2014 3:13 PM, "Ganesh Sittampalam" mailto:ganesh@earth.li> wrote:

On 16/10/2014 18:14, David Feuer wrote:

These functions can be lifted pretty much straight out of Data.Sequence. In particular, foldrWithIndex makes for a particularly nice expression of a fusing findIndices function, as is present in Data.Sequence.

Do these do anything better than just adding indicies first with the standard zip [0..] idiom?

Cheers,

Ganesh

_________________________________________________ Libraries mailing list Libraries@haskell.org mailto:Libraries@haskell.org http://www.haskell.org/__mailman/listinfo/libraries http://www.haskell.org/mailman/listinfo/libraries

Reply

Sign in to reply online Use email software

David Feuer

10:13 p.m.

I think the answer is almost certainly no. The zipWith will turn into a foldr2, and there's no vaguely sure way of snatching that before it fuses with a build form and is lost forever. You'd end up with some very complicated rules that only did something useful when the phase of the moon was right. I'm pretty sure it's not worth trying. On Oct 22, 2014 4:40 PM, "Ganesh Sittampalam" wrote:

I see, thanks. Could this be done via a rewrite rule from that idiom to an internal implementation function instead?

On 22/10/2014 20:19, David Feuer wrote:

...
Yes, they do. In particular, the zip can only fuse with one of the two lists so the Ints could be unboxed, or fusion optimizations could happen with the list folded over, but not both. The fold_WithIndex function can manage both at once. That said, I think there have been some pretty good arguments against adding these, or at least against adding them with these names.

On Oct 22, 2014 3:13 PM, "Ganesh Sittampalam" mailto:ganesh@earth.li> wrote:

On 16/10/2014 18:14, David Feuer wrote:

These functions can be lifted pretty much straight out of Data.Sequence. In particular, foldrWithIndex makes for a particularly nice expression of a fusing findIndices function, as is present in Data.Sequence.

Do these do anything better than just adding indicies first with the standard zip [0..] idiom?

Cheers,

Ganesh

_________________________________________________ Libraries mailing list Libraries@haskell.org mailto:Libraries@haskell.org http://www.haskell.org/__mailman/listinfo/libraries http://www.haskell.org/mailman/listinfo/libraries

Reply

Sign in to reply online Use email software

Carter Schonwald

23 Oct 23 Oct

5:32 a.m.

i hate always asking this question: but do we have an example benchmark illustrating there being a substantial difference in peformance if fold(l/r)withIndex is defined directly rather than via the more "naive" composition? On Wed, Oct 22, 2014 at 6:13 PM, David Feuer wrote:

I think the answer is almost certainly no. The zipWith will turn into a foldr2, and there's no vaguely sure way of snatching that before it fuses with a build form and is lost forever. You'd end up with some very complicated rules that only did something useful when the phase of the moon was right. I'm pretty sure it's not worth trying. On Oct 22, 2014 4:40 PM, "Ganesh Sittampalam" wrote:

...
I see, thanks. Could this be done via a rewrite rule from that idiom to an internal implementation function instead?

On 22/10/2014 20:19, David Feuer wrote:

...
Yes, they do. In particular, the zip can only fuse with one of the two lists so the Ints could be unboxed, or fusion optimizations could happen with the list folded over, but not both. The fold_WithIndex function can manage both at once. That said, I think there have been some pretty good arguments against adding these, or at least against adding them with these names.

On Oct 22, 2014 3:13 PM, "Ganesh Sittampalam" mailto:ganesh@earth.li> wrote:

On 16/10/2014 18:14, David Feuer wrote:

These functions can be lifted pretty much straight out of Data.Sequence. In particular, foldrWithIndex makes for a particularly nice expression of a fusing findIndices function, as is present in Data.Sequence.

Do these do anything better than just adding indicies first with the standard zip [0..] idiom?

Cheers,

Ganesh

_________________________________________________ Libraries mailing list Libraries@haskell.org mailto:Libraries@haskell.org http://www.haskell.org/__mailman/listinfo/libraries http://www.haskell.org/mailman/listinfo/libraries

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

Reply

Sign in to reply online Use email software

David Feuer

5:55 p.m.

Yes. Forgive the strange names below. The zip version is 3 times as slow on 7.8.3. I did some horrible hacks to convince 7.8.3 to compile it more like 7.9 would (I don't have Criterion set up for 7.9), and I got it down to only twice as slow. Still, that does not seem so wonderful. {-# LANGUAGE BangPatterns #-} module Main where import Criterion.Main foldlWithIndex :: (Int -> b -> el -> b) -> b -> [el] -> b foldlWithIndex f init xs = foldr go snd xs (0, init) where go x r (!n, a) = r (n+1, f n a x) {-# INLINE zippily #-} -- Taking this out makes it slower zippily :: (Int -> b -> el -> b) -> b -> [el] -> b zippily f init xs = foldl (\acc (!n,x) -> f n acc x) init (zip [0..] xs) sumspecialevens = foldlWithIndex (\n a x -> if even n then a+3*x else a+x) (0::Int) weirdspecialevens=foldlWithIndex (\n a x -> if x `rem` 16 == 0 then a+3*n else a + x) (0::Int) stupidsum = zippily (\n a x -> if even n then a+3*x else a+x) (0::Int) weirdstupidsum=zippily (\n a x -> if x `rem` 16 == 0 then a+3*n else a + x) (0::Int) main = defaultMain $ [ bgroup "useAll" [ bench "fwi" $ nf (\n -> sumspecialevens [1..n]) 1000000 ,bench "zip" $ nf (\n -> stupidsum [1..n]) 1000000 ] ,bgroup "useSome" [ bench "fwi" $ nf (\n -> weirdspecialevens [1..n]) 1000000 ,bench "zip" $ nf (\n -> weirdstupidsum [1..n]) 1000000 ] ] On Thu, Oct 23, 2014 at 1:32 AM, Carter Schonwald < carter.schonwald@gmail.com> wrote:

i hate always asking this question: but do we have an example benchmark illustrating there being a substantial difference in peformance if fold(l/r)withIndex is defined directly rather than via the more "naive" composition?

On Wed, Oct 22, 2014 at 6:13 PM, David Feuer wrote:

...
I think the answer is almost certainly no. The zipWith will turn into a foldr2, and there's no vaguely sure way of snatching that before it fuses with a build form and is lost forever. You'd end up with some very complicated rules that only did something useful when the phase of the moon was right. I'm pretty sure it's not worth trying. On Oct 22, 2014 4:40 PM, "Ganesh Sittampalam" wrote:

...
I see, thanks. Could this be done via a rewrite rule from that idiom to an internal implementation function instead?

...
Yes, they do. In particular, the zip can only fuse with one of the two lists so the Ints could be unboxed, or fusion optimizations could happen with the list folded over, but not both. The fold_WithIndex function can manage both at once. That said, I think there have been some pretty good arguments against adding these, or at least against adding them with these names.

On Oct 22, 2014 3:13 PM, "Ganesh Sittampalam" mailto:ganesh@earth.li> wrote:

On 16/10/2014 18:14, David Feuer wrote:

These functions can be lifted pretty much straight out of Data.Sequence. In particular, foldrWithIndex makes for a particularly nice expression of a fusing findIndices function, as is present in Data.Sequence.

Do these do anything better than just adding indicies first with

On 22/10/2014 20:19, David Feuer wrote: the

...
standard zip [0..] idiom?

Cheers,

Ganesh

_________________________________________________ Libraries mailing list Libraries@haskell.org mailto:Libraries@haskell.org http://www.haskell.org/__mailman/listinfo/libraries http://www.haskell.org/mailman/listinfo/libraries

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

Reply

Sign in to reply online Use email software

3910

Age (days ago)

3917

Last active (days ago)

Download

9 comments

5 participants

tags

participants (5)

Alexander Berntsen
Carter Schonwald
David Feuer
Edward Kmett
Ganesh Sittampalam