Proposal: specs for Maybe, Either, Tuple, Task, ...

[gcanti]

Sorry if it was discussed before, after scanning the issues I didn't find anything on the subject.

The motivation comes from the last addition: the spec for chainRec which I find hard to understand

chainRec :: ChainRec m => ((a -> c, b -> c, a) -> m c, a) -> m b

with respect to

class Monad m <= MonadRec m where
  tailRecM :: forall a b. (a -> m (Either a b)) -> a -> m b

Relevant issues

• Add ChainRec type class #151
• Add ChainRec specification #152

I understand the benefits of not depending on a particular implementation of Either but why fantasy-land doesn't provide a spec for Either in the first place?

For example writing the spec for Unfoldable would be problematic (Maybe AND Tuple)

class Unfoldable t where
  unfoldr :: forall a b. (b -> Maybe (Tuple a b)) -> b -> t a

We have great libraries out there for Maybe, Either, Task, etc... but there's no standard for them.

Would it be a good idea to add specs for these concrete types?

[rpominov]

Just as another example: a spec for Maybe could be used for mapMaybe #33 (comment)

[SimonRichardson]

Having used chainRec a few times now, I wish we had used Either.

I'm not totally sold on a whole spec for either as they type should say enough?

[safareli]

You can use Either and before returning it just do .fold(next, done) on it

About unfoldr it's type could be:

// unfoldr :: (Unfoldable t) => (((a, b) -> c, c, b) -> c) -> b -> t a
List.unfoldr((next, done, x) => x > 100 ? done : next(x*x, x+1), 0)

---

Also for example sanctuary or folktale could on their own Either and expose this function:

// chainRecWithEither :: (ChainRec m) => (TypRep m, a -> m (Either a r), a) -> m r
const chainRecWithEither = (T,f,i) => T.chainRec(
  (next,done,x) => f(x).map(e => e.fold(next,done)),
  i
)

---

Also using Either in chainRec is not a quite good idea imo. For example recently I saw there is an elm module elm-tail-recursion which uses Left as done and Right as next, when in old version of purescript-tailrec Left was used as next and Right as done. In current version of purescript-tailrec we have data Step a b = Loop a | Done b which I think better than Either.

[SimonRichardson]

Thanks @safareli some food for thought 👍

[rpominov]

Good point about ambiguous meaning of Left and Right in chainRec. Maybe we could have some general spec that would describe APIs of sum and product types? Something like a spec for daggy's cata method.

[safareli]

general spec that would describe APIs of sum and product types
@rpominov that's much better idea!

Some sketch of ideas:

// Step a b = Loop a | Done b
Step.types = ['Loop', 'Done']
Step.Loop = (a)  => ({ 
  type: Step.types[0], 
  constructor: Step,
  values: { _1: a },
  keys: ['_1'],
})
Step.Done = (a)  => ({ 
  type: Step.types[1], 
  constructor: Step,
  values: { _1: a },
  keys: ['_1'],
})

// Maybe a = Nothing | Just a
Maybe.types = ['Nothing', 'Just']
Maybe.Just = (a)  => ({ 
  type: Maybe.types[1], 
  constructor: Maybe,
  values: { _1: a },
  keys: ['_1'],
})
Maybe.Nothing = { 
  type: Maybe.types[0]
  constructor: Maybe,
  values: {},
  keys: [],
}

// List a = Nil | Cons a (List a)
List.types = ['Nil', 'Cons']
List.Cons = (a, b)  => ({ 
  type: List.types[1], 
  constructor: List,
  values: { _1: a, _2: b },
  keys: ['_1', '_2'],
})
List.Nil = { 
  type: List.types[0],
  constructor: List,
  values: {},
  keys: [],
}

// Tree a = Empty | Leaf a | Node a (Tree a) (Tree a)
Tree.types = ['Empty', 'Leaf', 'Node']
Tree.Node = (a, b, c)  => ({ 
  type: Tree.types[2], 
  constructor: Tree,
  values: { _1: a, _2: b , _3: c },
  keys: ['_1', '_2', '_3'],
})
Tree.Leaf = (a) => ({ 
  type: Tree.types[1], 
  constructor: Tree,
  values: { _1: a },
  keys: ['_1'],
})
Tree.Empty = { 
  type: Tree.types[0],
  constructor: Tree,
  values: {},
  keys: [],
}

using type, keys and values we can implement general fold or cata:

