CODEWITHSUNDEEP
scalaabstract-data-type
raul ferreira
raul ferreira

Reputation: 916

Method Definition When Using Algebraic Data Type in Scala

I want to implement a Library in Scala. I'm just starting and i'm already having trouble to design it in a modular and scalable way.

I need some help! For instance i have defined an tree ADT

sealed trait Tree[+A,+B,+C]
case object EmptyTree extends Tree[Nothing, Nothing, Nothing]
case class Leaf[A,B,C](value: C) extends Tree[A,B,C]
case class Branch_A1[A,B,C](op: B, left: Tree[A,B,C]) extends Tree[A,B,C]
case class Branch_A2[A,B,C](op: A, left: Tree[A,B,C], right: Tree[A,B,C]) extends Tree[A,B,C]

The Branch_A# represents a function with # arguments. You can see where this is going.

Why A,B and C? Because the Leafs will be e.g. Double, and i have two types of functions Double => Double and (Double, Double) => Double. I'm worried about how this will scale as I increase the number diversity of the branches. I w.anted to make this very flexible

I have two questions, one technical, the other regarding my design pattern.

Technical Question

When i try to define generic methods to operate on such structures i get compile errors which I cannot solve. For instance:

sealed trait Tree[+A,+B,+C] {
  def evaluateTree[A,B,C] (t: Tree[A,B,C]): C = t match {
    case Leaf(value) => value
    case Branch_A1(op, left) => op(evaluateTree(left))
    case Branch_A2(op, left, right) => op(evaluateTree(left),evaluateTree(right))
  }
}
case object EmptyTree extends Tree[Nothing, Nothing, Nothing]
case class Leaf[A,B,C](value: C) extends Tree[A,B,C]
case class Branch_A1[A,B,C](op: B, left: Tree[A,B,C]) extends Tree[A,B,C]
case class Branch_A2[A,B,C](op: A, left: Tree[A,B,C], right: Tree[A,B,C]) extends Tree[A,B,C]

In op(evaluateTree(left)) i get "Application does not support parameters". I cant understand why.

Design Question

If the user of the library is to be allowed to express a domain which higher arity functions this will be hard to manage. The number of generics types will explode i guess. How can i design this in a better way? I wanted to make this scalable. Is the use of generic types the most proper? Or should another way? I read that about abstract data types are an alternative

Upvotes: 0

Views: 142

Answers (2)

raul ferreira
raul ferreira

Reputation: 916

In the following day i looked again to the problem and it all made sense. It was just me making generics a lot more complicated than they are in fact.

I had previously said that the generics types [A,B,C] could mean for instance [(Double,Double)=>Double, Double => Double, Double]. So i just need one parameterised type:

sealed trait Tree[+A]
case object EmptyTree extends Tree[Nothing]
case class Leaf[A](value: A) extends Tree[A]
case class Branch_A1[A](op: A => A, left: Tree[A]) extends Tree[A]
case class Branch_A2[A](op: (A,A) => A, left: Tree[A], right: Tree[A]) extends Tree[A]

Upvotes: 0

jwvh
jwvh

Reputation: 51271

To the Technical Question: the compiler doesn't have enough information about A or B to know if op(...) is possible/permitted or that, if invoked, it would return the correct type.

What if (to use a simpler example) you had written case Leaf(value) => value-1? The compiler isn't going to allow that until/unless C has been defined/restricted to some subset of types known to have a -(x:Int) method with a matching return type.

Upvotes: 1

Related Questions