[announcement] filtrable: class of filtrable containers

older
Haskell.org Committee Financial...

M Farkas-Dyck

17 Feb 2016 17 Feb '16

2:02 a.m.

I quietly posted this library to Hackage nearly a year ago, but lately learned that some seeking such a package had difficulty finding it, so i announce it now ☺ https://hackage.haskell.org/package/filtrable class Functor f => Filtrable f where mapMaybe :: (a -> Maybe b) -> f a -> f b catMaybes :: f (Maybe a) -> f a filter :: (a -> Bool) -> f a -> f a For laws, see docs on Hackage.

Show replies by date

Joachim Breitner

17 Feb 17 Feb

3:32 a.m.

New subject: [announcement] filtrable: class of filtrable containers

Hi M, Am Dienstag, den 16.02.2016, 23:02 -0800 schrieb M Farkas-Dyck:

...

I quietly posted this library to Hackage nearly a year ago, but lately learned that some seeking such a package had difficulty finding it, so i announce it now ☺

https://hackage.haskell.org/package/filtrable

class Functor f => Filtrable f where mapMaybe :: (a -> Maybe b) -> f a -> f b catMaybes :: f (Maybe a) -> f a filter :: (a -> Bool) -> f a -> f a

For laws, see docs on Hackage.

You might want to add laws in the style of If this is also a Foldable, then toList . mapMaybe f = mapMapybe f . toList toList . catMaybes = catMaybes . toList toList . filter f = filter f . toList which would fix the behavior quite tightly. I wonder if these laws (together with a “well behaved” Foldable) still allow any unexpected behavior. And also whether they follow from your laws (but I don’t think so; mapMaybe could do something mean such as duplicating elements if there is at least one Nothing in the result). Do you plan to add instances for all the other data structures in base that are filtrable? Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

Oleg Grenrus

3:49 a.m.

Hi M, - I’d also like to see instances for types in containers, unordered-containers, vector and semigroup. - The OtherLicense seems a bit scary (even the contents aren’t), is there a good reason why you don’t use more familiar MIT or BSD3? If you don’t mind I can make a PR for the instances. And one more comment: The law: filter f = mapMaybe (liftA2 (<$) id (guard ∘ f)) is very hard to understand. filter f = mapMaybe (\x -> if f x then Just x else Nothing) is longer, but IMHO much simpler. Or if you really want to code golf, then maybe: filter f = mapMaybe (mfilter f . Just) - Oleg

...

On 17 Feb 2016, at 10:32, Joachim Breitner wrote:

Hi M,

Am Dienstag, den 16.02.2016, 23:02 -0800 schrieb M Farkas-Dyck:

...
I quietly posted this library to Hackage nearly a year ago, but lately learned that some seeking such a package had difficulty finding it, so i announce it now ☺

https://hackage.haskell.org/package/filtrable

class Functor f => Filtrable f where mapMaybe :: (a -> Maybe b) -> f a -> f b catMaybes :: f (Maybe a) -> f a filter :: (a -> Bool) -> f a -> f a

For laws, see docs on Hackage.

You might want to add laws in the style of

If this is also a Foldable, then toList . mapMaybe f = mapMapybe f . toList toList . catMaybes = catMaybes . toList toList . filter f = filter f . toList

which would fix the behavior quite tightly.

I wonder if these laws (together with a “well behaved” Foldable) still allow any unexpected behavior.

And also whether they follow from your laws (but I don’t think so; mapMaybe could do something mean such as duplicating elements if there is at least one Nothing in the result).

Do you plan to add instances for all the other data structures in base that are filtrable?

Greetings, Joachim

-- Joachim “nomeata” Breitner mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

Kosyrev Serge

7:21 a.m.

Oleg Grenrus writes:

...

And one more comment:

The law:

filter f = mapMaybe (liftA2 (<$) id (guard ∘ f))

is very hard to understand.

filter f = mapMaybe (\x -> if f x then Just x else Nothing)

Wow, the difference is simply astounding for me. Does this monster liftA2 (<$) id (guard ∘ f) really stand for \x -> if f x then Just x else Nothing ? Is there really no simpler "compact" representation for this trivial idea in Haskell? -- с уважениeм / respectfully, Косырев Сергей

Joachim Breitner

7:28 a.m.

New subject: [announcement] filtrable: class of filtrable containers

Hi, Am Mittwoch, den 17.02.2016, 15:21 +0300 schrieb Kosyrev Serge:

...

