Fantasy-land: Filterable algebra?

[Raynos]

.map and .chain are cool for writing higher order functions over things.

Another primitive I use a lot is .filter and I don't know how to implement in terms of .map / .ap / .chain.

Is there an algebra for it?

[Twisol]

I'm pretty sure your Monad needs to be a Monoid for this to work - i.e. it needs to have an empty.

filter = function(predicate) {
  return this.chain(function(x) {
    if (predicate(x)) {
      return this.constructor.of(x);
    } else {
      return this.constructor.empty();
    }
  });
};

[1, 2, 3].filter(function(x) {
  return x < 3;
});
// => [1, 2]

[Twisol]

Indeed, Haskell's mfilter requires a MonadPlus, which is a Monad with monoidal properties. In fact, the source implements exactly what I wrote above!

[puffnfresh]

@Twisol yeah, that sounds right. It's known as MonadPlus in Haskell - we should specify the MonadPlus laws for things that are both Monad and Monoid. I think the flatten in your example is an error.

[Twisol]

@pufuwozu: I think you caught me in between two edits. I originally had map().flatten(), then I changed it to chain() in two steps.

[puffnfresh]

@Twisol must have been it. Looks great :smile:

[Raynos]

@Twisol @pufuwozu I don't want monad semantics. i.e. I can't implement flatten(). Is there another way to implement filter() ?

[Twisol]

@Raynos: Nope. Mapping allows you to convert one value to another, but crucially it does not allow you to add more or remove any of those values. That's something you can only do at the monadic level.

What are you trying to implement filter on? Maybe we can figure something out if we know the specifics.

[Raynos]

An infinite stream. I just want to make Stream<Stream> invalid but still implement stream.filter()

filter() is obviously trivial to implement in terms of Foldable so maybe I should just do that.

[Twisol]

@Raynos: Yes, it definitely sounds like you want something based on Foldable.

[puffnfresh]

@Raynos why make Stream<Stream> invalid? That seems to break parametricity for no reason.

[puffnfresh]

Oh, I understand the use case. FRP should disallow joining of streams. Fair enough.

[Raynos]

@pufuwozu because that's an infinite thing of infinite things. Once i've specced out how to garbage collection an infinite amount of infinite things then I'll allow Stream<Stream>

[joneshf]

We could take a cue from witherable and provide mapMaybe as the method without pulling in all of witherable. filter is easily derived from it. Though it would add a specific dependency on an implementation of Maybe a existing somewhere.

There should be at least one law (maybe more?):

u.mapMaybe(Just) == u

And you should be able to derive Functors map from it:

function (f) { return this.mapMaybe(x => Just(f(x))); }

And of course filter is:

function (p) { return this.mapMaybe(x => p(x) ? Just(x) : Nothing); }

[joneshf]

Also, catMaybes comes for free:

function () { this.mapMaybe(x => x); }

[joneshf]

Oh look, prior art:

• https://github.com/fumieval/witherable/issues/10
• https://github.com/reflex-frp/reflex/issues/19
• https://github.com/reflex-frp/reflex/pull/44

[puffnfresh]

A useful function:

unite :: (MonadPlus m, Foldable t) => m (t a) -> m a
unite f = (>>= (getAlter . foldMap (Alter . pure)))

A generalised version of mapMaybe might use the above and look something like:

(MonadPlus m, Foldable t) => (a -> t b) -> m a -> m b

[joneshf]

unite = generalized catMaybes?

Seems like the MonadPlus constraint limits what can implement it though. We'd lose Map a b, ZipList a, and Validation a b to name a few.

I like the idea of a Foldable constraint though.

[puffnfresh]

You can change the constraint a bit to get:

collapse :: (Alternative m, Foldable t) => t a -> m a
collapse = foldr ((<|>) . pure) empty

Given that Foldable composes, you can then recover catMaybes:

let catMaybes :: [Maybe a] -> [a]
    catMaybes = collapse . Compose
