Data.Map.unzip?

older
Conversion between STRef RealWorld...

Joachim Breitner

5 Dec 2014 5 Dec '14

4:43 p.m.

Hi, did anyone else ever wanted to have a function Data.Map.unzip :: Map k (a, b) -> (Map k a , Map k b) and possibly unzipN for N >= 3? Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

Attachments:

signature.asc (application/pgp-signature — 819 bytes)

Show replies by date

Eric Mertens

5 Dec 5 Dec

5:09 p.m.

Would it be significantly better than just having/using the following definition? unzipF :: Functor f => f (a, b) -> (f a, f b) unzipF x = (fmap fst x, fmap snd x)

David Feuer

5:17 p.m.

On Dec 5, 2014 5:09 PM, "Eric Mertens" wrote:

...

Would it be significantly better than just having/using the following

definition?

...

unzipF :: Functor f => f (a, b) -> (f a, f b) unzipF x = (fmap fst x, fmap snd x)

It probably depends on how it's being used. Your way potentially does two passes, and may keep some things live longer than necessary.

Joachim Breitner

5:33 p.m.

New subject: Data.Functor.unzipF (Was: Data.Map.unzip?)

Hi, Am Freitag, den 05.12.2014, 14:09 -0800 schrieb Eric Mertens:

...

Would it be significantly better than just having/using the following definition?

unzipF :: Functor f => f (a, b) -> (f a, f b) unzipF x = (fmap fst x, fmap snd x)

yes, I guess that would be sufficient. Something for Data.Functor? Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

Henning Thielemann

5:36 p.m.

New subject: Data.Functor.unzipF (Was: Data.Map.unzip?)

On Fri, 5 Dec 2014, Joachim Breitner wrote:

...

Am Freitag, den 05.12.2014, 14:09 -0800 schrieb Eric Mertens:

...
Would it be significantly better than just having/using the following definition?

unzipF :: Functor f => f (a, b) -> (f a, f b) unzipF x = (fmap fst x, fmap snd x)

yes, I guess that would be sufficient. Something for Data.Functor?

Btw. you can already import it from here: http://hackage.haskell.org/package/utility-ht-0.0.10/docs/Control-Functor-HT...

David Feuer

5:38 p.m.

New subject: Data.Functor.unzipF (Was: Data.Map.unzip?)

On Fri, Dec 5, 2014 at 5:33 PM, Joachim Breitner wrote:

...

Hi,

Am Freitag, den 05.12.2014, 14:09 -0800 schrieb Eric Mertens:

...
Would it be significantly better than just having/using the following definition?

unzipF :: Functor f => f (a, b) -> (f a, f b) unzipF x = (fmap fst x, fmap snd x)

yes, I guess that would be sufficient. Something for Data.Functor?

This looks like it should be the default implementation of an Unzippable class, rather than a standalone function.

Joachim Breitner

5:48 p.m.

New subject: Data.Functor.unzipF (Was: Data.Map.unzip?)

Hi, Am Freitag, den 05.12.2014, 17:38 -0500 schrieb David Feuer:

...

Am Freitag, den 05.12.2014, 14:09 -0800 schrieb Eric Mertens: > Would it be significantly better than just having/using the following > definition? > > unzipF :: Functor f => f (a, b) -> (f a, f b) > unzipF x = (fmap fst x, fmap snd x)

yes, I guess that would be sufficient. Something for Data.Functor?

This looks like it should be the default implementation of an Unzippable class, rather than a standalone function.

Clearly, every Functor isunzippable. What do you expect to be Unzippable that is not a functor? Or are you worried about performance, and allow better implementations? Then I hope we can do that without touching the desired API, e.g. using RULEs. Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

David Feuer

6:08 p.m.

New subject: Data.Functor.unzipF (Was: Data.Map.unzip?)

I hate using RULES for this sort of thing. Logically, we should probably have Unzippable f => Functor f, but that's unlikely to fly. We could do that evil default signature thing for an Unzippable class. On Dec 5, 2014 5:49 PM, "Joachim Breitner" wrote:

...

Hi,

Am Freitag, den 05.12.2014, 17:38 -0500 schrieb David Feuer:

...
Am Freitag, den 05.12.2014, 14:09 -0800 schrieb Eric Mertens: > Would it be significantly better than just having/using the following > definition? > > unzipF :: Functor f => f (a, b) -> (f a, f b) > unzipF x = (fmap fst x, fmap snd x)

yes, I guess that would be sufficient. Something for Data.Functor?

This looks like it should be the default implementation of an Unzippable class, rather than a standalone function.

Clearly, every Functor isunzippable.

What do you expect to be Unzippable that is not a functor?

Or are you worried about performance, and allow better implementations? Then I hope we can do that without touching the desired API, e.g. using RULEs.

Greetings, Joachim

-- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

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

David Feuer

6:24 p.m.

