chapter 12 Composition comp1 definition

[tiagojdf]

I am trying to get my head around the section composition in chapter 12, and I don't understand how comp1 is working:

const comp1 = compose(sequence(Compose.of), map(Compose.of));
comp1(Identity(Right([true])));
// Compose(Right([Identity(true)]))

The way I see it:

map(Compose.of)(Identity(Right([true])))
// Identity(Compose([Right(true)]))
sequence(Compose.of)
// Compose(Identity([Right(true)])) !== Compose(Right([Identity(true)]))

Could you help me figure out what I am misunderstanding on this example?

[BJS-kr]

I got stuck there too. same reason but I think comp1's result is Compose(Identity(Right([true]))) not Compose(Identity([Right(true)])) as you mentioned.

1. map: Identity(Right([true])).map(Compose.of) -> Identity(Compose(Right([true])))
2. sequence: Identity(Compose(Right([true]))).sequence(Compose.of) -> Identity(...).traverse(Compose.of, x => x) -> Compose(Right([true])).map(Identity.of) -> Compose(Identity(Right([true]))

const comp1 = compose(map(map(sequence(Compose.of))), map(sequence(Compose.of)), Compose.of);
const comp2 = (Fof, Gof) => compose(Compose.of, map(sequence(Gof)), sequence(Fof));

would be more rational I think.

[sevillaarvin]

This was confusing for me as well. I understand what it's doing step-by-step, but I don't get what this law is trying to say.

Given an initial nested functor, Identity (Maybe ([123])), this functor has three layers:

1. Identity
2. Maybe
3. Array

In comp1, we create a Compose functor using the inner value of Identity:

1. Maybe
2. Array

resulting into Identity (Compose (Maybe ([123]))).

Then we swap the Identity and Compose functors.

However, since this is a Compose functor, I assume that the order of functors inside the Compose functor need to be preserved, therefore, instead of naively swapping Compose with Identity, such as Compose (Identity (Maybe ([123]))),

we move Compose to the place of Identity, then move Identity to the "last" place of the Composed functors, Compose (Maybe ([Identity (123)])). So now compose has an additional functor from two to three:

1. Maybe
2. Array
3. Identity (NEW, SWAPPED)

In comp2, we swap the outer layer of the given functor, resulting into Maybe (Identity [123]). Then we swap the inner value of Maybe, resulting into Maybe ([Identity 123]). Then we just wrap Compose directly, Compose (Maybe ([Identity 123]))

#+begin_src js :noweb no-export :results code
  <<js curry>>
  <<js compose>>
  <<js map>>
  <<js sequence>>
  <<js compose applicative>>
  <<js identity traversable>>
  <<js maybe traversable>>
  <<js list traversable>>

  // Compose.of :: x -> Compose F G x
  const iofm = Identity.of(Maybe.of([123]))  // Identity (Maybe [123])

  const x = Compose.of(iofm)                 // Compose (Identity (Maybe ([123])))

  // const comp1 =
  //   compose(sequence(Compose.of), map(Compose.of))
  const y = map(Compose.of)(iofm)            // Identity (Compose (Maybe ([123])))
  const z = sequence(Compose.of)(y)          // Compose (Maybe ([Identity (123)]))

  // const comp2 = (Fof, Gof) =>
  //   compose(Compose.of, map(sequence(Gof)), sequence(Fof))
  const a = sequence(Identity.of)(iofm)      // Maybe (Identity [123])
  const b = map(sequence(Maybe.of))(a)       // Maybe ([Identity 123])
  const c = Compose.of(b)                    // Compose (Maybe ([Identity 123]))

  return {
    x,
    y,
    z,
    a,
    b,
    c
  }
#+end_src

#+RESULTS:
#+begin_src js
{
  x: Compose { val: Identity { val: [Maybe] } },
  y: Identity { val: Compose { val: [Maybe] } },
  z: Compose { val: Maybe { val: [Array] } },
  a: Maybe { val: Identity { val: [Array] } },
  b: Maybe { val: [ [Identity] ] },
  c: Compose { val: Maybe { val: [Array] } }
}
#+end_src

full javascript code

const curry = (f) => {
  const arity = f.length

  return function currier(...args) {
    if (args.length < arity) {
      return currier.bind(null, ...args)
    }

    return f.apply(null, args)
  }
}
const compose = (...fs) => (...args) => {
  return fs.reduceRight(
    (result, f) => [f.apply(null, result)],
    args
  )[0]
  // alternatively:
  // return fs.reduceRight((result, f) => f.apply(null, [].concat(result)), args)
}
const map = curry((fn, f) => f.map(fn))
const sequence = curry((o, f) => f.sequence(o))
class Compose {
  constructor(fgx) {
    this.val = fgx
  }

  static of(fgx) {
    return new Compose(fgx)
  }

  map(fn) {
    const map = curry((fn, f) => f.map(fn))
    // return new Compose(this.val.map((x) => x.map(fn)))
    return new Compose(map(map(fn), this.val))
  }

  ap(f) {
    return f.map(this.val)
  }
}
class Identity {
  constructor(val) {
    this.val = val
  }

  static of(val) {
    return new Identity(val)
  }

  map(fn) {
    return new Identity(fn(this.val))
  }

  join() {
    return this.val
  }

  chain(fn) {
    return this.map(fn).join()
  }

  ap(f) {
    return f.map(this.val)
  }

  sequence(_of) {
    const id = (x) => x
    return this.traverse(_of, id)
    // evaluates to:
    // return fn(this.val).map(Identity.of)
    // which evaluates to:
    // return this.val.map(Identity.of)

    // equivalent form using ap:
    // return Identity.of(Identity.of).ap(this.val)
  }

  traverse(_of, mfn) {
    // 1. transform the value and
    //    return an applicative functor
    const transformed = mfn(this.val)

    // 1. wrap the value of the applicative functor
    //    with the traversable
    const wrapped = transformed.map(Identity.of)

    return wrapped
  }
}
class Maybe {
  constructor(val) {
    this.val = val
  }

  static of(val) {
    return new Maybe(val)
  }

  get isNothing() {
    return this.val === null || this.val === undefined
  }

  map(fn) {
    return this.isNothing ? this : new Maybe(fn(this.val))
  }

  join() {
    return this.isNothing ? this : this.val
  }

  chain(fn) {
    return this.map(fn).join()
  }

  ap(f) {
    return f.map(this.val)
  }

  sequence(_of) {
    const id = (x) => x
    return this.traverse(_of, id)
    // evaluates to:
    // return this.val.map(Maybe.of)
  }

  traverse(of, fn) {
    if(this.isNothing) {
      return of(this)
    }

    // short version:
    // return this.isNothing ? of(this) : fn(this.val).map(Maybe.of)

    // 1. take out the value of the traversable
    const unwrapped = this.val

    // 2. apply the monadic function to the
    //    unwrapped value. note that this should
    //    return a wrapped value of an applicative
    const transformed = fn(unwrapped)

    // 3. wrap back the value of the transformed wrapper
    //    to the traversable. since in step #1 we
    //    unwrapped the value, we have to wrap it back
    //    afterwards
    const rewrapped = transformed.map(Maybe.of)

    return rewrapped
  }
}
class List {
  constructor(vals) {
    this.val = vals
  }

  static of(val) {
    return new List([val])
  }

  concat(val) {
    return new List(this.val.concat(val))
  }

  map(fn) {
    return new List(this.val.map(fn))
  }

  sequence(of) {
    const id = (x) => x
    return this.traverse(_of, id)
  }

  // of() must return an applicative
  // fn() must return the same type as of()
  traverse(of, fn) {
    return this.val.reduce(
      // (f, a) => fn(a).map(b => bs => bs.concat(b)).ap(f),
      (f, a) => {
        // 1. wrap the unwrapped traversable values
        //    using the monadic function and
        //    return an applicative functor
        const transformed = fn(a)

        // 2. create a function with the first argument as
        //    the applicative functor's value, i.e.,
        //    =a= will be passed to =b=
        const mapped = transformed.map(b => bs => bs.concat(b))

        // 3. apply the accumulator which is an applicative functor
        //    as the last argument to the function in #2.
        //    as a result, this will unwrap it, passing List() to bs
        const applied = mapped.ap(f)

        return applied
      },
      of(new List([]))
    )
  }
}

// Compose.of :: x -> Compose F G x
const iofm = Identity.of(Maybe.of([123]))  // Identity (Maybe [123])

const x = Compose.of(iofm)                 // Compose (Identity (Maybe ([123])))

// const comp1 =
//   compose(sequence(Compose.of), map(Compose.of))
const y = map(Compose.of)(iofm)            // Identity (Compose (Maybe ([123])))
const z = sequence(Compose.of)(y)          // Compose (Maybe ([Identity (123)]))

// const comp2 = (Fof, Gof) =>
//   compose(Compose.of, map(sequence(Gof)), sequence(Fof))
const a = sequence(Identity.of)(iofm)      // Maybe (Identity [123])
const b = map(sequence(Maybe.of))(a)       // Maybe ([Identity 123])
const c = Compose.of(b)                    // Compose (Maybe ([Identity 123]))

return {
  x,
  y,
  z,
  a,
  b,
  c
}

[lachrymaLF]

@sevillaarvin is right, because map is called on Compose, which reaches two layers deep into the functor, both results are indeed Compose(Right([Identity(true)])). So comp1 is correct.

Because traverse(f) === compose(sequence, map(f)) (this wasn't really made obvious in the book), the composition law is equivalent to saying traverse(compose(Compose.of, map(g), f)) === compose(Compose.of, map(traverse(g)), traverse(f)). (One traversal of the composition is equivalent to traversing twice individually)

[BJS-kr]

@sevillaarvin @lachrymaLF thanks for helping me out!