Does this monster

liftA2 (<$) id (guard ∘ f)

really stand for

\x -> if f x then Just x else Nothing

?

Is there really no simpler "compact" representation for this trivial idea in Haskell?

I vaguely remember a discussion about adding a combinator doing that to the libray, and some googling turned out that there was a proposal 6 years ago by... me: https://ghc.haskell.org/trac/ghc/ticket/3446 (Well, not quite, the type was justIf :: a -> Bool -> Just a and not justIf :: a -> (a -> Bool) -> Just a and this shows that there are probably too many variants to warrant an addition of some or all of them to the standard library). The corresponding discussion on the libraries¹ list discussed some of the variants, and also turned up an even older equivalent proposal by Henning Thielemann² from 12 years ago. Greetings, Joachim ¹ https://mail.haskell.org/pipermail/libraries/2009-August/012413.html ² https://mail.haskell.org/pipermail/libraries/2004-July/002381.html -- Joachim “nomeata” Breitner mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

Sean Leather

3:50 a.m.

Hi Joachim, On Wed, Feb 17, 2016 at 10:32 AM, Joachim Breitner wrote:

...

Am Dienstag, den 16.02.2016, 23:02 -0800 schrieb M Farkas-Dyck:

...
I quietly posted this library to Hackage nearly a year ago, but lately learned that some seeking such a package had difficulty finding it, so i announce it now ☺

https://hackage.haskell.org/package/filtrable

class Functor f => Filtrable f where mapMaybe :: (a -> Maybe b) -> f a -> f b catMaybes :: f (Maybe a) -> f a filter :: (a -> Bool) -> f a -> f a

For laws, see docs on Hackage.

You might want to add laws in the style of

If this is also a Foldable, then toList . mapMaybe f = mapMapybe f . toList toList . catMaybes = catMaybes . toList toList . filter f = filter f . toList

which would fix the behavior quite tightly.

Why would you specify laws for Filtrable w.r.t. Foldable, when Foldable is not part of the definition? There is at least one potential application for Filtrable for a type that isn't a Foldable: https://github.com/reflex-frp/reflex/pull/44 Regards, Sean

Oleg Grenrus

3:57 a.m.

Hi, Sean, I guess that’s why there is a disclaimer: “If this is **also** a Foldable, then” Another similar example is `Hashable` which doesn’t require things to be `Eq`, yet states the infectivity law. - Oleg

...

On 17 Feb 2016, at 10:50, Sean Leather wrote:

Hi Joachim,

On Wed, Feb 17, 2016 at 10:32 AM, Joachim Breitner wrote: Am Dienstag, den 16.02.2016, 23:02 -0800 schrieb M Farkas-Dyck:

...
I quietly posted this library to Hackage nearly a year ago, but lately learned that some seeking such a package had difficulty finding it, so i announce it now ☺

https://hackage.haskell.org/package/filtrable https://hackage.haskell.org/package/filtrable

class Functor f => Filtrable f where mapMaybe :: (a -> Maybe b) -> f a -> f b catMaybes :: f (Maybe a) -> f a filter :: (a -> Bool) -> f a -> f a

For laws, see docs on Hackage.

You might want to add laws in the style of

If this is also a Foldable, then toList . mapMaybe f = mapMapybe f . toList toList . catMaybes = catMaybes . toList toList . filter f = filter f . toList

which would fix the behavior quite tightly.

Why would you specify laws for Filtrable w.r.t. Foldable, when Foldable is not part of the definition?

There is at least one potential application for Filtrable for a type that isn't a Foldable:

https://github.com/reflex-frp/reflex/pull/44 https://github.com/reflex-frp/reflex/pull/44

Regards, Sean _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

Christopher Allen

11:30 a.m.

...

Laws

Not for nothing, but there's prior art here for a "filterable" with laws. https://hackage.haskell.org/package/witherable On Wed, Feb 17, 2016 at 2:32 AM, Joachim Breitner wrote:

...

Hi M,

Am Dienstag, den 16.02.2016, 23:02 -0800 schrieb M Farkas-Dyck:

...
I quietly posted this library to Hackage nearly a year ago, but lately learned that some seeking such a package had difficulty finding it, so i announce it now ☺

https://hackage.haskell.org/package/filtrable

class Functor f => Filtrable f where mapMaybe :: (a -> Maybe b) -> f a -> f b catMaybes :: f (Maybe a) -> f a filter :: (a -> Bool) -> f a -> f a

