Implementing nested type constraints

[gcanti]

I'd love to hear your advice on how to implement nested type constraints.

Introduction

When I see the following spec

// Semigroup
concat :: Semigroup s => (s, s) → s

I automatically define the following 2 things (using pseudo code and the flow syntax in order to emphasize the types)

// Semigroup.js
export interface Semigroup<S> {
  concat(a: S, b: S): S
}

export function concat<S>(dictSemigroup: Semigroup<S>, a: S, b: S): S {
  return dictSemigroup.concat(a, b)
}

Here Semigroup<S> mimic a type class while dictSemigroup represent the Semigroup s => type contraint.

An example

const StringSemigroup = {
  concat(a: string, b: string): string {
    return a + b
  }
}

import { concat } from './Semigroup'
concat(StringSemigroup, 's1', 's2') // => 's1s2'

The problem

The problem comes when there are nested type contraints. Let's define a Semigroup instance for Maybe

// I can't implement this
const MaybeSemigroup = {
  concat<S>(a: Maybe<S>, b: Maybe<S>): Maybe<S> {
    if (isNothing(a) || isNothing(b)) {
      return Nothing
    }
    return Just(concat(?, a, b)) // <= here's the problem; I don't have an instance of Semigroup for S
  }
}

How could I implement MaybeSemigroup?

Now I'm doing something like this but I'm not entirely satisfied, are there other options?

function getMaybeSemigroup<S>(dictSemigroup: Semigroup<S>): Semigroup<Maybe<S>> {
  return concat<S>(a: Maybe<S>, b: Maybe<S>): Maybe<S> {
    if (isNothing(a) || isNothing(b)) {
      return Nothing
    }
    return Just(concat(dictSemigroup, a, b))
  }
}

[rpominov]

Interesting issue. We discussed it just yesterday in Fantasy Land's chat: https://gitter.im/fantasyland/fantasy-land?at=57b335271a7d02075684055b .

Yes, you need to have type dictionary of inner type in order to implement outer type's concat in Static Land. This is inherent limitation of Static Land compared to Fantasy Land https://github.com/rpominov/static-land#cons . We have to pass around type objects for any generic code.

[rjmk]

Is this fine for the spec? I'm implementing a These library inspired by @joneshf's example in Elm). If I implement a makeChain function that takes a type dictionary for a monoid, am I OK to be a static-land monad?

[rpominov]

I guess no one can answer for sure what is fine, we're all still exploring how this stuff fits into JS. But from strict static-land spec perspective: if a type dictionary obeys all laws for a particular algebra it's a correct static-land type that implements that algebra.

So if your makeChain function takes a type dictionary for a Monoid, and returns a type dictionary for Chain, for example, the only requirements for the result type dictionary is to obey Chain laws.

[gcanti]

As a side note, after using that technique for 9-10 days I can say I actually like it. At first seems a bit awkward (well, it is..) but unlike some Haskell/PureScript code where it's not always easy to guess which instance is involved, passing those dictionaries it's very explicit and easy to reason about, especially when you re-read your code after a few days. So I... "made a virtue of necessity"

[rjmk]

Yeah I hadn't thought of returning a dictionary. I actually really like the fact that means one is explicit about fixing one of the type variables in my case

El 27/08/2016, a las 16:29, Giulio Canti notifications@github.com escribió:

As a side note, after using that technique for 9-10 days I can say I actually like it. At first seems a bit awkward (well, it is..) but unlike some Haskell/PureScript code where it's not always easy to guess which instance is involved, passing those dictionaries it's very explicit and easy to reason about, especially when you re-read your code after a few days. So I... "made a virtue of necessity"

— You are receiving this because you commented. Reply to this email directly, view it on GitHub, or mute the thread.

[joneshf]

@gcanti You could also be lazy. Instead of saying, "Give me a type dict and two maybes and I'll return to you a new maybe." You could say, "Give me two maybes, and I'll return to you a function that needs a type dict to get a new maybe."

I'm not using flow since its syntax is incredibly bad.

const MaybeSemigroup = {
  concat(a, b) {
    return function(dictSemigroup) {
      return Maybe.ap(Maybe.map(x => y => concat(dictSemigroup, x, y), a), b);
    }
  }
}

You just push the responsibility to the caller rather than dealing with it yourself. Of course, that's no longer a Semigroup since

concat : (Maybe a, Maybe a) -> Semigroup a -> Maybe a

But you could change the type to be

concat : (Semigroup a -> Maybe a, Semigroup a -> Maybe a) -> Semigroup a -> Maybe a

const MaybeSemigroup = {
  concat(fa, fb) {
    return function(dictSemigroup) {
      const a = fa(dictSemigroup);
      const b = fb(dictSemigroup);
      return Maybe.ap(Maybe.map(x => y => concat(dictSemigroup, x, y), a), b);
    }
  }
}

This is slightly different from the original problem. But, if you look closely, that's a specific instance of Kleisli m a b. In this instance we have Kleisli Maybe (Semigroup a) a.

Also, I feel like you could write a kleisli semigroup once and for all m. It would only be one kind of Semigroup for a given m, but it seems like it would be principled.

Just some food for thought. :hamburger:

[rpominov]

Btw, what is a function that takes a type dictionary and returns another type dictionary? Is this higher kinded static-land type? 😮

[joneshf]

Does it need a special name?

[rpominov]

Maybe, if that become a common pattern like "Higher-Order Components" in React community. But it just seemed interesting to me to make that analogy.

[gcanti]

Thanks @joneshf, very interesting.

My main goal here was to come up with a "mechanical" and straightforward rule aimed to translate a PureScript signature to a FlowScript (or JavaScript) one, such that all the implementations are consistent. For example, here's a translation almost word by word

-- PuresScript
instance semigroupMaybe :: Semigroup a => Semigroup (Maybe a) where
  append Nothing y = y
  append x Nothing = x
  append (Just x) (Just y) = Just (x <> y)

to

// flow-static-land AKA FlowScript
const semigroupMaybe: (semigroupA: Semigroup<A>) => Semigroup<Maybe<A>> = semigroupA => ({
  concat(x, y) {
    if (prj(x) == null) {
      return y
    }
    if (prj(y) == null) {
      return x
    }
    return of(semigroupA.concat(prj(x), prj(y)))
  }
})

where type constraints are nicely translated to dict arguments

[joneshf]

Ah, then yeah, that's much better :).

[rpominov]

This is a great discussion, and please keep it going, but I'll close the issue since it seems resolved.