const valuesAsArray = v => {
  let args = []
  for (var i = 0; i < v.keys.length; i++) {
    args.push(v.values[v.keys[i]])  
  }
  return args
}
const fold = (fs, v) => {
  const idx = v.constructor.types.indexOf(v.type)
  if(idx == -1) throw new TypeError('invalid value')

  return fs[idx](...valuesAsArray(v))
}

const cata = (fs, v) => fs[v.type](...valuesAsArray(v))
// we can also check if `fs` does not contain functions for all `v.constructor.types`
//
// `keys` from instance could be moved to to Type, e.g.:
// Tree.typeNames = ['Empty', 'Leaf', 'Node']
// Tree.typeKeys = [
//   [],
//   ['_1'],
//   ['_1', '_2', '_3'],
// ]
//

[rjmk]

Maybe we could have some general spec that would describe APIs of sum and product types? Something like a spec for daggy's cata method.

Some good comments by @robotlolita and @SimonRichardson on that in #154

[robotlolita]

I'm not sure the spec describing specific data structures is a good idea, but as far as the description of tagged unions goes, something like OCaml's (and Lamdu's) Open Variants may be considered.

[joneshf]

Also using Either in chainRec is not a quite good idea imo. For example recently I saw there is an elm module elm-tail-recursion which uses Left as done and Right as next, when in old version of purescript-tailrec Left was used as next and Right as done. In current version of purescript-tailrec we have data Step a b = Loop a | Done b which I think better than Either.

Let me try to provide more motivation for my decision. I've found that if you type tailRec as (a -> Result a b) -> a -> b, (a -> Either a b) -> a -> b, or (a -> Step a b) -> a -> b, then the function is harder to use.

This is especially noticeable in PureScript because the Functor hierarchy works on the last type variable. We also lose most of the benefit of do notation.

If you break the recursion up into smaller functions and try to compose your functions, you end up having to complicate the problem a bit in order for things to line up. This is why go :: (Either Int Int -> Step Boolean (Either Int Int)) here. Compare that to my example here.

If you have (a -> Either b a) -> a -> b then you can rely on do notation pretty nicely:

foo = tailRec go
  where
  go x = do
    y <- bar x
    z <- baz y
    Left ("Barring " <> show x <> " with a bazzed " <> show y <> " gives " <> show z)

Whereas, with (a -> Either a b) -> a -> b you have to jump through some hoops. You can do things explicitly:

foo = tailRec go
  where
  go x =
    case bar x of
      Right b ->
        Right b
      Left y ->
        case baz y of
          Right b ->
            Right b
          Left z ->
            Right ("Barring " <> show x <> " with a bazzed " <> show y <> " gives " <> show z)

But, that's just using Either a b backwards from what we're used to with the Functor hierarchy. If you alpha-rename Right <-> Left, any knowledgeable PureScripter would point you to do-notation. Not to mention that the Functor hierarchy extends to typeclasses like Comonad f, Filterable f, and Traversable f. You could build up a set of combinators for working in the backwards world, but it feels wrong to force a new API on someone rather than building upon what they already know.

As far as Step a b vs Either a b. Step a b currently has a very limited API, so users have to do more wrapping/unwrapping just to get feature parity with Either a b. You have to write a function a -> Either a b and then wrap it in a function Either a b -> Step a b. Doesn't seem like a fair trade-off to impose on the user.

The point I wish to get across is that we don't get much benefit from renaming each value constructor. It might look prettier, but it's also demonstrably more difficult to use. We get a good deal more if you line up the type variables to play better with our Functor hierarchy—no matter what you name the value constructors.

[joneshf]

It pains me that we even have to question whether it's valuable to talk about Either a b. People have shown for decades that it's a useful data type. We use Compose f g a in Traversable t, why not use Either a b in chainRec.

Also, how does this function work:

chainRec :: ChainRec m => ((a -> c, b -> c, a) -> m c, a) -> m b

Where do you get the m b? For that matter, where do you get m c and b?. m must be covariant, since it's in the Functor hierarchy, and the only other b is in negative position. Am I missing something?

[rjmk]

I can't think of any cases where c is not t a b

[rpominov]

I can't think of any cases where c is not t a b

This actually follows from the algebraic types algebra:

https://www.youtube.com/watch?v=iXZR1v3YN-8

So pair of functions b -> a and c -> a is isomorphic to function Either b c -> a.

Not sure if this helps, I just though it's cool to mention 😄

[SimonRichardson]

As always @joneshf you put it way better than me...

[joneshf]

I hope that didn't come off negative. I'm not upset with any of the choices or comments anyone has made.

[SimonRichardson]

I found it very informative 😀