Add method for mapping instruction

[safareli]

I needed to map instructions so I have wrote this:

Free.prototype.mapInstruction =function(f) {
  return this.cata({
    Pure: value => Free.Pure(value),
    Impure: (instruction, next) => Free.Impure(
      f(instruction),
      (x) => next(x).mapInstruction(f)
    )
  })
}

test('mapInstruction', t => {
  const tree = liftF(1).chain(
    a => liftF(2).chain(
      b => Free.of([a, b])
    )
  )

  t.deepEqual(
    tree.mapInstruction((a) => a + 2).foldMap((a) => Identity(a), Identity).x,
    [3,4],
    'should add 2 to all instructions in Free'
  )
  t.end()
})

I would create a PR but first i'm not sure if that name is ok.

I have looked at other implementations of Free monad and I think that this functions are what I have actually implemented above:

• hoistFree in haskell and purescript
• mapSuspension in scalaz.

So question is what to name this function?

It looks like hoist is changing container type but here we could also lift non container types (like numbers as in test) so it's not quite what Haskell/Purescript hoistFree is. Also if we use hoist in name it will cause confusion, one might think it's related to hoisting in js :D

IMHO equivalent for Suspension is Impure so we might call it mapImpure, but I don't know decision behind giving name Impure to what is called Free in haskell and Bind in Purescript.

As i was thinking and writing this issue I came to decision that it's actually a good name as it actually is mapping instruction which is in Impure, not whole Impure as there is also rest of instructions.

[safareli]

@DrBoolean could you review this?

BTW it will be nice if we create some kind of roadmap (maybe discuss this in seperate issue)

[DrBoolean]

Hello!

I got Impure from the free(er) monads paper, of which this library is an implementation.

I think Bind is probably the most intuitive name since we're using it like normal bind, but on the type level.

Gibbons has a terrific paper http://www.cs.ox.ac.uk/jeremy.gibbons/publications/dgp.pdf where at around page 25, he introduces a Bifunctor on Fix types.

I think we can introduce bimap, first, and second , then the above would be first and second would be normal map.

I think we'd need to check the laws (https://hackage.haskell.org/package/bifunctors-3.2.0.1/docs/Data-Bifunctor.html), but that sounds right because Free is just Fix with a Pure.

Thanks for all your help.

[DrBoolean]

Good call on the roadmap. I seriously think the only things are to understand the implications of @rjmk's PR (I'm such a jerk for not doing this) and either use that or port the PureScript implementation that has all the performance/memory enhancements.

I tend to want to write it "correctly", then pull out each piece and "imperative-ize" it so it's faster.

I haven't had any performance issues personally, but if you're using this with Redux, that might be an eventual concern. Stoked on that, btw, because i really wanted to try that, but i got "is not a plain object" before.

[safareli]

So in this Free structure (and in one I have ported), we have one type of node which holds values and other(s) which hold lifted instructions. so if we implement BiFunctor interface first would map instructions and second sould map values.

But when I was using this structure I also needed a way to do chain like on Trees. the chain I wanted should take a function which receives instruction (not value) and returns other Free structure. it's type should be something like this: (i -> Free b v) -> Free i v -> Free b v (i - instruction, v - value). if we just liftF instructions it should not change anything. But we could also return other Free structure which contains some more instructions.

For example we might have Free structure containing some FS instructions, with hoist we could transform one instruction into different (one to one ) but we we can't transform instruction into different Free structure (as it's jus map on instructions). With the chain we could for example transform all Free.Impure(Move(from,to),next) Instruction into:

Free.Impure(
  Read(from), 
  (content) => 
    Free.Impure(
      Write(to,content),
      () => 
        Free.Impure(
          Delete(from),
          () => next())))

So maybe it should also be BiMonad?

I have googled and found this and it's kinda what we want here, but then I have found BiMonad Laws in Scala's cats and it looks like BiMonad is combinatio of Mondad and CoMonad and there is also a link to some paper which contains some hardcore category stuff which I dont understend, so i dont know if it's correct to say that Free is BiMonad.

But anyway, i Think hoist is good name for doing map on instructions and graft for doingchain on instructions, as they describe what we are doing with our tree structure.

Here is implementation of graft:

Free.prototype.graft = fixDo(function(f) {
  return this.cata({
    Pure: value => Free.Pure(value),
    Impure: (instruction, next) => f(instruction).cata({
      Pure: value => Free.Pure(value),
      Impure: (subInstruction, subNext) =>
        Free.Impure(subInstruction,
          y => subNext(y).chain(
            z => next(z).graft(f)
          )
        ),
    })
  })
})

And here are some tests too.

[safareli]

Actually as a.foldMap(interpreter,of) is same as a.hoist(interpreter).retract(of) graft is actually more specific case where of is Free.of, a.graft(f) => a.foldMap(f, Free.of) => a.hoist(f).retract(Free.of), instead of transforming into different monad we are transforming Free i v into Free b v.

Free.prototype.graft = function(f) {
  return this.foldMap(f, Free.of);
}

So yeah we already have it :D

[DrBoolean]

Thanks for the ride! haha

I'm looking at the linked paper. I think i might want to struggle through it, thanks for pointing out bimonads

[safareli]

I have not even tried to read that paper :d did not quite understand comonads and category stuff.

Here is one observation a made on Free:

graft(f) = foldMap(f, Free.of)

// as map(f) = chain(compose(of, f))
hoist(f) = graft(compose(liftF, f)) = foldMap(compose(liftF, f), Free.of)

retract(of) => foldMap(id, of)

foldMap(f,of) = compose(retract(of), hoist(f))

So hoist, retract and graft could all be implemented with foldMap 🎉

Free.prototype.hoist =function(f) {
  return this.foldMap(compose(liftF,f), Free.of);
}
Free.prototype.retract = function(of) {
  return this.foldMap(id, of)
}
Free.prototype.graft = function(f) {
  return this.foldMap(f, Free.of);
}