module program2

/**
 * Kinds:
 *
 * Bool     *
 * Bin      *->*
 * Rose     *->*
 * Bin Int  *
 * Tree     *->*->*
 * T1       (*->*)->*->*
 * T2       (*->*)->(*->*)->*->*
 * T3       (a->b->*)->a->b->*
 *  - For instance, C3 (1,2) with a = b = *
 *  - Or, C3 (Box [1,2,3]) with a = *->*, b = * (:: Box t u = Box (t u))
 * T4       (b->*)->(a->b)->a->*
 *  - For instance, C4 [[1]] with a = *, b = *
 *  - Or, C4 (IntBox (Box [5])) with a = *->*, b = *->* (:: IntBox t = IntBox (t Int))
 */

import StdEnum
import StdFunc
import StdList
import StdString

class Container t
where
	Cinsert :: a (t a) -> t a | < a
	Ccontains :: a (t a) -> Bool | <, Eq a
	Cshow :: (t a) -> [String] | toString a
	Cnew :: t a

:: Bin a = Leaf | Bin (Bin a) a (Bin a)

instance Container []
where
	Cinsert x xs = [x:xs]
	Ccontains x xs = isMember x xs
		// It would be nice if it were possible to write functions with arity
		// that does not match the type, especially for classes where it is not
		// easy to change the type. This can be implemented as sugar.
	Cshow xs = map toString xs
	Cnew = []

instance Container Bin
where
	Cinsert x Leaf = Bin Leaf x Leaf
	Cinsert x b=:(Bin l y r)
	| x < y     = Bin (Cinsert x l) y r
	| x > y     = Bin l y (Cinsert x r)
	| otherwise = b // Assuming that we don't want to store a value multiple times
	Ccontains _ Leaf = False
	Ccontains x (Bin l y r)
	| x == y    = True
	| x <  y    = Ccontains x l
	| otherwise = Ccontains x r
	Cshow Leaf = []
	Cshow (Bin l x r) = Cshow l ++ [toString x:Cshow r] // Terrible complexity, but easiest implementation
	Cnew = Leaf

Start = (Ccontains 3 c, Cshow c)
where
	c :: Bin Int // Change to [Int] for testing the [] instance
	c = foldr Cinsert Cnew [10..20]