For laws, see docs on Hackage.

You might want to add laws in the style of

If this is also a Foldable, then toList . mapMaybe f = mapMapybe f . toList toList . catMaybes = catMaybes . toList toList . filter f = filter f . toList

which would fix the behavior quite tightly.

I wonder if these laws (together with a “well behaved” Foldable) still allow any unexpected behavior.

And also whether they follow from your laws (but I don’t think so; mapMaybe could do something mean such as duplicating elements if there is at least one Nothing in the result).

Do you plan to add instances for all the other data structures in base that are filtrable?

Greetings, Joachim

-- Joachim “nomeata” Breitner mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

-- Chris Allen Currently working on http://haskellbook.com

Sebastian Dröge

3:59 a.m.

New subject: [announcement] filtrable: class of filtrable containers

On Di, 2016-02-16 at 23:02 -0800, M Farkas-Dyck wrote:

...

I quietly posted this library to Hackage nearly a year ago, but lately learned that some seeking such a package had difficulty finding it, so i announce it now ☺

https://hackage.haskell.org/package/filtrable

class Functor f => Filtrable f where mapMaybe :: (a -> Maybe b) -> f a -> f b catMaybes :: f (Maybe a) -> f a filter :: (a -> Bool) -> f a -> f a

For laws, see docs on Hackage.

This looks very similar to the Witherable class from https://hackage.haskell.org/package/witherable : class Traversable t => Witherable t where wither :: Applicative f => (a -> f (Maybe b)) -> t a -> f (t b) wither f = fmap catMaybes . T.traverse f mapMaybe :: (a -> Maybe b) -> t a -> t b mapMaybe = mapMaybeOf wither catMaybes :: t (Maybe a) -> t a catMaybes = catMaybesOf wither filterA :: Applicative f => (a -> f Bool) -> t a -> f (t a) filterA = filterAOf wither filter :: (a -> Bool) -> t a -> t a filter = filterOf wither

M Farkas-Dyck

12:16 p.m.

On 17/02/2016, Joachim Breitner wrote:

...

You might want to add laws in the style of

If this is also a Foldable, then toList . mapMaybe f = mapMapybe f . toList toList . catMaybes = catMaybes . toList toList . filter f = filter f . toList

Shall do.

...

Do you plan to add instances for all the other data structures in base that are filtrable?

Yes, if i missed any, please let me know which ☺ On 17/02/2016, Oleg Grenrus wrote:

...

- I’d also like to see instances for types in containers, unordered-containers, vector and semigroup.

I was hoping to have no deps but base... alas, Cabal and Hackage seem to have no good way to have instance deps, so the instances must be in either the package defining the class or the one defining the types which are instances of it.

...

If you don’t mind I can make a PR for the instances.

Feel free to do so for containers and vector at least. I may want this to not transitively depend on unordered-containers → hashable → text, but if enough potential users want these instances i'll include them (containers and vector come with GHC so it's not so bad). What types in semigroups would you add instances of?

...

- The OtherLicense seems a bit scary (even the contents aren’t), is there a good reason why you don’t use more familiar MIT or BSD3?

Too verbose. I might use ISC if it weren't also an OtherLicense...

...

The law:

filter f = mapMaybe (liftA2 (<$) id (guard ∘ f))

is very hard to understand.

Rewritten. On 17/02/2016, Simon Jakobi wrote:

...

your package looks very similar to http://hackage.haskell.org/package/witherable!

Witherable has Traversable superclass, but some Filtrable types may not be Traversable.

Bryan Richter

12:31 p.m.

New subject: [announcement] filtrable: class of filtrable containers

On Wed, Feb 17, 2016 at 09:16:01AM -0800, M Farkas-Dyck wrote:

...

On 17/02/2016, Oleg Grenrus wrote:

...
- The OtherLicense seems a bit scary (even the contents aren’t), is there a good reason why you don’t use more familiar MIT or BSD3?

Too verbose. I might use ISC if it weren't also an OtherLicense...

I appreciate the feeling. My personal favorite is the WTFPL. :) However, you are trading verbosity in one particular reference file for increased obscurity and adoption friction for the library as a whole. They may be more verbose, but MIT and BSD3 are very well understood and accepted, and for the audience for whom they are intended, verbosity is just another term for "completeness".

M Farkas-Dyck

7:06 p.m.

On 17/02/2016, Bryan Richter wrote:

...

