MyList.scala

sealed trait MyList[+T] 
case object MyNil extends MyList[Nothing]
case class MyCons[+T](value: T, tail: MyList[T]) extends MyList[T]

object MyList {
  
  def empty[T]: MyList[T] = MyNil
  
  implicit class MyListOps[A](val self: MyList[A]) extends AnyVal {
    
    def foldLeft[B](i: B)(f: (B, A) => B): B = {
      def aux(s: B, xs: MyList[A]): B = xs match {
        case MyNil => s
        case MyCons(x, xs) => aux(f(s, x), xs)
      }
      aux(i, self)
    }
    
    def reverse: MyList[A] = self.foldLeft(MyList.empty[A])((acc, x) => x :: acc)
    
    def map[B](f: A => B): MyList[B] = self
      .foldLeft(MyList.empty[B])((acc, x) => f(x) :: acc)
      .reverse
      
    def flatMap[B](f: A => MyList[B]): MyList[B] = self
      .map(f)
      .foldLeft(MyList.empty[B])((acc, xs) => acc ++ xs)
      
    def ::(x: A): MyList[A] = MyCons(x, self)
    
    def :::(xs: MyList[A]): MyList[A] = xs
      .reverse
      .foldLeft(self)((acc, x) => x :: acc)
    
    def ++(xs: MyList[A]): MyList[A] = self ::: xs
  }
}