Create your own 'typed' Map implementation in Scala

trait MyMap[K,V] {
 def get(x:K):V
 def +(x:K, y:V):MyMap[K,V]
 def isEmpty:Boolean
 def keys:List[K]
 def values:List[V]
}
object MyMap{
 def apply[K,V](x:Tuple2[K,V]*):MyMap[K,V] = new MyMapImpl[K,V](x.toList)
 class MyMapImpl[T,M](var myMap:List[Tuple2[T,M]]) extends MyMap[T,M] {
  def get(x:T):M = {
   for((key,value)<-myMap) {
    if(key==x)
    return value
   }
   throw new Exception("Value not found!!!")
  }
  def +(x:T,y:M):MyMapImpl[T,M] = {
   for((key,value)<-myMap){
    if(key==x)
    throw new Exception("Key value already exists")
   }
   myMap::=Tuple2(x,y)
   new MyMapImpl[T,M](myMap)
  }
  def isEmpty:Boolean = if (myMap.length==0) true else false
  def keys:List[T] = for((key,value)<-myMap) yield {key}
  def values:List[M] = for((key,value)<-myMap) yield {value}
 }
}
def myTest {
 val myMap1 = MyMap((1,"Sandeep"),(2,"Praveen"),(3,"Vikas"),(4,"Suresh"))
 println(myMap1.get(3)) // Getting the value with key 3
 println(myMap1.keys) // Displaying a list of all keys
 println(myMap1.values) // Displaying a list of all values

 val myMap2 = myMap1+(5,"Pranay") // Add a key value pair to our custom Map(MyMap)

 println(myMap2.keys) // Displaying the list of keys of our map including '5' added in previous line
 println(myMap2.values)
}
myTest

//Output
Vikas
List(1, 2, 3, 4)
List(Sandeep, Praveen, Vikas, Suresh)
true
List(5, 1, 2, 3, 4)
List(Pranay, Sandeep, Praveen, Vikas, Suresh)

Explanation:

We have a predefined Map definition under the scala.predef object. Using similar methods present in the Map object we can come up with our own definition of the Map.

The underlying data structure we will be using is a List, therefore the results will all be in the form of lists.

1) Define a trait with a preferred name (say MyMap) and define all the abstract methods which your custom map should expose. Make sure your map is typed so that we can create a map of any object type say MyMap[Any,Any].
2) Define an object (with the same name MyMap), this object is the companion object of all the concrete classes which mixes in with the trait MyMap.
3) Override the apply function in the object . The input parameters of the apply function will be a sequence of Tuple2 's. x:Tuple2[K,V]* indicates patterns of the form (a,b),(c,d)(e,f) (where every alphabet represents any object in scala, Any)
4) Write a class inside the MyMap object which will be a concrete implementation of the trait MyMap. Lets say the concrete class is MyMapImpl which takes arguments of type List[Tuple2[K,V]] which means it a list of Tuple2's of type[K,V] which are key & value pairs. We should make sure we represent the variable of this type is a var and not a val.
5) Implement the methods in the MapTrait. One of the method here needs special attention. The "+" operator is now an overloaded method which is used to add a mapping entry into the custom map. This operator takes the Tuple as an input and return an object of the for MyMapImpl which also includes the newly added mapping.

6) Once the map is ready, write a test method (say myTest) and test the functionality of the methods you just implemented.