Creating immutable datastructures in Scala

I decided to take a shot at creating a simplified version of an immutable list structure and this is the result.

	package lists
	abstract class MyList[+A] {
	def isEmpty: Boolean
	def head: A
	def tail: MyList[A]
	def elementsToString: String = head + (if (tail.isEmpty) "" else ", " + tail.elementsToString)
	def length: Int
	/**
	* prepend elements of list to this list
	*/
	def ++:[B >: A](list: MyList[B]): MyList[B] = {
	if (isEmpty) list
	else if (list.isEmpty) this
	else FilledList(list.head, list.tail ++: this)
	}
	/**
	* append elements of list to this list
	*/
	def :++[B >: A](list: MyList[B]): MyList[B] = this ++: list
	/**
	if (isEmpty) list else FilledList(head, tail ++: list)
	**/
	/**
	* prepend element to this list
	*/
	def +:[B >: A](ele: B): MyList[B] = FilledList(ele, this)
	/**
	* append element to this list
	*/
	def :+[B >: A](ele: B): MyList[B] = this ++: FilledList(ele, EmptyList)
	/**
	if (isEmpty) FilledList(ele, EmptyList) else FilledList(head, tail :+ ele)
	**/
	}
	case object EmptyList extends MyList[Nothing] {
	override def isEmpty = true
	override def head: Nothing = throw new NoSuchElementException("head of empty list")
	override def tail: MyList[Nothing] = throw new UnsupportedOperationException("tail of empty list")
	override def length: Int = 0
	}
	case class FilledList[B](hd: B, tl: MyList[B]) extends MyList[B] {
	override def head : B = hd
	override def tail : MyList[B] = tl
	override def isEmpty: Boolean = false
	override def toString: String = "FilledList(" + elementsToString + ")"
	override def length: Int = 1 + tl.length
	}
	object MyList {
	def apply[A](xs: A*): MyList[A] = {
	if (xs.isEmpty) EmptyList
	else FilledList(xs.head, apply(xs.tail: _*))
	/**
	var result: MyList[A] = EmptyList
	for (ele <- xs.reverse) {
	result = ele +: result
	}
	result
	**/
	}
	}
	/************ Below some examples from a worksheet ************/
	import lists.{MyList, EmptyList, FilledList}
	val list1 = FilledList(4, FilledList(5, FilledList(6, EmptyList)))
	val list2 = FilledList(8, FilledList(9, EmptyList))
	val list3 = 7 +: list2
	val list4 = list1 ++: list2 //prepending list1 to list2
	val list5 = list1 :+ 7
	val list6 = list1 :++ list2 //appending list2 to list1
	val list7 = MyList(5,6,7,8)
	val list8 = EmptyList
	/** output
	> list1: lists.FilledList[Int] = FilledList(4, 5, 6)
	> list2: lists.FilledList[Int] = FilledList(8, 9)
	> list3: lists.MyList[Int] = FilledList(7, 8, 9)
	> list4: lists.MyList[Int] = FilledList(4, 5, 6, 8, 9)
	> list5: lists.MyList[Int] = FilledList(4, 5, 6, 7)
	> list6: lists.MyList[Int] = FilledList(4, 5, 6, 8, 9)
	> list7: lists.MyList[Int] = FilledList(5, 6, 7, 8)
	> list8: lists.EmptyList.type = EmptyList
	**/

view raw gistfile1.scala hosted with ❤ by GitHub