`sequence` on a Result behaves inconsistently

[diegovdc]

When sequencing a Result, Ok behaves differently than Err, namely, that Err requires it's contents to be put inside an array, to be properly concatenated, while Ok does not.

const crocks = require('crocks')
crocks.sequence(Result.of, [Ok(5), Ok(6)]) // Ok [5, 6]
crocks.sequence(Result.of, [Err(5), Err(6)]) // Err 5
crocks.sequence(Result.of, [Err([5]), Err([6])]) // Err [5, 6]

I feel this to be very unintuitive, and might lead to code that has an inconsistent (more than necessary) interface for it's return values (either returning an Ok a or an Err [b]), or code that may need to be flattened if one wants to be more "consistent" and return Ok [a].

[evilsoft]

ohhhh. looks like there may be a bug there! GREAT find, will def look into it!

[evilsoft]

Oh I am sorry, I misunderstood. This is the correct behavior, but I can understand why it is unintuitive at first glance. And it just so happens that there are all kinds of neat things in your provided example that may be adding to the confusion.

It starts with how sequence and traverse work with Sum Types, and more to the point it is how ap is implemented on Sum Types. That is the reason traverse can only work on a Traversable of Applicatives (or Applys in crocks if you pass an Apply returning function to the first argument).

So just to show the siggy of sequence may shed some light on your results, then I will show you how ap gets involved in all this mess. First lets start with Either Number String, with a Type of Number on the Left and String on the Right:

// sequence ::  t -> m (f a) -> f (m a)

// `t` is the TypeRep of our Applicative (so the Either constructor)

// `m` is our `Traversable`, so we will use `Array`, making it:
// [ f a ] -> f [ a ]

So it flips the types around, takes an Array of (f a)s and gives us an f of [ a ]

Now here is the first bit that makes it unintuitive. When dealing with Sum Types that a in the signature is referring to the far right instance, so with Either that would be Right.

// Replace `f` with `Either Number String` we get:
// [ Either Number String ] -> Either Number [ String ]

The thing to notice there is we only traverse on Right, the Left stays a Number. So when we encounter a Left at anytime, we need to keep the Either siggy 🌽sistant, and return a single Left of Number, for example:

// [ Either Number String ] -> Either Number [ String ]
sequence(Either, [ Right('one'), Right('two'), Right('three') ])
//=> Right [ 'one', 'two', 'three' ]

sequence(Either, [ Right('one'), Left(2), Right('three') ])
//=> Left 2

Notice how both results match the signature.

There is also another thing going on because of the behavior of Result. The only difference between Either and Result, is that when the left side Err is a semigroup, it will accumulate Err values over the Semigroup when used as either an Applicative or an Alt. Under the hood, traverse uses ap or the Apply portion of the Applicative.

So if we look at the signatures for the provided examples we see that it returning the accumulated value of the left side, which also happens to be the Traversable Array.

sequence(Result.of, [Ok(5), Ok(6)])
//=> Ok [ 5, 6 ]
// Result e [ Number ]

sequence(Result, [ Err(5), Err(6) ])
//=> Err 5
// Result Number [ a ]

sequence(Result, [ Err([ 5 ]), Err([ 6 ]) ])
//=> Err [5, 6]
// Result [ Number ] [ a ]

See how the types still line up. It may be easier to see what is going on if we change our Semigroup to say a String or a Sum Monoid:

// Result String [ Number ]
///////////////////////////
sequence(Result, [ Err('*'), Err('--'), Err('*'), Ok(42) ])
//=> Err "*--*"

sequence(Result, [ Ok(23), Ok(94), Ok(42) ])
//=> Ok [ 23, 94, 42 ]

// Result Sum [ String ]
////////////////////////

sequence(Result, [ Ok('Hello'), Ok('Bob') ])
//=> Ok [ "Hello", "Bob" ]

sequence(Result, [ Err(Sum(1)), Ok('Hello'), Err(Sum(1)) ])
//=> Err Sum 2

Notice how the types still line up just like with Either. The only difference is on the Err we accumulate Semigroups. But like your second case shows, when Err is not a Semigroup it will behave like Either and return the first Err is encounters.

So you may be wondering what the heck you could use that for, so here is a quick example that is less contrived than above and a little closer to Real World Usage, although I am using traverse just know that it does the same thing as sequence, but will lift a value in the Traversable into an instance of the target Applicative. So if you already have an Array of Applicatives you can still use traverse by providing identity as the required function const seqResult = traverse(Result, identity).

const {
  Result, bimap, compose, identity,
  traverse, tryCatch
} = require('crocks')

