Style question on chaining of partial results

Question
1

A question on style here…

I have an object algebra type that has various operations on it. These allow an algebra instance to apply operations through a result, like this (the type signatures are simplified)…

trait Algebra[Result]:
    def empty: Result
    def addSomething(partialResult: Result, newData: String): Result
    def forgetSomething(partialResult: Result, obsoleteKey: Int): Result
    def joinSomethingsTogether(partialResult: Result, thingOne: Int, thingTwo: Int): Result
end Algebra

Algebras can be supplied for production and for testing. It’s also possible to delegate from one algebra to another, performing some pre / post-processing in the outer algebra. Cool.

There is a consumer of algebras that takes an algebra and pumps out some result by applying operations (again, simplified):

def weeklyGrind[Result](algebra: Algebra[Result]): Result = 
    val monday = algebra.empty
    val tuesday = algebra.addSomething(monday, "A hard working day.")
    val wednesday = algebra.joinSomethingsTogether(tuesday, 3, 4)
    val thursday = algebra.forgetSomething(wednesday, -16)
    // Long weekend follows...
    thursday
end weeklyGrind

You might look at that result threading and wonder, but hold that thought…

So far, so good - the result threading isn’t too prolix in practice, as it happens.

However, the latest wheeze is to allow one algebra to be supplied to the weeklyGrind, and then to play back the same operations to another algebra with a completely different implementation. This is because weeklyGrind can be a very expensive computation in the real world case.

So let’s write an algebra to do that:

case class Recording(playback: [Result] => Algebra[Result] => Result)
//                               ^^^
// Polymorphic because we don't know what kind of result
// the downstream algebra will work with.


class RecordingAlgebra extends Algebra[Recording]:
  def empty: Recording =
    Recording(
      [Result] =>
        ((downstreamAlgebra: Algebra[Result]) => downstreamAlgebra.empty)
    )
  def addSomething(partialResult: Recording, newData: String): Recording =
    Recording([Result] => { (downstreamAlgebra: Algebra[Result]) =>
      val theStorySoFar = partialResult.playback(downstreamAlgebra)
      downstreamAlgebra.addSomething(theStorySoFar, newData)
    })

  def forgetSomething(partialResult: Recording, obsoleteKey: Int): Recording =
    ???
  def joinSomethingsTogether(
      partialResult: Recording,
      thingOne: Int,
      thingTwo: Int
  ): Recording = ???
end RecordingAlgebra

Now one can playback the working week ad-nauseum:

val onTheRecord = weeklyGrind(new RecordingAlgebra)

val _ = onTheRecord.playback(new DoSomeActualWorkAlgebra)

val _ = onTheRecord.playback(new BookInMindlessTaskCodesAlgebra)

val _ = onTheRecord.playback(new MoanEndlesslyAboutFutilityOfWorkAlgebra)

val _ = onTheRecord.playback(new BragHyperbolicallyBeforeBonusEvaluationAlgebra)

Scastie here

Excellent. The thing is, the way Recording.playback is defined leads to a deepening stack as the partial results are computed in their original order. This can be a problem in practice.

So I could refactor to use:

  1. explicit continuation-passing written in longhand to chain the merge algebra calls using tail recursion,
  2. or Eval to get a trampolined alternative to continuation passing,
  3. or State[Unit] to thread the partial results through the merge algebra calls (and keep the trampolining),
  4. or StateT[Reader, Unit] to thread the partial results and supply the merge algebra …
  5. … or something completely different.

I’m open to making Algebra into a typeclass too, but only if it significantly simplifies things.

What would you folks do?

2

Actually, I could just make Recording.playback a sequence of functions accepting an algebra and a partial result, and just add a method to Recording to left-fold an empty partial result through the playback. It means the initial call to .empty becomes a no-operation, but might work…

**EDIT: ** here’s the changed code for the example above:

case class Recording(
    steps: Vector[[Result] => Algebra[Result] => Result => Result]
):
//                ^^^
// Polymorphic because we don't know what kind of result
// the downstream algebra will work with.
  def playback[Result](algebra: Algebra[Result]): Result =
    steps.foldLeft(algebra.empty)((partialResult, step) =>
      step(algebra)(partialResult)
    )

class RecordingAlgebra extends Algebra[Recording]:
  def empty: Recording =
    Recording(steps = Vector.empty)
  def addSomething(partialResult: Recording, newData: String): Recording =
    partialResult.copy(steps =
      partialResult.steps.appended(
        [Result] =>
          (downstreamAlgebra: Algebra[Result]) =>
            downstreamAlgebra.addSomething(_, newData)
      )
    )

  def forgetSomething(partialResult: Recording, obsoleteKey: Int): Recording =
    ???
  def joinSomethingsTogether(
      partialResult: Recording,
      thingOne: Int,
      thingTwo: Int
  ): Recording = ???
end RecordingAlgebra

Ironically, I was thinking of just hacking out some imperative loop-through-actions thing that made me think of a sequence and folding. :grin: