Interest in adding `Align`?

[joneshf]

How would we feel about adding a class in the spirit of Align? I think we probably want a bit more granularity (akin to Apply and Divide). What about something that parallels the Apply/Applicative and Divide/Divisible classes:

class (Functor f) <= Align f where
  align :: forall a b c. (These a b -> c) -> f a -> f b -> f c

With the laws:

• Naturality

  align f (map g x) (map h y) = align (f <<< bimap g h) x y

• Associativity

  associate :: These a (These b c) -> These (These a b) c
  associate = case _ of
    This x -> This (This x)
    That (This x) -> This (That x)
    That (That x) -> That x
    That (Both x y) -> Both (That x) y
  
  map associate (align identity x (align identity y z))
    = align identity (align identity x y) z

  Or, simpler

  aligned :: forall a b f. Align f => f a -> f b -> f (These a b)
  aligned = align identity
  
  map associate (aligned x (aligned y z)) = aligned (aligned x y) z

class (Align f) <= Alignable f where
  nil :: forall a. f a

With the laws

• Right identity

  align f x nil = map (f <<< This) x

• Left identity

  align f nil x = map (f <<< That) x

From Alignable, we can derive map as:

map f x = align (f <<< these identity identity const) x nil

---

The ultimate motivation for this is to define something similar to Crosswalk, so we can do things like:

parities :: Map Parity (List Int)
parities = crosswalk parity (range 1 10)

parity :: Int -> Map Parity Int
parity x
  | x `mod` 2 == 0 = singleton Even x
  | otherwise = singleton Odd x

data Parity
  = Even
  | Odd

derive instance eqParity :: Eq Parity
derive instance ordParity :: Ord Parity

But, I wanted to see if there was interest in Align first, before going further. Also, Crosswalk is such an out-there name. Maybe we can bike shed it before committing to Align/Alignable.

What do we think?

[joneshf]

In case it was unclear, the takeaway of that example is that we can write a program we otherwise couldn't before.

We can't traverse with a -> Map b c as there's no law-abiding Applicative instance for Map a. We could traverse1, but that changes the problem to requiring a non-empty list (and that's not always possible). We could change parity to Int -> Map Parity (List Int), and use foldMap parity (range 1 10); but, that adds more complexity to parity for the sake using Foldable.

Since we can write a law-abiding Alignable instance for Map a, we can crosswalk over a List Int and get the thing we want.

[garyb]

Yeah definitely, this sounds sounds great 👍

[joneshf]

Cool!

So, what about the names? If there were different names for Align and Alignable–say Foo and Bar for the sake of the idea–we could have a hierarchy like:

class (Functor f) <= Foo f where
  foo :: forall a b c. (These a b -> c) -> f a -> f b -> f c

class (Foo f) <= Bar f where
  bar :: forall a. f a

class (Foldable f, Functor f) <= Alignable f where
  align :: Bar t => (a -> t b) -> f a -> t (f b)

The motivation there is that there's a parallel between Alignable and Traversable. The difference is in which bifunctor the underlying effect type class is using: These and Tuple, respectively. Is having both classes end with-able helpful? If so, what could we name Foo and Bar?

[eviefp]

Since I have an open PR fixing this, should this be assigned to me?