New subject: Data.Functor.unzipF (Was: Data.Map.unzip?)

Oh, you're right, there probably isn't anything unzippable that's not a functor, unless you go really wild. So could we just add unzip to the Functor class? On Dec 5, 2014 5:49 PM, "Joachim Breitner" wrote:

...

Hi,

Am Freitag, den 05.12.2014, 17:38 -0500 schrieb David Feuer:

...
Am Freitag, den 05.12.2014, 14:09 -0800 schrieb Eric Mertens: > Would it be significantly better than just having/using the following > definition? > > unzipF :: Functor f => f (a, b) -> (f a, f b) > unzipF x = (fmap fst x, fmap snd x)

yes, I guess that would be sufficient. Something for Data.Functor?

This looks like it should be the default implementation of an Unzippable class, rather than a standalone function.

Clearly, every Functor isunzippable.

What do you expect to be Unzippable that is not a functor?

Or are you worried about performance, and allow better implementations? Then I hope we can do that without touching the desired API, e.g. using RULEs.

Greetings, Joachim

-- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

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

Joachim Breitner

7 p.m.

New subject: Data.Functor.unzipF (Was: Data.Map.unzip?)

Hi, Am Freitag, den 05.12.2014, 18:24 -0500 schrieb David Feuer:

...

Oh, you're right, there probably isn't anything unzippable that's not a functor, unless you go really wild. So could we just add unzip to the Functor class?

I still believe a stand-alone function makes more sense. Otherwise we’d be increasing the size of the Functor dictionary for very little gain (because the function is not so frequent, and there are probably not many instances where there is a significant performance gain to be gained). Greetings, Joachim

...

-- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

John Lato

9:18 p.m.

New subject: Data.Functor.unzipF (Was: Data.Map.unzip?)

Data.Vector.Unboxed.Vector is unzippable and not a Functor. That's the only case I can think of now. On 15:24, Fri, Dec 5, 2014 David Feuer wrote:

...

Oh, you're right, there probably isn't anything unzippable that's not a functor, unless you go really wild. So could we just add unzip to the Functor class? On Dec 5, 2014 5:49 PM, "Joachim Breitner" wrote:

...
Hi,

Am Freitag, den 05.12.2014, 17:38 -0500 schrieb David Feuer:

...
Am Freitag, den 05.12.2014, 14:09 -0800 schrieb Eric Mertens: > Would it be significantly better than just having/using the following > definition? > > unzipF :: Functor f => f (a, b) -> (f a, f b) > unzipF x = (fmap fst x, fmap snd x)

yes, I guess that would be sufficient. Something for Data.Functor?

This looks like it should be the default implementation of an Unzippable class, rather than a standalone function.

Clearly, every Functor isunzippable.

What do you expect to be Unzippable that is not a functor?

Or are you worried about performance, and allow better implementations? Then I hope we can do that without touching the desired API, e.g. using RULEs.

Greetings, Joachim

-- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

_______________________________________________ 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

Joachim Breitner

6 Dec 6 Dec

5:46 a.m.

New subject: Data.Functor.unzipF (Was: Data.Map.unzip?)

Hi, right, any any other container having special requirements on the contained type, e.g. Data.Set. Greetings, Joachim Am 6. Dezember 2014 03:18:09 MEZ, schrieb John Lato :

...

Data.Vector.Unboxed.Vector is unzippable and not a Functor. That's the only case I can think of now.

On 15:24, Fri, Dec 5, 2014 David Feuer wrote:

...
Oh, you're right, there probably isn't anything unzippable that's not a functor, unless you go really wild. So could we just add unzip to the Functor class? On Dec 5, 2014 5:49 PM, "Joachim Breitner" wrote:

...
Hi,

Am Freitag, den 05.12.2014, 17:38 -0500 schrieb David Feuer:

...
Am Freitag, den 05.12.2014, 14:09 -0800 schrieb Eric

Mertens:

...
> Would it be significantly better than just having/using

the

...
following > definition? > > unzipF :: Functor f => f (a, b) -> (f a, f b) > unzipF x = (fmap fst x, fmap snd x)

yes, I guess that would be sufficient. Something for Data.Functor?

This looks like it should be the default implementation of an Unzippable class, rather than a standalone function.

Clearly, every Functor isunzippable.

What do you expect to be Unzippable that is not a functor?

Or are you worried about performance, and allow better implementations? Then I hope we can do that without touching the desired API, e.g. using RULEs.

Greetings, Joachim

-- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

_______________________________________________ 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

Andreas Abel

4:25 a.m.

On 05.12.2014 22:43, Joachim Breitner wrote:

...

did anyone else ever wanted to have a function

Data.Map.unzip :: Map k (a, b) -> (Map k a , Map k b)

