CODEWITHSUNDEEP
scalapattern-matching
CodingNow
CodingNow

Reputation: 1028

Scala: Is there an elegant way to compare values in pattern matching?

I'm trying to implement a simple binary tree using scala. My tree definition is as below:

abstract class Tree[T <: Ordered[T]]
case class Node[T <: Ordered[T]](v:T, l:Tree[T], r:Tree[T]) extends Tree[T]
case class Leaf[T <: Ordered[T]](v:T) extends Tree[T]

And I'm trying to implement a method to find the minimum value in the tree. The method implementation is as below:

def minInTree[T <: Ordered[T]](t: Tree[T]): T = t match {

    case Node(v, lft, rght) if minInTree(lft) > minInTree(rght) => {
        val mLft = minInTree(lft)
        val mRght = minInTree(rght)
        if (v > mRght)
           mRght
        else
           v
    }

    case Node(v, lft, rght) if minInTree(lft) <= minInTree(rght) => {
        val mLft = minInTree(lft)
        val mRght = minInTree(rght)
        if (v > mLft)
            mLft
        else
            v
    }
    case Leaf(lf) => lf
}

I found that minInTree(lft) and minInTree(rght) are called multiple times, which I believe is slow and ugly. The comparison uses multiple if-else clause, which I believe is also ugly.

Is there any elegant way to restructuring the code? Any hints are appreciated.

Upvotes: 1

Views: 428

Answers (3)

volia17
volia17

Reputation: 938

As jwvh wrote, you can use Ordering to have a cleaner code. An other way to have a cleaner code is to use inheritence in place of pattern matching :

println("Welcome to the Scala worksheet")       //> Welcome to the Scala worksheet

sealed trait Tree[T] {
    def min(implicit ev : Ordering[T]) : T
}

case class Node[T](value : T, left : Tree[T], right : Tree[T]) extends Tree[T] {
    def min(implicit ev : Ordering[T]) : T = ev.min(value, ev.min(left.min(ev), right.min(ev)))
}

case class Leaf[T](value : T) extends Tree[T] {
    def min(implicit ev : Ordering[T]) : T = value
}

val tree = Node(17, Leaf(2), Node(4, Leaf(10), Leaf(8)))
                                              //> tree  : testTree#626615.Node#1020777[Int#918] = Node(17,Leaf(2),Node(4,Leaf(
                                              //| 10),Leaf(8)))
tree.min                                  //> res0: Int#918 = 2

I prefer to add the Ordering typeclass only for the min method, when you need it. If you still want a function, it is very easy :

def minTree[T](t : Tree[T])(implicit ev : Ordering[T]) = t.min
minTree(tree)                             //> res1: Int#918 = 2

Upvotes: 2

jwvh
jwvh

Reputation: 51271

If you were to use the Ordering type class you could then employ the min() method on your values, which makes things much more elegant.

abstract class Tree[T: Ordering]
case class Node[T: Ordering](v:T, l:Tree[T], r:Tree[T]) extends Tree[T]
case class Leaf[T: Ordering](v:T) extends Tree[T]

def minInTree[T](t: Tree[T])(implicit ev:Ordering[T]): T = t match {
  case Node(v, lft, rght) => ev.min(v, ev.min(minInTree(lft), minInTree(rght)))
  case Leaf(lf) => lf
}

Import some handy implicits and the min evaluations are even clearer.

import Ordering.Implicits._
def minInTree[T: Ordering](t: Tree[T]): T = t match {
  case Node(v, lft, rght) => v min minInTree(lft) min minInTree(rght)
  case Leaf(lf) => lf
}

It also makes the basic comparison operations available. (<, >, etc.)

Upvotes: 3

Alexey Romanov
Alexey Romanov

Reputation: 170835

I would just move the comparison later, I don't think there's a good way to achieve this otherwise:

case Node(v, lft, rght) => {
    val mLft = minInTree(lft)
    val mRght = minInTree(rght)
    if (mLft > mRght) ... // corresponds to if minInTree(lft) > minInTree(rght) => ...
    else ... // corresponds to your second branch
}

Upvotes: 2

Related Questions