Here is a another solution using fold that has the similar performance characteristics. One difference is that it doenst have to compute the linear List Length

  def inserts[A](x: A): List[A] => List[List[A]] =
    ls =>
      ls match {
        case Nil       => List(List(x))
        case (y :: ys) => (x :: y :: ys) :: (inserts(x)(ys)).map(z => y :: z)
      }
  def permutations[A](ls: List[A]): List[List[A]] =
    ls.foldRight(List(List[A]()))((x, xss) => xss.flatMap(inserts(x)))

Here is a another solution using fold that has the similar performance characteristics. One difference is that it doesn't have to compute the linear List Length

  def inserts[A](x: A): List[A] => List[List[A]] =
    ls =>
      ls match {
        case Nil       => List(List(x))
        case (y :: ys) => (x :: y :: ys) :: (inserts(x)(ys)).map( y :: _)
      }
  def permutations[A](ls: List[A]): List[List[A]] =
    ls.foldRight(List(List[A]()))((x, xss) => xss.flatMap(inserts(x)))