# How to make function applicable to the most general container appropriate

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)

}
``````

I think there are two good approaches here:

• 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.

Regarding approach #1: In this particular instance, is there any actual advantage of `F[X] <: IterableOnce[X]`/`F[A]` over plain `IterableOnce[A]`?

Looks like `IterableOnce` may only be available in 2.13, can I use `TraversableOnce` in the mean time? or is that completely different?

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â€¦

1 Like

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.

Probably not, I think I got into the habit of doing it from writing methods that used the `F[_]` to do things with `CanBuildFrom`

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 `Int`s. 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â€¦

1 Like

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}"
}

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.

``````def calculate(dat: Data)(implicit show: Show[Data]): (Result, String) = {
process(dat) -> show(dat)
}

calculate(dat)                   // uses implicit helper
calculate(dat)(showDataDebug)    // explicitly provide desired helper
``````

VoilĂ .

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.