CODEWITHSUNDEEP
scalarecursionfunctional-programmingtree
Sebastian Zapata
Sebastian Zapata

Reputation: 180

regular shaped tree fold left scala implementation

I'm trying to implement a tail-recursive foldLeft function for a regular shaped tree. The exercise comes from the book, "The Science of Functional Programming," in exercise 3.3.5.3.

Until now, I was able to do the exercises but I don't know what I'm missing in this one.

There's is a definition for the regular shaped tree:

sealed trait RTree[A]
final case class Leaf[A](x: A) extends RTree[A]
final case class Branch[A](xs: RTree[(A,A)]) extends RTree[A]

The method signature and expected result:

@tailrec
def foldLeft[A,R](t: RTree[A])(init: R)(f: (R,A)=>R): R= ???

foldLeft(Branch(Branch(Leaf(((1,2),(3,4))))))(0)(_+_)
//10

The biggest problem so far is that I don't know how to match and access the element inside the case class of Branch. I can only match the Leaf and Branch (and not the leaf's inside a branch) and because of that the recursion has no end.

Upvotes: 7

Views: 344

Answers (1)

Ivan Kurchenko
Ivan Kurchenko

Reputation: 4063

Not sure if this helps, but for now I have only NON tail-recursive implementation.

def foldLeft[A, R](t: RTree[A])(init: R)(f: (R, A) => R): R = {
      t match {
        case Leaf(value) => f(init, value)
        case Branch(tree) =>
          foldLeft(tree)(init) {
            case (result, (left, right)) => f(f(result, left), right)
          }
      }
    }

UPDATE: As was said in comments section to this answer this is actually tail rec implementation, excuse me, for confusing you.

Upvotes: 6

Related Questions