Closed Raynos closed 6 years ago
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]
Indeed, Haskell's mfilter
requires a MonadPlus, which is a Monad with monoidal properties. In fact, the source implements exactly what I wrote above!
@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.
@pufuwozu: I think you caught me in between two edits. I originally had map().flatten()
, then I changed it to chain()
in two steps.
@Twisol must have been it. Looks great :smile:
@Twisol @pufuwozu I don't want monad semantics. i.e. I can't implement flatten()
. Is there another way to implement filter()
?
@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.
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.
@Raynos: Yes, it definitely sounds like you want something based on Foldable
.
@Raynos why make Stream<Stream>
invalid? That seems to break parametricity for no reason.
Oh, I understand the use case. FRP should disallow joining of streams. Fair enough.
@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>
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 Functor
s 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); }
Also, catMaybes
comes for free:
function () { this.mapMaybe(x => x); }
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
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.
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]
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)
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?
Why are neither of those examples valid?
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()
}
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.
Why can't Maybe a
be a Semigroup
?
Why can't
Maybe a
be aSemigroup
?
Maybe a
can be a Semigroup
only when a
is Semigroup
.
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,
});
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
@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.
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.
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 Monoid
s and Alternative
s 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.
Because we'd like
S.filterM(S.odd, S.Just(0))
to evaluate toNothing
, 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;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:
filterMaybe :: (a -> Boolean) -> Maybe a -> Maybe a
;sanctuary/filter
method or some other non-FL method; orMonoid (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 aMonoid
, anAlternative
, 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. :)
.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?