fork download
copy 
  1. object Main extends App {
  2.     abstract class Tree {
  3.         val datum: Int
  4.         val left: Tree
  5.         val right: Tree
  6.  
  7.         def isEmpty: Boolean
  8.  
  9.         def insert(newDatum: Int): Tree = {
  10.             if(datum < newDatum)
  11.                 Node(datum, left, right insert newDatum)
  12.             else if(datum > newDatum)
  13.                 Node(datum, left insert newDatum, right)
  14.             else 
  15.                 this
  16.         }
  17.  
  18.         def fold[A](init: A)(fn: (A,Int) => A): A = this.isEmpty match {
  19.             case false => (right fold fn((left fold init)(fn), datum))(fn)
  20.             case _ => init
  21.         }
  22.  
  23.         def merge(t: Tree) = (this fold t)(_ insert _)
  24.         override def toString = (this fold "")(_ + _ + ", ")
  25.     }
  26.  
  27.     object Empty extends Tree {
  28.         lazy val right = throw new Exception()
  29.         lazy val left = throw new Exception()
  30.         lazy val datum = throw new Exception()
  31.  
  32.         def isEmpty = true
  33.  
  34.         override def insert(newDatum: Int) = Node(newDatum, Empty, Empty)
  35.     }
  36.  
  37.     case class Node(datum: Int, left: Tree, right: Tree) extends Tree {
  38.         def isEmpty = false
  39.     }
  40.  
  41.     object Tree {
  42.         def apply(data: Int*) = (data foldLeft (Empty: Tree))(_ insert _)
  43.     }
  44.  
  45.     println(Tree(5,2,3))
  46.  
  47.     println(Tree(5,2,3) merge Tree(6,2,4))
  48. }
Success #stdin #stdout 0.3s 247552KB
comments (?)
stdin
copy 
1
2
10
42
11
stdout
copy 
2, 3, 5, 
2, 3, 4, 5, 6,
https://ideone.com/l1l8nQ
language:
Scala (scala 2.12.8)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!