They may be more verbose, but MIT and BSD3 are very well understood and accepted, and for the audience for whom they are intended, verbosity is just another term for "completeness".

Yeah, i may as well release it under BSD3; it's all a farce as far as i care. Done.

amindfv＠gmail.com

1:34 p.m.

New subject: Instance deps (was: [announcement] filtrable: class of filtrable containers)

...

El 17 feb 2016, a las 12:16, M Farkas-Dyck escribió:

...
On 17/02/2016, Joachim Breitner wrote: You might want to add laws in the style of

If this is also a Foldable, then toList . mapMaybe f = mapMapybe f . toList toList . catMaybes = catMaybes . toList toList . filter f = filter f . toList

Shall do.

...
Do you plan to add instances for all the other data structures in base that are filtrable?

Yes, if i missed any, please let me know which ☺

...
On 17/02/2016, Oleg Grenrus wrote: - I’d also like to see instances for types in containers, unordered-containers, vector and semigroup.

I was hoping to have no deps but base... alas, Cabal and Hackage seem to have no good way to have instance deps, so the instances must be in either the package defining the class or the one defining the types which are instances of it.

Are there any existing proposals for a solution to this? Tom

...

...
If you don’t mind I can make a PR for the instances.

Feel free to do so for containers and vector at least. I may want this to not transitively depend on unordered-containers → hashable → text, but if enough potential users want these instances i'll include them (containers and vector come with GHC so it's not so bad). What types in semigroups would you add instances of?

...
- The OtherLicense seems a bit scary (even the contents aren’t), is there a good reason why you don’t use more familiar MIT or BSD3?

Too verbose. I might use ISC if it weren't also an OtherLicense...

...
The law:

filter f = mapMaybe (liftA2 (<$) id (guard ∘ f))

is very hard to understand.

Rewritten.

...
On 17/02/2016, Simon Jakobi wrote: your package looks very similar to http://hackage.haskell.org/package/witherable!

Witherable has Traversable superclass, but some Filtrable types may not be Traversable. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

Oleg Grenrus

2:47 p.m.

New subject: Instance deps (was: [announcement] filtrable: class of filtrable containers)

There are discussions once in a while: https://www.reddit.com/r/haskell/comments/2rajq1/is_there_anything_planned_t... https://www.reddit.com/r/haskell/comments/2rajq1/is_there_anything_planned_t... https://www.reddit.com/r/haskell/comments/1id0p7/backpack_retrofitting_haske... https://www.reddit.com/r/haskell/comments/1id0p7/backpack_retrofitting_haske... I’m not sure what’s the story with backpack, way or another it would need to solve instance problem. - Oleg

...

On 17 Feb 2016, at 20:34, amindfv@gmail.com wrote:

...
El 17 feb 2016, a las 12:16, M Farkas-Dyck escribió:

...
On 17/02/2016, Joachim Breitner wrote: You might want to add laws in the style of

If this is also a Foldable, then toList . mapMaybe f = mapMapybe f . toList toList . catMaybes = catMaybes . toList toList . filter f = filter f . toList

Shall do.

...
Do you plan to add instances for all the other data structures in base that are filtrable?

Yes, if i missed any, please let me know which ☺

...
On 17/02/2016, Oleg Grenrus wrote: - I’d also like to see instances for types in containers, unordered-containers, vector and semigroup.

I was hoping to have no deps but base... alas, Cabal and Hackage seem to have no good way to have instance deps, so the instances must be in either the package defining the class or the one defining the types which are instances of it.

Are there any existing proposals for a solution to this?

Tom

...
...
If you don’t mind I can make a PR for the instances.

Feel free to do so for containers and vector at least. I may want this to not transitively depend on unordered-containers → hashable → text, but if enough potential users want these instances i'll include them (containers and vector come with GHC so it's not so bad). What types in semigroups would you add instances of?

...
- The OtherLicense seems a bit scary (even the contents aren’t), is there a good reason why you don’t use more familiar MIT or BSD3?

Too verbose. I might use ISC if it weren't also an OtherLicense...

...
The law:

filter f = mapMaybe (liftA2 (<$) id (guard ∘ f))

is very hard to understand.

Rewritten.

...
On 17/02/2016, Simon Jakobi wrote: your package looks very similar to http://hackage.haskell.org/package/witherable!

Witherable has Traversable superclass, but some Filtrable types may not be Traversable. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

M Farkas-Dyck

9:38 p.m.

New subject: Instance deps (was: [announcement] filtrable: class of filtrable containers)

