Permutations on a List

Perms.scala

///////////////////////////////////////////////////////////
/// may seem more complicated thatn it realy is for:
///    1- concat behaves diff in haskell from Scala, so I need to modify it a bit
///    2- There is no concatMap in Scala Collection API, there is one in Scala Cats, but didnt want to use cats for this assignment
//////////////////////////////////////////////////////////////
/// About the solution:
/// The general notion is to extend the `inserts` function to the entire collection where `inserts` inserts all the way an elelemt may be inserted in a colletion
////////////////////////////////////////////////////////////

object Perms {
  def mmap[T, U](f: T => U)(xs: List[T]): List[U] = xs map f // redefine scala map so we can use it in composition

  def inserts[T](x: T)(xs: List[T]): List[List[T]] = xs match {
    case Nil      => List(List(x))
    case (h :: t) => (x :: h :: t) :: inserts(x)(t).map(x => h :: x)
  }

  def _concat[T](xss: List[List[T]]): List[T] =
    xss.foldRight(List[T]())((c, a) => c ++ a)

  def concatMap[T, U](f: T => List[U])(ts: List[T]): List[U] =
    (mmap(f) _ andThen _concat)(ts)

  def perm[T](xs: List[T]): List[List[T]] =
    xs.foldRight(List(List[T]()))((c, a) => concatMap(inserts(c))(a))
}
//////////////////////////// corresponding unit tests//////////////////

class PermsSpec extends Specification {
  def is = s2"""
    Perms specs are
       should give the correct inserts $e1
       should give the correct perms $e2
"""
  def e1 = {
    val computed = inserts(0)(List(1, 2, 3))
    val expected = List(
      List(0, 1, 2, 3),
      List(1, 0, 2, 3),
      List(1, 2, 0, 3),
      List(1, 2, 3, 0)
    )
    computed === expected
  }

  def e2 = {
    val computed = perm(List(1, 2, 3))
    val expected = List(
      List(1, 2, 3),
      List(2, 1, 3),
      List(2, 3, 1),
      List(1, 3, 2),
      List(3, 1, 2),
      List(3, 2, 1)
    )
    computed === expected

  }

}