// tryParse :: a -> Result [ Error ] b
const tryParse = compose(
  bimap(x => [ x ], identity),
  tryCatch(JSON.parse)
)

// parseList :: [ a ] -> Result [ Error ] [ * ]
const parseList =
  traverse(Result, tryParse)

const good = [
  '{"a":true}',
  '[ 6, 7, 8 ]',
  true // silly JS
]

const bad = [
  '{a:false}',
  'true',
  [ 6, 7, 8 ]
]

parseList(good)
//=> 'Ok [ { a: true }, [ 6, 7, 8 ], true ]'

parseList(bad)
//=> 'Err [ SyntaxError, SyntaxError ]

Although more real world would capture what the value was (using fanout and joining it back in on Err using merge and making an object { value: '{a:false}', err: SyntaxError } that is wrapped in an Array. If you want to play around with fanout, merge, Pair and parallel execution with Product Types this would be a fun exercise for the reader.

I hope this helps clear up some of the unintuitive feel of Traversables with Sum Type Applicatives.

[diegovdc]

Wow, thanks @evilsoft for the amazing explanation!

Taking notice of how the types line up really makes it very clear.

Would it be ok to think that compose(sequence(Monad), map(fn)) === traverse(Monad, fn)?

[evilsoft]

Well yes and no. I would say they are equivalent in their results, but not equal, one is more performant than the other. The composition will map twice while the right side will map and apply in one iteration.

Also Monad is the wrong 🌽straint, it is less general then actual Applicative. So one thing you may have noticed is that when using traverse, each value in the is completely independent of the other values in the Traversable, the "calculation" of one is not dependent on others. The effects are, mind you; like if I hit a Left, I will return a Left. But the values inside of the instances have no part in the calculation of the next.

Applicative allows of "parallel" computation. A lot of the material out in the wild (except for the Tom Harding Blogs and a couple others) talks about the mechanics of being able to lift a function and apply different values, but miss out in the fact of what that implies. It means we can have many separate, non-dependent calculations that "can" run in parallel and can be combined in a meaningful way. The same way a Semigroup can be split up and parallelized.

Now, Monad adds the ability to calculate a value based on the value and effect of a previous calculation, this is not parallel, but sequential, one has to finish before the next calculation can be performed.

Now Maths-wise, Monad really adds the ability to lift values into its context (of) and the ability to turn (T ∘ T -> T) which is a natural transformation from a Functor T ∘ T which is T composed with T to the Endofunctor T (can you figure out WHY this has to be an Endofunctor?).

When we look at the component of this NT at some typea, with the Endofunctor T being say a Maybe we get Maybe Maybe a and it will turn that into a Maybe a. This is called join in Haskell, if I were to add it to crocks, I would probably call it joinM.

We typically do not need joinM as chain is essentially derived from joinM by taking advantage of the Functor. So if we had joinM, chain could be derived by doing fn => compose(joinM, map(fn)), simply by mapping (a-> T b) getting our T (T b) then running it through joinM to flatten. Also, you can derive joinM simply by doing chain(identity) (try that on an Array of Arrays and see what it does, pretty neat those Monads.

But because we do not need the values to be dependent on one another, we do not need to have the stronger Monad condition.

So all that said, the only way to have a Monad is to have the type be an Applicative Functor. So because a Monad has to be an Applicative first, your statement is correct, BUT traverse does not need to be as strong as a Monad and requiring it as such may lead people to believe that the functions is going to do something in sequence based on previous calculations.

Does this help, or does it make things worse?

[diegovdc]

It helps a lot. The importance of Applicative is very clear.

The only thing I am not getting is why does a Monad needs to be also an Applicative to be a Monad.

About the Endofunctor thing. A Monad needs to be an Endofunctor because chain allows the Monad to map over a function of type (a -> mb) and return mb (instead of m m b), thus being able to map back to itself (the meaning of "endo"), right?

[evilsoft]

Sorry about that I misspoke, Monad does not need to be Applicative (they are in fact two separate "paths"). BUT if I have chain, I can always derive ap is what I should have said.

It has to be an Endofunctor otherwise we could not form the T ∘ T. Because it is a Functor if I left the Category, I would have to get back to the original category with a different Functor (call it F) and it would be T ∘ F ∘ T which cannot be joined. Also T would take me back outside of the Category.

For instance we always wanna stay in our Category of Javascript, sure we can leave and come back (by faking the effects from the other category in our type implementations) but we always wanna deliver our Types or what have you to the enduser in our Javascript Category

[evilsoft]

Closing.