fantasyland / fantasy-land

Specification for interoperability of common algebraic structures in JavaScript
MIT License
10.11k stars 375 forks source link

Why is the class/constructor required as a parameter for `traverse` (or sequence)? #297

Closed babakness closed 6 years ago

babakness commented 6 years ago

A Fantasy-land compliant version of traverse might go something like this:

S.traverse (Array) (S.words) (S.Just ('foo bar baz'))

But why are we asking for the first (Array) parameter? If the words function must return an Array, could we not access the constructor of the Array as such:

const foo  = [1,2,3]
const foo2 = foo.constructor.of( 4,5,6 )

So why do we need Array at all? Here S.words returns an Array Monad contained within the Maybe. We can then derive the Array constructor as mentioned above to sequence an Array of Maybes.

evilsoft commented 6 years ago

From my understanding, I has to do with when you have say [ Maybe String ], but the data you get passed to you is an empty Array, you do not know how to construct a Maybe as there is no instance to get the Maybe from.

Same for like a Maybe [ String ]...if you receive a Nothing, you cannot construct the Array as there is no instance.

Even in a case like Either String [ Number ], if you ever get a Left that would be a String instance. In an adhoc language like JS, we can not infer the inner type from just a siggy.

davidchambers commented 6 years ago

@evilsoft is spot on. :)

babakness commented 6 years ago

@evilsoft @davidchambers I'm just experimenting with it right now and it works

export type Maybe<A> = Nothing<A> | Just<A>
export const Maybe = {
  // ..
  of: <A>(a: A): Maybe<A> => {
    return isNully(a) ?  nothing : Just.of(a) 
  },
}

class Nothing {
  // ...
  sequence<F extends URIS,B,C>( ) : any {
    return nothing 
  }
  traverse<F extends URIS,B,C>( this: Maybe<A> , fn: (a: A) => (HKT<F,B> & Apply<B>) | (HKT<F,B> & ArrayApply<B>)): Type<F,Maybe<B>> {
    return nothing
  }  
}

class Just { 
  // ...
  traverse<F extends URIS,B,C>( this: Maybe<A> , fn: (a: A) => (HKT<F,B> & Apply<B>) | (HKT<F,B> & ArrayApply<B>)): Type<F,Maybe<B>> {
    const functor = this.isJust() ? fn(this.value) : nothing
    return Maybe.of(functor).sequence()
  }  

  sequence<F extends URIS,B,C>( this: Maybe<HKT<F,A> & Apply<A>> ): any {
    const functor = this.isJust() ? this.value : nothing
    const isArray = (f):f is HKT<F, B> & ArrayApply<B> => Array.isArray(f) 
    return ( isArray(functor) ? functor[adtn.ap] : functor.ap )
      .call( functor, (functor.constructor as any).of( Maybe.of ) )
  }
}

test('sequence', t => {
  t.deepEqual(
     Maybe.of( 'it works' ).traverse( str => str.split(' ') ),
     [ Just.of('it'), Just.of('works')]
}) // passes

Am I misunderstanding the problem?

PS - ignore some superfluous types at the moment

evilsoft commented 6 years ago

What happens with Nothing? The expected result should be [ Nothing ] I believe

Need to turn a Maybe [ String ] into a [ Maybe String ]

EDIT: Sorry this is for sequence, but you want to turn a Maybe String into an [ Maybe String ]. using a String -> [ String ] (gosh traverse is the best bit ever IMO).

babakness commented 6 years ago

Ah, right ok, you get Nothing not [ Nothing ]

evilsoft commented 6 years ago

Pardon the silly pattern, but this is one way that I have implemented traverse on a Maybe type: https://github.com/evilsoft/crocks/blob/master/src/core/Maybe.js#L210

The left side of that either function is for the Nothing case, so it composes a Nothing constructor before the af or Applicative function resulting in the Applicative m => m Maybe a

So in short: the traverse is "run", but the "lifing" function is not. That af needs to come from somewhere, and that is what the TypeRep or a -> m a in the case of crocks (we accept both the Applicative TypeRep or an Apply returning function, which is why this pattern looks so silly.)

EDIT: notice that af is based on the f that is passed in and it only appears in the left or Nothing case.

EDIT AGAIN: Oh looks like the comment I was replying to was deleted. So sorry about that!

babakness commented 6 years ago

@evilsoft Hey! Didn't see your message before deleting the comment, I realized that of course Nothing can implement a traverse that wraps a Nothing into the desired Applicative.

Thanks for the reference, I like your library--its pretty awesome. I dig the runtime checks :-)