Yes, I wanted it, and was annoyed by its absence, and the fact that I had to fall back to the solution (for efficiency reasons). Cheers, Andreas -- Andreas Abel <>< Du bist der geliebte Mensch. Department of Computer Science and Engineering Chalmers and Gothenburg University, Sweden andreas.abel@gu.se http://www2.tcs.ifi.lmu.de/~abel/

Joachim Breitner

5:50 a.m.

Hi, Am 6. Dezember 2014 10:25:03 MEZ, schrieb Andreas Abel :

...

On 05.12.2014 22:43, Joachim Breitner wrote:

...
did anyone else ever wanted to have a function

Data.Map.unzip :: Map k (a, b) -> (Map k a , Map k b)

Yes, I wanted it, and was annoyed by its absence, and the fact that I had to fall back to the solution (for efficiency reasons).

although I wonder how big the difference would be. At least both versions will re-use the tree-structure. It probably depends on how its used... Greetings, Joachim

Henning Thielemann

6:08 a.m.

On Sat, 6 Dec 2014, Joachim Breitner wrote:

...

Am 6. Dezember 2014 10:25:03 MEZ, schrieb Andreas Abel :

...
On 05.12.2014 22:43, Joachim Breitner wrote:

...
did anyone else ever wanted to have a function

Data.Map.unzip :: Map k (a, b) -> (Map k a , Map k b)

Yes, I wanted it, and was annoyed by its absence, and the fact that I had to fall back to the solution (for efficiency reasons).

although I wonder how big the difference would be. At least both versions will re-use the tree-structure. It probably depends on how its used...

Consider the following example let (bigs,smalls) = unzip mix in do f bigs g smalls 'bigs' contains a great amount of data, and thus you prefer that it can be garbage collected as 'f' consumes it. If 'unzip' is actually (fmap fst mix, fmap snd mix) then 'mix' (and thus all big data) will be kept in memory until 'g' starts processing.

Joachim Breitner

7:08 a.m.

Hi, Am Samstag, den 06.12.2014, 12:08 +0100 schrieb Henning Thielemann:

...

Consider the following example

let (bigs,smalls) = unzip mix in do f bigs g smalls

'bigs' contains a great amount of data, and thus you prefer that it can be garbage collected as 'f' consumes it. If 'unzip' is actually

(fmap fst mix, fmap snd mix)

then 'mix' (and thus all big data) will be kept in memory until 'g' starts processing.

on a first glance, I agree. But I wouldn’t trust my first glance until I investigated the issue. It also depends on the particular implementation of unzip. You assume that after `f bigs` is done, nothing references mix any more. But `smalls` is going to be a thunk referencing mix, so mix will only be GC’ed _while g is forcing smalls_, not earlier. And if `g` is just a lookup in a tree, and `smalls` is used later as well, then the parts of the tree not traversed will still reference `mix`. It might be possible to implement unzip in a way so that smalls gets fully created while bigs is being forced. But that will require careful code and analysis to verify that it works. And even then a partial evaluation of `bigs` might break this expectation. OTOH, the `(fmap fst mix, fmap snd mix)` might be more efficient if only one component will actually be used and/or if `mix` is going to stay live anyways. Who knows. Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

Joachim Breitner

7:29 a.m.

Hi, Am Samstag, den 06.12.2014, 13:08 +0100 schrieb Joachim Breitner:

...

on a first glance, I agree. But I wouldn’t trust my first glance until I investigated the issue.

I investigate the case for lists, which have a specialized unzip: unzip :: [(a,b)] -> ([a],[b]) {-# INLINE unzip #-} unzip = foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[]) I started with defining

...

let list1 = map (\c -> (c, Data.Char.ord c)) "hallo" let (uz1, uz2) = unzip list1 and then forcing list1 and uz1, but not uz2.

This gave me unzip.pdf, and you can clearly see that uz2 still references all all of the values, and a whole bunch of thunks and other annoying stuff. But: That is not due to unzip, but rather due to the lazy binding in

...

let (uz1, uz2) = unzip list1

If I then also force "head uz2", I get unzip_nice.pdf, where indeed uz2, despite not being forced, does not evaluate anything from uz1 any more. The same with

...

let !(uz1, uz2) = unzip list1

I assume this works due to GHC “Fixing some space leaks with a garbage collector“. So my conclusion is: Yes, specialized unzips do behave better behavior, but exploiting this behavior requires non-trivial knowledge about Haskell. In particular, the difference between a lazy and a strict tuple pattern. (Disclaimer: It is likely that "let (uz1, uz2) = unzip list1" would have worked in compiled code better than in GHCi due to either strictness analysis and/or “Fixing some space leaks with a garbage collector“ kicking in.) Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

3935

Age (days ago)

3936

Last active (days ago)

List overview

Download

16 comments

6 participants

participants (6)

Andreas Abel
David Feuer
Eric Mertens
Henning Thielemann
Joachim Breitner
John Lato

Data.Map.unzip?

tags

participants (6)