Sanctuary: Add Intercalate

[syaiful6]

So, we have joinWith that joins the strings of the second argument separated by the first argument. Which only work on array of string. What if i need to work with different container? Can we abstract this? Yes, by constraints it with Foldable and Monoid.

The type signature would be:

intercalate :: (Foldable f, Monoid m) => m -> f m -> m

[davidchambers]

This sounds useful, @syaiful6. Would you like to submit a pull request?

[syaiful6]

i would, but there is a problem, we look like need type representative for underlying Monoid in case the structure is empty. Now, i think it make it more complicated /weird than joinWith.

joinWith(',', ['a', 'b']);
// compared to
intercalate(String, ',', ['a', 'b']);

So, i start think better not to implements it after all? Can we get the type respresentative by it value?

[safareli]

As first argument is of same Monoid type, you can get empty from it's constructor prop:

// :: (Foldable f, Monoid m) => m -> f m -> m
intercalate  = (x, fx) => fx.reduce(...., x.constructor[fl.empty]())

[rjmk]

What about types made from applying type constructors, Irakli? Identity a is a monoid if a is, but Identity has the wrong kind to be a monoid. I'm a little out-of-date on FL so maybe there's away to handle that?

[davidchambers]

As a result of fantasyland/fantasy-land#180 it's no longer possible for the Identity type to satisfy the requirements of Monoid, @rjmk, so we're in the clear!

The fact that we can now define intercalate in general terms makes me feel very good about this breaking change to the FL spec. :)

[rjmk]

Does that mean that Reader r can no longer be an Applicative/Monad?

[davidchambers]

I don't know, Rafe. I haven't learnt about Reader yet. I imagine Irakli knows the answer. :)

[rjmk]

Perhaps a better example would be Validation e (An Either where you gather up further errors). The Applicative instance for Validation e has a monoid constraint on the e, so there'd be no way to make the of on the type representative?

edit: or even better, (,) a traditionally has a monoid constraint on a if you want to make an Applicative

[safareli]

@rjmk you are right you can't make Validation e Applicative, nor (,) a.
recently I wrote about making Maybe a Monoid, but it becomes problematic when you start defining map

[safareli]

@davidchambers Reader e a describes computation which produces some value of type a if you give it access to environment of type e. This description looks like a function and it's actually implemented using a function (type Reader e a = Reader (e -> a)).

Here are some videos about it:

• in this talk(Dead-Simple Dependency Injection) @runarorama starts with moving from Dependency injection to Inversion of control (aka passing an argument) and then gradually implements Reader and finally moves on Free monad.
• and this is small introduction from @drboolean about Reader.

[syaiful6]

Sorry, i don't have time recently, i will send the PR when i have time for this, maybe this week i can send PR for this, feel free to take over. :+1:

@rjmk i don't get it why Validation e can't implements applicative in FL, but i think we can implements it in regard of FL spec, for example take a look Folktale implementation, I believe they implements it correctly. But (,) a look like we can't because it product type, since when we construct them we must already know what's type would be on the first component. But Validation e is a union type, and pure function lift a value to it, then we can just take it and apply them to Success/Valid constructor.

you are right you can't make Validation e Applicative, nor (,) a.
recently I wrote about making Maybe a Monoid, but it becomes problematic when you start defining map

@safareli i don't clear why a Monoid can be problematic and affect Functor implementation, from my understanding they not related. Since Functor has kind * -> * and Monoid has kind *. Maybe a can implements Monoid but can't implements Functor, but, of course, it (Maybe type) can implements functor as Maybe.

[rjmk]

@syaiful6 Folktale doesn't comply to the latest FL spec; they're doing their own thing

[syaiful6]

@rjmk can you elaborate? The Folktale's Validation i mean is the one in Origami Tower.

[rjmk]

@syaiful6 Yep! Sorry last message was pretty useless.

Fantasy Land currently does things like require prefixed method names and an object called a type representative (if you implement certain algebras; Applicative is one of them). As far as I'm aware, Quildreen is not implementing those.

For something like Validation, you need your error type to be a Monoid to implement Applicative. That means you cannot create an type rep with an of method once and for all.

The same problem stands for the normal (,) a instance. The issue isn't the presence of the a.

[syaiful6]

@rjmk oh, i see. Quil implements the prefixed method and the type representative, But it implemented in their new lib (maintained on Origami Tower organization). Folktale use something like Daggy to implements Validation, the implementation for of like this:

Validation['fantasy-land/of'] = Success

That's all, you don't need info for Monoid representative there, in fact Validation doesn't require Monoid, only Semigroup. But for Tuple it does require Monoid, that's why we can't express it on FL.

[rjmk]

Yep, you're right for Validation we do only need Semigroup and it is the presence of the a that requires the Monoid

[syaiful6]

Well, look like we need to discuss this on other chat room. But, as i am aware Validation doesn't require Monoid on it implementation of Applicative, even on Haskell/Purescript.

[rjmk]

Sorry message above should have read "... it is the presence of a in (,) a". Just agreeing with you!

[masaeedu]

I think this sort of problem should be resolved by representing typeclass instances as explicit dictionaries, and typeclass constraints as explicit parameters. For example, the intercalate function would be:

const Arr = (() => {
  // Constructors
  const Nil = []
  const Cons = x => xs => [x, ...xs]
  const match = ({ Nil, Cons }) => arr =>
    arr.length === 0 ? Nil : Cons(arr[0])(arr.slice(1))

  // Foldable
  const foldMap = M => f => arr =>
    arr.reduce((p, c) => M.append(p)(f(c)), M.empty)
  const fold = M => foldMap(M)(x => x)

  // Monoid
  const empty = []
  const append = x => y => [...x, ...y]

  // Misc
  // I just copied all these from the haskell definitions
  const prependToAll = s => match({
    Nil,
    Cons: x => xs => Cons(s)(Cons(x)(prependToAll(s)(xs)))
  })

  const intersperse = s => match({
    Nil,
    Cons: x => xs => Cons(x)(prependToAll(s)(xs))
  })

  const intercalate = M => m => arr => fold(M)(intersperse(m)(arr))

  return {
    Nil, Cons, match,
    foldMap, fold,
    empty, append,
    prependToAll, intersperse, intercalate
  }
})()

// Test
const Str = { empty: "", append: x => y => x + y }
console.log(Arr.intercalate(Str)(" mississippi, ")(["one", "two", "three", "four"]))
// => "one mississippi, two mississippi, three mississippi, four"

While fantasy land is good for many things, I think the early decision made to tie everything to prototypes is acting as a drag on adding many nice utilities that would be easy to define with a more systematic approach to typeclasses.

[davidchambers]

Would you like to submit a pull request, @masaeedu?

[masaeedu]

@davidchambers For which thing? I'd really like Sanctuary to adopt a consistent dictionary passing style instead of the fantasy-land style, but this is a big change that should probably be discussed in a different issue.

As far as intercalate is concerned I could probably do a PR with a typerep for the monoid in the meantime.

[davidchambers]

As far as intercalate is concerned I could probably do a PR with a typerep for the monoid in the meantime.

This would be great! It could serve as a concrete example of the dictionary passing you would like to see used more broadly. :)

[masaeedu]

Ok, cool. Do you want intersperse, prependAll as first class things as well?

[davidchambers]

I imagine so, but let's add one function at a time, in individual pull requests.

[masaeedu]

Ok. I actually need to add them all at once because intercalate is defined in terms of the other two, but I'll start by only exposing intercalate.