These, Align, and Crosswalk

Published: 2017-03-29
Words: 1322

My post about merging maps got me thinking about merging lists and sets. List.zip and List.zipWith lead to plenty of sneaky bugs, just like Map.union. Again, we could write our own function each time using primitive recursion, but it happens enough that it'd be handy to be able to do it inline without thinking too much.

This post will focus on the contents of Hackage's these, which is maintained by C McCann. I was struggling to understand some of the library's concepts, which are presented in a quite abstract setting, so I'll aim to keep it somewhat concrete, so it can be used as a crummy quick-start tutorial by future lazyfolk.

These

The namesake of the package, These , is quite similar to Either:

data These a b =
    This a
  | That b
  | These a b

Left a is This a, Right b is That b, and we get a new constructor for when we have both, These a b.

The Functor instance only lets us touch the b:

λ> import Data.These
λ> fmap not (This 'a')
This 'a'
λ> fmap not (That True)
That False
λ> fmap not (These 5 False)
These 5 True

The Bifunctor instance is a little more useful:

λ> bimap Char.ord not (These 'a' False)
These 97 True

The Monad and Applicative instances for These a b requires a Semigroup constraint on a. It does its best to retain every a until it encounters a This, when it has to stop for reasons similar to my accumulating errors post:

λ> (,,) <$> That 5 <*> These ["warning!"] 42 <*> This ["error!"]
This ["warning!", "error!"]
λ> (,,) <$> This ["error!"] <*> That 5 <*> These ["warning!"] 42
This ["error!"]

The Applicative instance could easily continue collecting every This, but that would make ap different to (<*>), likely offending lambda man or whoever.

For this reason, the docs describe it as "a hybrid error/writer monad, as would be expected." I suppose someone expected this, one of those mythical folk who think before they type! Not I, I had to ham around in GHCi and write about it.

These is a pretty useful type, somewhere between Either and Writer, encapsulating things I do all the time: making mistakes, contriving values, and ignoring mistakes while pontificating. If it were in base, I'd probably use it all the time. Nevertheless, it's not in my dependency tree yet. Before I can bring myself to introduce it to a project, I require a little more value from the package.

Behold, These sliced four ways, concisely solving moderately-practical problems:

Align

From the README:

The type class Align is here because f (These a b) is the natural result type of a generic "zip with padding" operation--i.e. a structural union rather than intersection.

Here we go: safe zipping.

The Align class requires us to implement two functions:

The Maybe instance is not all that interesting:

λ> align (Just 10) Nothing
Just (This 10)
λ> align (Just 10) (Just True)
Just (These 10 True)
λ> align Nothing (Just True)
Just (That True)

The instance for lists is pretty straightforward, and what we probably want most of the time:

λ> nil :: [Bool]
[]
λ> align [1..3] [1.0 .. 6]
[These 1 1.0,These 2 2.0,These 3 3.0,That 4.0,That 5.0,That 6.0]

... with Vector and Seq instances behaving pretty similarly.

The best bang for buck comes from the wonderfully-named malign (and its Semigroup cousin, salign), which handles the zipWith (<>) case (while handling remnants correctly on either side):

λ> :t malign
malign :: (Monoid a, Align f) => f a -> f a -> f a
λ> :t salign
salign :: (Data.Semigroup.Semigroup a, Align f) => f a -> f a -> f a
λ> malign ["foo", "bar", "baz"] ["quux"]
["fooquux","bar","baz"]

padZipWith is also quite handy, allowing us to get safe padded zipWith without even importing Data.These:

λ> :t padZipWith
padZipWith :: Align f => (Maybe a -> Maybe b -> c) -> f a -> f b -> f c
λ> padZipWith (\ a b -> (+) <$> a <*> fmap fromRational b) [1..5] [1.0 .. 3]
[Just 2.0,Just 4.0,Just 6.0,Nothing,Nothing]

... I suspect it is not particularly helpful when using the Maybe instance.

Aligning Set and Map

Unfortunately, there's no Align instance for Set or Map, because they demand an Ord constraint. There's an instance for IntMap and an instance for Seq, which suggests we could probably write them if not for the additonal constraints. We don't really need Align for Map, since we have Map.merge, but it would have been quite helpful for Set.

See Sculthorpe et al, The Constrainted-Monad Problem to tour the painful intersection of constraints and typeclasses.

Crosswalk

Crosswalk is to Align as Traversable is to Applicative. That's all there is to say on the matter.

This class motivated me to write this ridiculous post. I read that quote and still did not quite understand what Crosswalk was. Now I'm here to confuse you with some helldamned GHCi session dumps.

The List instance lets us align all the things at once, rather than two at a time:

λ> :t sequenceL
sequenceL :: (Crosswalk t, Align f) => t (f a) -> f (t a)
λ> sequenceL [[1..5], [6..10], [11..12]]
[[1,6,11],[2,7,12],[3,8],[4,9],[5,10]]

Quite useful!

The instance for Maybe is not so useful:

λ> sequenceL (Just [1..5])
[Just 1,Just 2,Just 3,Just 4,Just 5]

... and the instance for These is quite unintuitive, especially if you've just used the list instance:

λ> sequenceL (These [1..3] [4.0 .. 8])
[These [1,2,3] 4.0,These [1,2,3] 5.0,These [1,2,3] 6.0,These [1,2,3] 7.0,These [1,2,3] 8.0]

(These does not have an Align instance; it is being used here via its Functor, so we can't do anything useful with the This a.)

Bicrosswalk

Unfortunately it is too perfect an abstraction to be useful. - elliott

Bicrosswalk is Crosswalk for bifunctors. If you're not into bifunctors, they are much like Functor, but of higher kind; in practice, this means we can map over two type parameters instead of just the one.

At the time of writing there were but two Bicrosswalk instances. Too perfect, indeed!

The Either instance means well, and is very friendly, but does not help us a lot:

λ> :t bisequenceL
bisequenceL :: (Bicrosswalk t, Align f) => t (f a) (f b) -> f (t a b)
λ> bisequenceL (Left [1..5])
[Left 1,Left 2,Left 3,Left 4,Left 5]
λ> bisequenceL (Right [1..5])
[Right 1,Right 2,Right 3,Right 4,Right 5]

... and the instance for These does what I expected its Crosswalk to do, aligning both values as best it can:

λ> bisequenceL (This [1..5])
[This 1,This 2,This 3,This 4,This 5]
λ> bisequenceL (That [1..5])
[That 1,That 2,That 3,That 4,That 5]
λ> bisequenceL (These [1..4] [5..7])
[These 1 5,These 2 6,These 3 7,This 4]

I can foresee the These instance being useful to someone, somewhere.

Chronicle

The package also includes Control.Monad.Chronicle , containing a mtl-style monad transformer with the hybrid error/writer functionality of These.

I'm out of energy for this post and I haven't used it before. I note it has renamed versions of most of Writer's key functions, plus equivalents to throwError and catchError. Looks useful, and could replace some of the awful things I do with EitherT.

You probably want to check for space leaks before running off and using it, since it resembles WriterT, the famous leaky monad.

Thanks

I'd like to thank the maintainers of these for providing lenses while avoiding a lens dependency.

Many of us choose not to use lenses or to use competing libraries, to avoid unnecessary constraints and upstream risk. It is a joy to discover an interesting new package that can be used without a moment's hesitation. Thank you.