Add part(ition) and part(ition)ing to Filterable

[Jashweii]

Addressing #21

class Functor f => Filterable f where
  ...
  part :: f (Either a b) -> (f a, f b)
  part = parting id

  parting :: (c -> Either a b) -> f c -> (f a, f b)
  parting f fc = (mapMaybe (isLeft . f) fc, mapMaybe (isRight . f) fc)
  -- default implementation in terms of mapMaybe where (definitions omitted)
  -- isLeft  :: Either a b -> Maybe a
  -- isRight :: Either a b -> Maybe b

The default implementation uses mapMaybe twice (mapMaybe and parting can both be expressed in terms of the other). By adding it as a method, lists, maps and other instances can avoid making two traversals.
Likewise indexed and applicative/traversal variants could be added.

[spacekitteh]

You should make this a PR :)

[kindaro]

I'd sure like this!

[alexfmpe]

This can have surprising behavior with Compose instances

witherable/witherable/src/Witherable.hs

Lines 306 to 309 in 187ca07

	instance (Functor f, Filterable g) => Filterable (Compose f g) where
	mapMaybe f = Compose . fmap (mapMaybe f) . getCompose
	filter p = Compose . fmap (filter p) . getCompose
	catMaybes = Compose . fmap catMaybes . getCompose

parting :: (a -> Bool) -> Compose IO [] a -> (Compose IO [] a, Compose IO [] a)

Now we're launching twice the missiles

[Jashweii]

This can have surprising behavior with Compose instances

witherable/witherable/src/Witherable.hs

Lines 306 to 309 in 187ca07

	instance (Functor f, Filterable g) => Filterable (Compose f g) where
	mapMaybe f = Compose . fmap (mapMaybe f) . getCompose
	filter p = Compose . fmap (filter p) . getCompose
	catMaybes = Compose . fmap catMaybes . getCompose

parting :: (a -> Bool) -> Compose IO [] a -> (Compose IO [] a, Compose IO [] a)

Now we're launching twice the missiles

When you look at it without the newtype it isn't really surprising
(a -> Bool) -> IO [a] -> (IO [a], IO [a])
There's no way it can avoid duplicating the effects in the two results (in an instance this general). It is functionally the same as using filter twice. I don't think it's really worth either de-generalising Compose's instance or putting partition in a subclass for this, if you have some effects you want done once you can use fmap . parting

parting :: Filterable g => (a -> Either b c) -> 
   g a -> (g b, g c)
-- ^       ^    ^
-- duplicated, including f in g = Compose f g'
fmap . parting :: (Functor f, Filterable g) => (a -> Either b c) -> 
   f (g a) -> f (g b, g c)
-- ^          ^  
-- not duplicated for outer f

Of course this requires unwrapping Compose, and can't be rewrapped without another Compose V2 in the middle (where V2 a = a x a) indicating the duplicated component
FWIW with GHC 9 it may be worth considering a linear version (but this prevents using mapMaybe as a default implementation). Not sure if some data structures may have issues with duplicating book-keeping. I suppose this could go in linear base instead.

parting :: Filterable f => (a -> Either b c) -> f a %1 -> (f b, f c)

[hseg]

To clarify, are there any objections to adding this?
Perhaps with some documentation to the effect of "make sure you're catching the exact number of layers in your call to parting, as for some types it duplicates effects"?

[fumieval]

No objection from me

[hseg]

OK, finally found some time to work on this.
Just noticed that while this is practical for fusing a single partition,
anything more complex would still unnecessarily need multiple passes.
To solve that, we'd need something like

data Sum xs where
    SL :: x -> Sum [x]
    SR :: Sum xs -> Sum (a:xs)

absurdSum :: Sum [] -> a
absurdSum x = case x of {}

is :: Maybe a -> Bool
is (Just _) = True
is Nothing = False

sL :: Sum (x:xs) -> Maybe x
sL (SL x) = Just x
sL (SR _) = Nothing

sR :: Sum (x:xs) -> Maybe (Sum xs)
sR (SR x_) = Just x
sR (SL _) = Nothing

data Prod xs where
    O :: Prod []
    C :: x -> Prod xs -> Prod (x:xs)

class Filterable f => Part f xs where
    part :: f (Sum (xs :: [Type])) -> (Prod (xs :: [Type]))

instance Filterable f => Part f [] where
    part = fmap absurdSum

instance (Filterable f, Part f xs) => Part f (x:xs) where
    part xs = filter (is.sL) xs `C` part (mapMaybe sR xs)

Of course, this is starting to verge on scope creep. Especially considering Data.List suffices itself with partitioning on predicates.

[phadej]

That i.e. reinventing sop-core is definitely out of scope. Also N-ary product is a linked-list, not a random-access tuple, so for say N-bins it won't be good.

That's why I don't think parting belongs to Filterable.

Another argument is why not adding also

