Add the Align, Alignable and Crosswalk classes

[eviefp]

Description of the change

Looking for early feedback.

I tried to implement the classes described in #21 to the best of my knowledge, using the Haskell implementation as an example.

I am looking for early feedback on

• naming,
• instances required (e.g. we could include ordered-collections for Map instance for example),
• and the validity of the lazy list instance.

Feel free to ask me to add more documentation or tests before providing any feedback (although I would rather wait on those until I get a :+1: ).

Fixes #21

---

Checklist:

• [x] Added the change to the changelog's "Unreleased" section with a link to this PR and your username
• [x] Linked any existing issues or proposals that this pull request should close
• [ ] Updated or added relevant documentation in the README and/or documentation directory
• [x] Added a test for the contribution (if applicable)

[thomashoneyman]

I'm not familiar with these type classes myself. However, I do see laws from Haskell, which would be useful to be added to the class documentation comments (as is done for other classes in PureScript, like Semigroup, Monoid, Alternative, etc.). It would also be useful to add some tests that:

• show how these typeclasses are useful / how to use them and
• ensure that the LazyList instance works (it can be difficult to verify laziness by inspection, so it's useful to test to make sure lazy things are really lazy)

The new dependencies are not a problem :)

[thomashoneyman]

Oh -- and wrt instances, I do think it makes sense to add an instance for Map as that was the original motivating example in the linked issue. Perhaps @garyb and @joneshf have other ideas as well.

[joneshf]

As a quick response, you can think of Data.Align.Align _, Data.Align.Alignable _, and Data.Align.Crosswalk _ filling a similar role as Control.Apply.Apply _, Control.Applicative.Applicative _, and Data.Traversable.Traversable _, respectively. The difference is in how values are combined.

For example, given:

even ::
  Int ->
  Data.Maybe.Maybe Int
even x =
  if mod x 2 == 0 then
    Data.Maybe.Just x
  else
    Data.Maybe.Nothing

Where Data.Traversable.Traversable _ "fails early," Data.Align.Crosswalk _ "fails late":

• When everything "succeeds," they behave the same:

  > Data.Traversable.traverse even [2,4]
  (Just [2,4])
  
  > Data.Align.crosswalk even [2,4]
  (Just [2,4])

• When everything "fails," they behave the same:

  > Data.Traversable.traverse even [1,3,5]
  Nothing
  
  > Data.Align.crosswalk even [1,3,5]
  Nothing

• When somethings "fail," Data.Traversable.traverse "fails" everything and Data.Align.crosswalk does not:

  > Data.Traversable.traverse even [1,2,3,4,5]
  Nothing
  
  > Data.Align.crosswalk even [1,2,3,4,5]
  (Just [2,4])

I.e. It takes everything "failing" to "fail" Data.Align.crosswalk. Or, Data.Align.crosswalk "fails late."

All of the caveats around the generality of Control.Apply.Apply _, Control.Applicative.Applicative _, and Data.Traversable.Traversable _ apply to Data.Align.Align _, Data.Align.Alignable _, and Data.Align.Crosswalk _, respectively. It's not just all about the one case of Data.Maybe.Maybe _, because some data types don't have a concept of "failure" like Data.Maybe.Maybe _.

[eviefp]

I added quickcheck laws and tests for the instance laws. Also added some module documentation and examples.

I did not add documentation to README.md/docs. I think I would rather tackle that in a subsequent PR, such that I also add some docs for These as well.

[eviefp]

Huge thanks to @joneshf , the initial issue was quite clear, and the examples you posted a couple of days ago were great!

[joneshf]

Thank you for putting this together!

[joneshf]

If people are up to it, I'd like to bikeshed the names–in particular Crosswalk. If they're not, I wont.

[thomashoneyman]

I don’t mind, and I don’t think there’s any particular urgency that would force the issue. What do you have in mind?

[eviefp]

I like Crosswalk only because it already exists in Haskell so people might find it familiar, although I could be convinced that there's very few people who know about/use it in Haskell anyway so I don't feel very strongly about it.

I like that it has walk in it, since it feels close to traverse, or at least in the same ballpark.

OTOH, this feels very close to being some sort of mix between Alternative and Traversable. For example, is there an example where nil is not the same thing as empty?

[joneshf]

I went down quite the rabbit-hole on this one. Ended up at this comment by @masaeedu and this Stack Overflow question. Haven't really gathered all my thoughts, but agree that there's something between Data.Traverable.Traverable _ and at least Control.Plus.Plus _ (dunno that it needs the full Control.Alternative.Alternative _).

The linked comment talk about how Data.Align.Align _ is always derivable from the interaction between Control.Alt.Alt _ and Control.Apply.Apply _. I.e. we don't actually need to define Data.Align.Align _ to get equivalent behavior. I think the thing we get by defining it is efficiency. I dunno if you can derive Data.Align.Align _ without "traversing" each data structure at least twice (maybe at least three times?). Also dunno if that's even worth worrying about.

In any case, it sparks the idea that if there were something like Data.Traversable.Traversable _ that worked with Control.Plus.Plus _ instead of Control.Applicative.Applicative _, we might be able to derive Data.Crosswalk.Crosswalk _ similarly. Didn't see anything explicitly about it, but it seems like a possibility.

[thomashoneyman]

@vladciobanu @joneshf I've added the merge before 0.14 label to indicate we'd like to get this change in before releasing the final 0.14-ready version of the library. Do y'all have additional thoughts on these classes?

[joneshf]

I don't really have a suggestion, and it doesn't look like there's much discussion going on, so don't hold anything up.