'intersection' combinator

[mitchellwrosen]

trafficstars

I've occasionally found this combinator useful:

-- | Only emit event occurrences coincident with the second event.
coincident :: Event a -> Event b -> Event a
coincident e1 e2 = 
  filterRight                  -- (3) Filter down to only coincident events
    (unionWith
      (\(Left x) _ -> Right x) -- (2) Re-tag coincident Lefts as Rights
      (Left <$> e1)            -- (1) Left means "not coincident"
      (unsafeCoerce e2))
 where
  filterRight e = filterJust (either (const Nothing) Just <$> e)

I wonder if anyone else has, too?

[nickkuk]

What about such simplification?

coincident :: Event a -> Event b -> Event a
coincident e1 e2 = filterJust (unionWith const (Nothing <$ e2) (Just <$> e1))

[mitchellwrosen]

That's the XOR of mine :)

[nickkuk]

Ah, sorry, I misunderstood :smile:

[nickkuk]

One could suggest more general function

intersectionWith :: (a -> b -> c) -> Event a -> Event b -> Event c

[mitchellwrosen]

Yup, and the implementation is just a variation of unionWithP:

intersectionWithP :: (a -> b -> c) -> Pulse a -> Pulse b -> Build (Pulse c)
intersectionWithP f px py = do
    p <- newPulse "intersectionWithP" $ eval <$> readPulseP px <*> readPulseP py
    p `dependOn` px
    p `dependOn` py
    return p
  where
    eval (Just x) (Just y) = Just (f x y)
    eval _ _ = Nothing

though the name is kind of long... I wish unionWith was called union instead!

[nickkuk]

I think these names are good, because they correspond to similar functions from e.g. Data.IntMap.

[mitchellwrosen]

Well there used to be a union function before version 1.0, so the name unionWith made more sense. Now that union no longer exists, I'd prefer to simply rename unionWith to save 4 characters... but that's just a personal preference, and anyways, beside the point of this ticket :)

[nickkuk]

@mitchellwrosen I see, that you added PR about intersectionWith. What do you think about even more general function mergeWithKey? In the case of reactive-banana its type will look like

mergeWith :: (a -> b -> Maybe c) -> (Event a -> Event c) -> (Event b -> Event c) -> Event a -> Event b -> Event c

[mitchellwrosen]

I think its reactive-banana type would actually be this:

mergeWith 
  :: (a -> b -> Maybe c) 
  -> (a -> Maybe c) 
  -> (b -> Maybe c) 
  -> Event a 
  -> Event b 
  -> Event c

Looks very general, I'm not sure how useful it would be in practice. Still, unionWith and intersectionWith could both be implemented in terms of it:

unionWith :: (a -> a -> a) -> Event a -> Event a -> Event a
unionWith f e1 e2 = mergeWith (\x y -> Just (f x y)) Just Just

intersectionWith :: (a -> b -> c) -> Event a -> Event b -> Event c
intersectionWith f e1 e2 = mergeWith (\x y -> Just (f x y)) (const Nothing) (const Nothing)

Hmm :thinking:

[nickkuk]

Aha! I start to write the message that "two inner -> Event c are superfluous" :smile:

[nickkuk]

Also my broken coincident (that is acutally difference and can be generalized to differenceWith) can be implemented in terms of mergeWith.

[nickkuk]

@mitchellwrosen, let me point out the situation when one needs mergeWithKey and when intersectionWith, unionWith, differenceWith are not enough.

If you want to work with sparse vectors over the field of rational numbers, you can just filter it by non zero elements and store in IntMap Rational. So newtype Vector = Vector (IntMap Rational). But to implement addition or subtraction of such vectors it is convenient and more performant to use mergeWithKey, because you get unionWith + filtering of non zeros in one function. In terms of your function mergeWith it will look like

add = mergeWith (\a b -> filterNonZero (a + b)) Just Just
sub = mergeWith (\a b -> filterNonZero (a - b)) Just (Just . negate)
filterNonZero a = if a == 0 then Nothing else Just a

I believe that it is not hard to find use cases for mergeWith in reactive programming.

[ocharles]

@mitchellwrosen Now that we have merge, I believe we have

coincident :: Event a -> Event b -> Event a
coincident e1 e2 = filterJust $ merge e1 e2 <&> \case
  These a _ -> Just a
  _         -> Nothing

Do you still think we should add this to R.B.Combinators?

[mitchellwrosen]

Hmm... I'm not sure :)

On one hand, I do find I need this combinator, or something like it, a lot.

But on the other hand, I don't like how the order of arguments isn't clear to a reader.

[HeinrichApfelmus]

But on the other hand, I don't like how the order of arguments isn't clear to a reader.

How about using an adjective, e.g. a present participle?

intersecting :: Event a -> Event b -> Event a

… (ea `intersecting` eb) …