partingThese :: (a -> These b c) -> f a -> (f b, f c) ? That's another way to distribute elements.
And the most general version is partingTwoMaybes :: (a -> (Maybe b, Maybe c) :: f a -> (f b, f c) i.e. doing two mapMaybes in one go.

I don't see a good guideline why something should be in Filterable and something doesn't.
Maybe partingTwoMaybes, but with some clearly better name. These and Either variants are specializations of it.

[hseg]

Perhaps exposing something like the composable folds of foldl?

[phadej]

Also: the GADT Prod won't even work, as we need lazy match (see https://hackage.haskell.org/package/base-4.16.0.0/docs/src/Data.Either.html#partitionEithers for an example) to have benefits of single pass, but the Prod cannot be lazily matched on. With data family it would work, but it's trickier to use: we would need a list singleton.

Perhaps exposing something like the composable folds of foldl?

How? Could you sketch?

[Jashweii]

That i.e. reinventing sop-core is definitely out of scope. Also N-ary product is a linked-list, not a random-access tuple, so for say N-bins it won't be good.

That's why I don't think parting belongs to Filterable.

Another argument is why not adding also

partingThese :: (a -> These b c) -> f a -> (f b, f c) ? That's another way to distribute elements. And the most general version is partingTwoMaybes :: (a -> (Maybe b, Maybe c) :: f a -> (f b, f c) i.e. doing two mapMaybes in one go.

I don't see a good guideline why something should be in Filterable and something doesn't. Maybe partingTwoMaybes, but with some clearly better name. These and Either variants are specializations of it.

I hadn't considered putting values into both functors, just divvying them up. It is pretty arbitrary seeing that maybe version, since you could have _ -> (Maybe a, Maybe b, ..., Maybe z), and it really is just a bunch of mapMaybes.
I wonder if you could do it generally with something like distributive or representable.
Edit: rank 2 distributive

class Functor f => Filterable f where 
  mapMaybe :: (a -> Maybe b) -> f a -> f b
-- rank 2 distributive, from rank2classes
class Distributive t where
  cotraverse :: Functor m => (forall a. m (p a) -> f a) -> m (t p) -> t f

mapMaybes :: (Filterable f, Distributive t) => (a -> t Maybe) -> f a -> t f
mapMaybes f = cotraverse (mapMaybe id) . fmap f

-- example, mapMaybe to int char and a
data CustomTuple a f = CustomTuple { int :: f Int, char :: f Char, a :: f a }
instance Distributive (CustomTuple a) where
  cotraverse h b = CustomTuple (h (fmap int b)) (h (fmap char b)) (h (fmap a b))

[hseg]

How? Could you sketch?

The idea was half-formed and doesn't quite hold up on further inspection. Basically thought we might be able to reify the maps arising from the particular mapMaybes, combine them, then run them in one pass.

Trying to find a different way to type what I'm suggesting here, you'd want distMaybe :: f (r Maybe) -> r f where r :: (Type -> Type) -> Type is some HKD type.
EDIT: sniped

so going by @Jashweii's implementation, we'd have

genCatMaybes :: (Filterable f, Distributive t) => f (t Maybe) -> t f
genCatMaybes = cotraverse catMaybes

[Jashweii]

Trying to find a different way to type what I'm suggesting here, you'd want distMaybe :: f (r Maybe) -> r f where r :: (Type -> Type) -> Type is some HKD type. EDIT: sniped

Odds of that were pretty low! I dunno if there's an efficient way of doing this generally except maybe with representable. If it's not any more efficient it may as well be a free function assuming it's useful enough.

[phadej]

@Jashweii I see, with hkd we can do https://hackage.haskell.org/package/hkd-0.1/docs/Data-HKD.html

{-# LANGUAGE DeriveGeneric #-}
{-# OPTIONS_GHC -Wall #-}
module Partition where

import GHC.Generics (Generic)

-- from hkd
-- https://hackage.haskell.org/package/hkd-0.1/docs/Data-HKD.html
import Data.HKD

class Partition f where
    partition :: FRepeat r => (a -> r Maybe) -> f a -> r f

instance Partition [] where
    partition _ []     = frepeat []
    partition f (x:xs) = fzipWith maybeCons (f x) (partition f xs) 
      where
        maybeCons Nothing  ys = ys
        maybeCons (Just y) ys = y : ys

-- an example

data HTriple a b c f = HTriple (f a) (f b) (f c)
  deriving (Show, Generic)

instance FFunctor (HTriple a b c) where ffmap _ _ = error "not needed"
instance FZip     (HTriple a b c) where fzipWith  = gfzipWith
instance FRepeat  (HTriple a b c) where frepeat   = gfrepeat

justIf :: (a -> Bool) -> a -> Maybe a
justIf f x = if f x then Just x else Nothing

-- HTriple [1,3,5,7,9] [2,4,6,8,10] ["1","2","3","4","5","6","7","8","9","10"]
ex :: HTriple Int Int String []
ex = partition (\x -> HTriple (justIf odd x) (justIf even x) (Just (show x))) [1..10 :: Int]

and this should be good if fzipWith isn't strict. (Re partitionEither)

And hkd is light package. But I don't know what are @ekmett's plans with it (and distributive) are at the moment, so I'm hesitant to depend on it.

EDIT: its next version is something like in https://github.com/ekmett/hkd/blob/main/hkd.cabal, so my opinion is that Partition class should go there. It's much "heavier" package than current witherable.

[hseg]

Makes sense for me.
(BTW, it feels like this Partition is near the FFilterable point of that design space)
Looking into possible homes for this...

[phadej]

FFilterable would filter fields of a "record". E.g. data Maybe1 a f = Just1 (f a) | Nothing1

[hseg]

Ah right. It's getting late here, my mistake.
In any case, the original issue (distributing Either) looks small and useful enough to supply here,
will be writing the patch (including avoiding multiple passes) for it tomorrow.

[phadej]

@hseg, I'd call parting partition (as that's the type partition in Data.List should really have). And not have part at all, or at least not in the class. it would make sense to have in class if partition's default implementation were defined using it, but it won't, so part will always (!?) be using the default implementation.