isorecursive

// Хаскелист
trait Monoid[T] {
  val id: T
  def op: T => T => T
}

// Эмельщик
trait Monoid {
  type T
  val id: T
  def op: (T, T) => T
}

// Хардкорный эмельщик
type MONOID = {
  type T
  val id: T
  def op: (T, T) => T
}

// Джавист, прочитавший о self-типах
trait Monoidal[T] { this: T =>
  def op(x: T): T
}

// Джавист, прочитавший о имплицитных вьюхах
abstract class MonoidEnriched[T] {
  def op(y: T): T
}

// Джавист, прочитавший о тайпклассах
trait Monoid[T] {
  val id: T
  def op(x: T, y: T): T
}

// Джавист, прочитавший ещё и о карринге и частичном применении
trait Monoid[T] {
  val id: T
  def op(x: T)(y: T): T
}

// Хаскелист
implicit def list[T] = new Monoid[List[T]] {
  val id = Nil
  def op = xs => xs ++ _
}

// Эмельщик
implicit def list[E] = new Monoid {
  type T = List[E]
  val id = Nil
  def op = _ ++ _
}

// Хардкорный эмельщик
implicit def list[E]: MONOID { type T = List[E] } = new {
  type T = List[E]
  val id = Nil
  def op = _ ++ _
}

// Джавист, прочитавший о self-типах
class MonoidalListAdapter[T](val list: List[T]) extends Monoidal[MonoidalListAdapter[T]] {
  def op(x: MonoidalListAdapter[T]) = new MonoidalListAdapter[T](list ++ x.list)
}

// Джавист, прочитавший о имплицитных вьюхах
abstract class ListMonoidEnriched[T](x: List[T]) extends MonoidEnriched[List[T]] {
  def op(y: List[T]) = x ++ y
}

implicit def list[T](l: List[T]) = new ListMonoidEnriched(l)

// Джавист, прочитавший ещё и о имплицитных классах
implicit class ListMonoidEnriched[T](x: List[T]) extends MonoidEnriched[List[T]] {
  def op(y: List[T]) = x ++ y
}

// Джавист, прочитавший о тайпклассах
implicit def list[T] = new Monoid[List[T]] {
  val id = Nil
  def op(x: List[T], y: List[T]) = x ++ y
}

// Джавист, прочитавший ещё и о карринге и частичном применении
implicit def list[T] = new Monoid[List[T]] {
  val id = Nil
  def op(x: List[T])(y: List[T]) = x ++ y
}

// Ребята с тайпклассами
def f[M](xs: M)(implicit m: Monoid[M]) = m.op(xs, xs) // или m.op(xs)(xs)

// Хардкорный эмельщик
def f[M](xs: M)(implicit m: MONOID { type T = M }) = {
  import m._
  op(xs, xs)
}

// Джавист, прочитавший о self-типах
def f[M <: Monoidal[M]](xs: M) = xs.op(xs)

// Ребята с имплицитными вьюхами и классами
def f[M <% MonoidEnriched[M]](xs: M) = xs.op(xs)

class ~>[A](delayed: => A) {
  private lazy val value = delayed  
  def force() = value
}

implicit def thunkable[A](computation: => A)  =
  new ~>(computation)

implicit def forceable[A](computation: ~>[A]) =
  computation.force

def lazyInR(x: Int, y: ~>[Int]) = {
  val a = x + 5 * y
  val b = y - 5 * x
  a * b
}

def x: Int = {
  println("I'm printed once!");
  2
}

lazyInR(1, x)

class Node<K> {    
    public K key;
    
    public Node<K> left;
    public Node<K> right;
    
    public Node(K key) {
        this.key = key;
    }            

    public String toString() {
        String leftStr  = left  == null ? "nil" : left.toString(),
               rightStr = right == null ? "nil" : right.toString();            
        return "(" + key.toString() + " " + leftStr + " " + rightStr + ")";
    }
}

class AvlNode<K> extends Node<K> {
    public AvlNode<K> parent;
    public int height = 1;     
    
    public AvlNode(K key) { super(key); }
}