I asked this question elsewhere, but re-reading the OP, it was posed far too complicated.
Here is a simpler formulation of the question.
How do I need to change the declaration of treeReduce so that I can call it on the most permissive type of container. The main thing is that objs is something which has a foldLeft method. Do I really need to use a structural type (as I understand is going away in Scala 3)? Or is there a correct superclass of Seq[A] which I need to use?
def treeReduce[A,B](objs: Seq[A], init: B, g:A=>B, f: (B,B) => B): B = {
def consumeStack(stack: List[(Int, B)]): List[(Int, B)] = {
stack match {
case (i, a1) :: (j, a2) :: tail if i == j => consumeStack((i + 1, f(a1, a2)) :: tail)
case _ => stack
}
}
val stack = objs.foldLeft((1, init) :: Nil) { case (stack: List[(Int, B)], ob: A) =>
(1, g(ob)) :: consumeStack(stack)
}
// there may be up to log_2 of objs.size many pairs left on the stack
assert(stack != Nil)
stack.tail.map(_._2).foldLeft(stack.head._2)(f)
}
Use a signature like def treeReduce[F[X] <: IterableOnce[X], A, B](objs: F[A], init: B, g: A => B, f: (B, B) => B): B.
Use a library like cats which will allow you to use the Foldable class to declare def treeReduce[F[_]: Foldable, A, B](objs: F[A], init: B, g: A => B, f: (B, B) => B): B. You’d then have to provide your own Foldable instance for any custom data type that you want to use.
Just to underscore this: Foldable is the correct answer to the question as stated – it’s the truly general solution to the problem.
Seriously, you really should get in the habit of using typeclasses – they’re the right answer to a lot of the problems you’re tossing out here, and you’re making life much harder for yourself by avoiding them…
Interesting comment. It’s not evident for me as a novice how to topologically sort the many 1000s of things I don’t understand. What does the learning path of typeclasses look like? In the mean time I’ll take a look at the explanation in the scalac documentation.
Yes, I think that is fine, apologies, I’ve been using the second approach for long enough that I don’t really remember the collections hierarchy well anymore.
They’re not hard if you get the right route in – I teach them in about 45 minutes. There are about a million tutorials available online, if you Google it. The one-minute summary is:
A typeclass is the functional-programming equivalent of an interface.
Your type doesn’t actually inherit from the typeclass; instead, you define a typeclass instance that says how to implement this typeclass for this type.
The typeclass instance should be implicit, and available at the call sites of the functions that need them, so that it gets picked up when needed.
The [T: MyTypeclass] syntax is called a context bound, and is syntax sugar for an extra (implicit ev: MyTypeclass[T]) parameter list on your function. Basically, this is how the function gets the right typeclass instance for your type.
There are (optional) fancy syntax tricks using implicits that let you use the functions defined in your typeclass in an object-oriented sort of way.
So Ordering[T] (in the standard library) is a typeclass that provides functions for order. Ordering[Int] is the instance that says how to implement those functions for Ints. A function with a signature like:
def myFunc[T: Ordering](t: T) = ...
means that it will accept any type T for which there is an Ordering instance available implicitly where myFunc is called. And that function can use implicitly[Ordering[T]] to get its hands on that typeclass instance. (Or spell out an explicit (implicit ordering: Ordering[T]) parameter list instead of using the context bound, and then use that ordering parameter directly – the two syntaxes are interchangeable, and you use whichever makes more sense at the moment.)
There are more details, but that’s the essence of it, and it’s the key to an enormous number of Scala libraries.
Important: scalac.io is in no way official. They’re good folks, but they’re a consultancy that specializes in Scala. (Similar to Lightbend, Underscore, Artima, etc.) This article is probably accurate (I don’t have time to read it), but is absolutely not official documentation…
Having just given this presentation at work… a Typeclass is a trait that defines behavior over some type and can be used as a helper for your code. In Cats there is a Show[A] typeclass with definition
trait Show[A] {
def show(item: A): String
}
With it I can define helpers for whatever type I wish in order to provide a mechanism for creating a String given a value of the type. In addition, unlike .toString() I can define multiple Show instances.
implicit object showData extends Show[Data] {
def show(item: Data): String = s"I've got Data, it's mine, and if you are lucky I will share. Data=${item.dat}"
}
object showDataDebug extends Show[Data] {
def show(item: Data): String = s";; Data=${item.dat}, internal state=${item.state}"
}
By making an instance of Show[Data] implicit I can get the compiler (I have a truly marvelous writeup on the rules for telling the compiler how to find implicits which this margin is too narrow to contain) to provide it for me when I want it without having to pass it in explicitly at call site.
PS - I see now that jducoeur beat me to the punch. Leaving this up since in my experience it can take multiple tellings for the utility of Typeclasses to sink in.