in catMaybes [Just 1, Nothing, Just 2] == [1, 2]

[safareli]

you can also do like this

filter :: (Applicative f, Foldable f, Monoid (f a)) => (a -> Bool) -> f a -> f a
filter p = foldMap (\a -> if p a then pure a else mempty)

[davidchambers]

Sanctuary currently provides S.filter and S.filterM (which wrap Z.filter and Z.filterM respectively).

As a result of sanctuary-js/sanctuary#359 it's now apparent that neither filter(odd, Just(4)) nor filterM(odd, Just(4)) is valid due to the Monoid (m a) constraints. To filter values of type Maybe a we need mfilter, which requires MonadPlus.

Is adding MonadPlus to the specification a good idea, do you think?

[joneshf]

Why are neither of those examples valid?

[safareli]

you can do it with (Alternative m, Monad m) => m constraint:

// :: (Alternative m, Monad m) => (a -> Boolean, m a) -> m a
const mfilter = (p,ma) => {
  const T = ma.constructor
  return ma.chain(a => p(a) ? T.of(a) : T.zero()
}

[davidchambers]

Why are neither of those examples valid?

From the Monoid spec:

A value that implements the Monoid specification must also implement the Semigroup specification.

Just(4) cannot satisfy Semigroup, so by extension cannot satisfy Monoid.

As @safareli pointed out, though, Just(4) can satisfy Alternative! The solution, therefore, is to replace the Monoid (m a) constraint with an Alternative m constraint. I've opened sanctuary-js/sanctuary-type-classes#37 to do exactly this.

[joneshf]

Why can't Maybe a be a Semigroup?

[safareli]

Why can't Maybe a be a Semigroup?

Maybe a can be a Semigroup only when a is Semigroup.

[joneshf]

1. Why is that a problem?

2. Can't you also do:

   const Nothing = {
     concat: x => x,
   };
   const Just = x => ({
     concat: _ => x,
   });
   

   or

   const Nothing = {
     concat: x => x,
     isJust: false,
   };
   const Just = x => ({
     concat: y => y.isJust ? y : x,
     isJust: true,
   });
   

[safareli]

Technically you can you can make any Alternative a Monoid:

T.empty = T.zero
T.prototype.concat = T.prototype.alt

The definition of concat you provided is more alt then concat.

Ideally we should be able to make Maybe a, Monoid when a is Monoid

const MaybeOf = M => {
  const TypeRep = {
    empty: M.empty,
  }

  const Just = value => {
    value,
    tag: 'Just',
    concat: b => Just(b.tag == 'Just' ? value.concat(b.value) : value)
    constructor: TypeRep,
  }

  const Nothing = {
    value,
    tag: 'Nothing',
    concat: b => b,
    constructor: TypeRep,
  }

  TypeRep.of = Just
  TypeRep.Just = Just
  TypeRep.Nothing = Nothing

  return TypeRep
}

But it becomes problematic when you start defining map

[xaviervia]

@safareli could this be two different Maybe variations? I see the point of @joneshf of making Maybe a Semigroup.

The Maybe a that is a Monoid when a is a Monoid sounds like one of many possible interpretations of Maybe.concat. It would mean that Maybe is not a Monoid per se, and you cannot really make assumptions about it being a Monoid if you get a Maybe and don’t know which type it is parametrized with, which sounds odd to me. I haven’t seen many cases in which the parameter type changes the type class of the parametrized type.

[davidchambers]

Why is that a problem?

Because we'd like S.filterM(S.odd, S.Just(0)) to evaluate to Nothing, but it's a type error:

S.filterM(S.odd, S.Just(0));
// ! TypeError: Type-class constraint violation
//
//   filterM :: (Monad m, Monoid m) => (a -> Boolean) -> m a -> m a
//                        ^^^^^^^^                       ^^^
//                                                        1
//
//   1)  Just(0) :: Maybe Number, Maybe FiniteNumber, Maybe Integer, Maybe ValidNumber
//
//   ‘filterM’ requires ‘m’ to satisfy the Monoid type-class constraint; the value at position 1 does not.

As for your second point, @joneshf, you're quite right to point out that this claim is false:

Just(4) cannot satisfy Semigroup, so by extension cannot satisfy Monoid.

It should read does not rather than cannot.

The question is then whether we should adopt your version of Maybe#fantasy-land/concat. Letting our desire to filter values of type Maybe a dictate the concat semantics seems like the tail wagging the dog. Why go to such lengths to satisfy Monoid when we could satisfy Alternative instead?

The concat and alt semantics of Sanctuary's Maybe type match those of Haskell's Maybe type:

> Just "abc" <> Just "def"
Just "abcdef"

> Just "abc" <|> Just "def"
Just "abc"

> mfilter odd (Just 0)
Nothing

I haven’t seen many cases in which the parameter type changes the type class of the parametrized type.

Try evaluating this in ghci, @xaviervia:

> Just 123 <> Just 456

Again, @safareli and I are referencing the Haskell behaviour. The Haskell definition of (<>) for Maybe a is not the only valid definition, but it is certainly useful in some contexts.

[joneshf]

Because we'd like S.filterM(S.odd, S.Just(0)) to evaluate to Nothing, but it's a type error:

That works on the docs here: https://sanctuary.js.org/#filterM I'm still confused what the problem is. If you can only make Maybe a a Monoid only if a is also a Monoid, then you should rightly get an error when you pass a Maybe a where a is not a Monoid.

Letting our desire to filter values of type Maybe a dictate the concat semantics seems like the tail wagging the dog. Why go to such lengths to satisfy Monoid when we could satisfy Alternative instead?

Chasing Monoids and Alternatives in order to get an approximation of filter is equally tail-wagging. Why not just define filter and be done with it? We can add the algebra to the spec with laws so there isn't a need to debate whether something should be a Monoid, an Alternative, or whatever else. filter is a worthwhile enough function with enough behavior that it should get its own algebra instead of being derived from other algebras. Not to mention that if we push on filter a bit we get things like partition, filterMap, wither, etc.

[davidchambers]

Because we'd like S.filterM(S.odd, S.Just(0)) to evaluate to Nothing, but it's a type error:

That works on the docs here: https://sanctuary.js.org/#filterM I'm still confused what the problem is.

It currently works because Sanctuary's Maybe type defines fantasy-land/concat unconditionally. This is not correct, though, and leads to invalid code "working" in some cases and throwing errors with unhelpful descriptions in other cases:

S.concat(S.Just(0), S.Nothing);
// => Just(0)

S.concat(S.Just(0), S.Just(0));
// ! Semigroup.methods.concat(...) is not a function

The fix for this is to define fantasy-land/concat for a Just only if the Just's value satisfies Z.Semigroup.test (sanctuary-js/sanctuary#359). There are several consequences of this change:

• S.Just(0) no longer satisfies Semigroup;
• as a result it no longer satisfies Monoid; and
• as a result it can no longer be used with S.filter and S.filterM.

In order to continue to support filtering values of type Maybe a without changing the Maybe type's concat semantics (which match those of Haskell's Maybe type), we could:

• provide a separate function such as filterMaybe :: (a -> Boolean) -> Maybe a -> Maybe a;
• dispatch to a sanctuary/filter method or some other non-FL method; or
• replace the Monoid (m a) constraint of S.filterM with an Alternative m constraint.

I favour the last option.

Why not just define filter and be done with it? We can add the algebra to the spec with laws so there isn't a need to debate whether something should be a Monoid, an Alternative, or whatever else.

Sounds great to me! If and when Fantasy Land specifies Filterable we will replace S.filter and S.filterM with a single S.filter :: Filterable f => (a -> Boolean) -> f a -> f a. Until that point, though, we can make do with type classes already specified. :)