2 options readily come to mind: • For each pair of packages (P, Q) where either has potential instances of a class in the other, we define these as orphans in yet another package R and tell this somehow in the cabal files of P and Q. If any package transitively depends on both P and Q it automatically sees the instance in R wherever all its types are in scope. Potential problem: quadratically many packages needed • We can mark some deps Qs in the cabal file of package P as only needed to define instances of their classes for our types or for their types for our classes. If a package which depends on P would not otherwise transitively depend on Q, these instances and dependencies are ignored.

David Menendez

12:26 p.m.

On Wed, Feb 17, 2016 at 2:02 AM, M Farkas-Dyck wrote:

...

I quietly posted this library to Hackage nearly a year ago, but lately learned that some seeking such a package had difficulty finding it, so i announce it now ☺

https://hackage.haskell.org/package/filtrable

class Functor f => Filtrable f where mapMaybe :: (a -> Maybe b) -> f a -> f b catMaybes :: f (Maybe a) -> f a filter :: (a -> Bool) -> f a -> f a

For laws, see docs on Hackage.

This is something I’ve made for myself once or twice (I called it “Siftable”). One law I didn’t notice you mention is: mapMaybe f . mapMaybe g = mapMaybe (f <=< g) In other words, mapMaybe is a functor from the Kleisli category over Maybe to Hask. (This may come free from parametricity and mapMaybe Just = id.) -- Dave Menendez http://www.eyrie.org/~zednenem/

M Farkas-Dyck

7:21 p.m.

On 17/02/2016, David Menendez wrote:

...

One law I didn’t notice you mention is:

mapMaybe f . mapMaybe g = mapMaybe (f <=< g)

Good call, added! If someone proves some law to be reducible to the others i'll delete it.

martin

9:57 p.m.

New subject: [announcement] filtrable: class of filtrable containers

The only need for the functor requirement is in the default definition of mapMaybe - so why not drop it? I would also suggest you add (modulo better names) partition :: (a -> Bool) -> f a -> (f a , f a) partitionWith :: (a -> Either b c) -> f a -> (f b, f c) catEithers :: f (Either b c) -> (f b, f c) lefts :: f (Either b c) -> f b rights :: f (Either b c) -> f c I think the class would still be equivalent to your current one, but more useful. On 2016-02-17 08:02, M Farkas-Dyck wrote:

...

I quietly posted this library to Hackage nearly a year ago, but lately learned that some seeking such a package had difficulty finding it, so i announce it now ☺

https://hackage.haskell.org/package/filtrable

class Functor f => Filtrable f where mapMaybe :: (a -> Maybe b) -> f a -> f b catMaybes :: f (Maybe a) -> f a filter :: (a -> Bool) -> f a -> f a

For laws, see docs on Hackage. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

Chris Wong

18 Feb 18 Feb

1:03 a.m.

On Thu, Feb 18, 2016 at 1:57 PM, martin wrote:

...

The only need for the functor requirement is in the default definition of mapMaybe - so why not drop it?

Since fmap can be defined in terms of mapMaybe: fmap f = mapMaybe (Just . f) Filtrable should imply Functor in the same way that Traversable implies Foldable. -- Chris Wong (https://lambda.xyz) "I had not the vaguest idea what this meant and when I could not remember the words, my tutor threw the book at my head, which did not stimulate my intellect in any way." -- Bertrand Russell

M Farkas-Dyck

2:01 a.m.

On 17/02/2016, Chris Wong wrote:

...

On Thu, Feb 18, 2016 at 1:57 PM, martin wrote:

...
The only need for the functor requirement is in the default definition of mapMaybe - so why not drop it?

Since fmap can be defined in terms of mapMaybe:

fmap f = mapMaybe (Just . f)

Filtrable should imply Functor in the same way that Traversable implies Foldable.

I think the notion is to make mapMaybe not a class method, and rather define it on its own: mapMaybe f :: (Functor f, Filtrable f) => (a -> Maybe b) -> f a -> f b mapMaybe f = catMaybes . fmap f I like this idea, but worry what the laws would be...

3380

Age (days ago)

3381

Last active (days ago)

List overview

Download

19 comments

12 participants

participants (12)

amindfv＠gmail.com
Bryan Richter
Chris Wong
Christopher Allen
David Menendez
Joachim Breitner
Kosyrev Serge
M Farkas-Dyck
martin
Oleg Grenrus
Sean Leather
Sebastian Dröge