foldMap is equivalent to scala.List

FList.scala

trait Semigroup[A] {
  def op(a1: A, a2: A): A
}

trait Monoid[A] extends Semigroup[A] {
  def id: A
}

object Monoid {
  implicit def ListMonoid[A]: Monoid[List[A]] =
    new Monoid[List[A]] {
      def op(a1: List[A], a2: List[A]) =
        a1 ::: a2

      def id =
        Nil
    }
}

// foldMap is isomorphic to scala.List
trait FMList[A] {
  def foldMap[B](f: A => B)(implicit M: Monoid[B]): B

  def ::(a: A): FMList[A] =
    new FMList[A] {
      def foldMap[B](f: A => B)(implicit M: Monoid[B]) =
        M.op(f(a), FMList.this.foldMap(f))
    }

  def +:(a: A): FMList[A] =
    new FMList[A] {
      def foldMap[B](f: A => B)(implicit M: Monoid[B]) =
        M.op(FMList.this.foldMap(f), f(a))
    }

  def :::(a: FMList[A]): FMList[A] =
    new FMList[A] {
      def foldMap[B](f: A => B)(implicit M: Monoid[B]) =
        M.op(a.foldMap(f), FMList.this.foldMap(f))
    }    

  def filter(p: A => Boolean): FMList[A] =
    new FMList[A] {
      def foldMap[B](f: A => B)(implicit M: Monoid[B]) =
        FMList.this.foldMap(x => if(p(x)) f(x) else M.id)
    }

  def map[X](q: A => X): FMList[X] =
    new FMList[X] {
      def foldMap[B](f: X => B)(implicit M: Monoid[B]) =
        FMList.this.foldMap(f compose q)
    }    

  def flatMap[X](q: A => FMList[X]): FMList[X] =
    new FMList[X] {
      def foldMap[B](f: X => B)(implicit M: Monoid[B]) =
        FMList.this.foldMap(q(_) foldMap f)
    }

  def toScalaList: List[A] =
    foldMap(List(_))

  override def toString: String =
    "FM" + toScalaList.toString
}

object FMList {
  def nil[A]: FMList[A] = 
    new FMList[A] {
      def foldMap[B](f: A => B)(implicit M: Monoid[B]) =
        M.id
    }

  def single[A](a: A): FMList[A] = 
    new FMList[A] {
      def foldMap[B](f: A => B)(implicit M: Monoid[B]) =
        f(a)
    }

  def fromScalaList[A](a: List[A]): FMList[A] =
    a.foldRight[FMList[A]](nil)(_ :: _)
}

case class ~>[R, A](run: (A => R) => R) {
  def map[B](f: A => B): R ~> B =
    ~>(g => run(g compose f))

  def flatMap[B](f: A => (R ~> B)): R ~> B =
    ~>(g => run(f(_) run g))
}

object ~> {
  def pure[R, A](a: A): R ~> A =
    ~>(_(a))

  def constant[R, A](r: => R): R ~> A =
    ~>(_ => r)
}

// fold is isomorphic to scala.List
trait FList[A] {
  def fold[R](implicit M: Monoid[R]): R ~> A

  def ::(a: A): FList[A] =
    new FList[A] {
      def fold[R](implicit M: Monoid[R]) =
        ~>(f => M.op(f(a), FList.this.fold run f))
    }

  def +:(a: A): FList[A] =
    new FList[A] {
      def fold[R](implicit M: Monoid[R]) =
        ~>(f => M.op(FList.this.fold run f, f(a)))
    }

  def :::(a: FList[A]): FList[A] =
    new FList[A] {
      def fold[R](implicit M: Monoid[R]) =
        ~>(f => M.op(a.fold run f, FList.this.fold run f))
    } 

  def filter(p: A => Boolean): FList[A] =
    new FList[A] {
      def fold[R](implicit M: Monoid[R]) =
        ~>(f => FList.this.fold run (x => if(p(x)) f(x) else M.id))
    }

  def map[X](q: A => X): FList[X] =
    new FList[X] {
      def fold[R](implicit M: Monoid[R]) =
        ~>(f => FList.this.fold run (f compose q))
    }    

  def flatMap[X](q: A => FList[X]): FList[X] =
    new FList[X] {
      def fold[R](implicit M: Monoid[R]) =
        ~>(f => FList.this.fold run (q(_).fold run f))
    }  
    
  def toScalaList: List[A] =
    fold[List[A]].run(List(_))
    
  override def toString: String =
    "F" + toScalaList.toString
}

object FList {
  def nil[A]: FList[A] = 
    new FList[A] {
      def fold[R](implicit M: Monoid[R]) =
        ~>.constant(M.id)
    }

  def single[A](a: A): FList[A] = 
    new FList[A] {
      def fold[R](implicit M: Monoid[R]) =
        ~>(_(a))
    }

  def fromScalaList[A](a: List[A]): FList[A] =
    a.foldRight[FList[A]](nil)(_ :: _)
}

object Main {
  def step[A](a: A): A = {
    println(a)
    a
  }

  def main(args: Array[String]) {
    val flist0: FList[Int] = FList.nil
    val flist1 = 3 :: flist0    
    val flist2 = 1 :: 2 :: flist1
    val flist3 = flist2 map (_ * 2)
    val flist4 = flist3 ::: (40 :: 50 :: 60 :: FList.nil)
    val flist5 = flist4 filter (x => x / 10 % 2 == 0)
    val flist6 = flist5.flatMap(x => x :: x + 200 :: FList.nil)

    val fmlist0: FMList[Int] = FMList.nil
    val fmlist1 = 3 :: fmlist0    
    val fmlist2 = 1 :: 2 :: fmlist1
    val fmlist3 = fmlist2 map (_ * 2)
    val fmlist4 = fmlist3 ::: (40 :: 50 :: 60 :: FMList.nil)
    val fmlist5 = fmlist4 filter (x => x / 10 % 2 == 0)
    val fmlist6 = fmlist5.flatMap(x => x :: x + 200 :: FMList.nil)


    List(
      flist0
    , flist1
    , flist2
    , flist3
    , flist4
    , flist5
    , flist6
    , flist6.toScalaList

    , fmlist0
    , fmlist1
    , fmlist2
    , fmlist3
    , fmlist4
    , fmlist5
    , fmlist6
    , fmlist6.toScalaList
    ) foreach println
  }
}