How to create function which would make flat List from arbitrarily deeply nested lists?

The thing is, you don't receive a List[T] in input, but a List[Any] where Any is a mix of T and List[Any].

So if you know the type of leaf elements, you could potentially use a type parameter T to represent it and flatmap elements by recursively pattern matching on either T or List[Any]:

import scala.reflect.ClassTag

def flatten[T: ClassTag](list: List[Any]): List[T] =
  list.flatMap {
    case x: T => List(x)
    case sub: List[Any] => flatten[T](sub)
  }

flatten[Int](List(List(1), List(List(2), 3), 4))
// List[Int] = List(1, 2, 3, 4)

Your desired flatten is intrinsically untyped. You are putting elements (let's say they have type E), lists thereof (List[E]), lists thereof (List[List[E]]), etc. into one list, which must have type List[Any], because its elements don't have anything in common. Shapeless is all about having descriptive types and transforming between them, so it has nothing for you. Furthermore, look at your function's definition:

def apply[T](s: List[T]) = s.flatMap { // should be flatMap, conceptually
   case l: List[T] => apply(l) // should be l, conceptually
   case x => List(x) // should be singleton list, conceptually
}

So, s is a List[T], and s.map is giving you each of the Ts in turn. You then use a type-case, and, in one of the arms, you check whether l: T is actually a l: List[T]. That is, you check that List[T] <: T. This is weird, and signifies that your function is incorrect.

If you really want to use Shapeless, accurately describe your input with types. We want this interface for flatten[T]:

• If it receives a t: T, then it returns List(t): List[T].
• If it receives a l: List[X], where X is a valid input to flatten[T], it flattens each X, then outputs the concatenation of the results as one, big List[T].
• If it receives a h: H where H <: HList, where each element of H is a valid input to flatten[T], each element is flattened and the results are concatenated into one List[T].

This is its implementation:

object flatten extends Poly1 {
  implicit def caseT[T] = at[T](List(_))
  implicit def caseList[T, X](implicit e: Case.Aux[X, List[T]])
    = at[List[X]](_.flatMap(e))
  implicit def caseHNil[T, N <: HNil] = at[N](_ => List[T]())
  implicit def caseHCons[T, H, R <: HList](implicit hf: Case.Aux[H, List[T]],
                                                    rf: Case.Aux[R, List[T]])
    = at[H :: R] { case h :: r => hf(h) ++ rf(r) }

  final class Specialized[T] {
    def apply[X](x: X)(implicit c: Case.Aux[X, List[T]]): List[T] = c(x)
  }
  def apply[T]: Specialized[T] = new Specialized
}

With usage:

scala> flatten[Int]((1 :: HNil) :: ((2 :: HNil) :: 3 :: HNil) :: 4 :: HNil)
List(1, 2, 3, 4)
scala> flatten[Int](1 :: List(2, 3) :: List(List(4, 5), List(), List(6, 7)) :: List(8 :: List(9, 10) :: HNil, 11 :: List(12, 13, 14) :: HNil) :: HNil)
List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)

The alternative is to simply use the correct data structure. In this context, the correct structure is called the free monad on List, also known as the rose tree:

sealed trait Free[M[+_], +A] {
  def flatten(implicit M: Monad[M]): M[A]
}
case class Pure[M[+_], +A](x: A) extends Free[M, A] {
  override def flatten(implicit M: Monad[M]) = M.pure(x)
}
case class Step[M[+_], +A](step: M[Free[M, A]]) extends Free[M, A] {
  override def flatten(implicit M: Monad[M]) = step.flatMap(_.flatten)
}
// for convenience
object Rose {
  type Rose[+A] = Free[List, A]
  type Leaf[+A] = Pure[List, A]
  type Branch[+A] = Step[List, A]
  object Leaf {
    def apply[A](x: A): Leaf[A] = Pure(x)
    def unapply[A](x: Leaf[A]): Some[A] = Some(x.x)
  }
  object Branch {
    def apply[A](xs: Rose[A]*): Branch[A] = Step(xs.toList)
    def unapplySeq[A](xs: Branch[A]): Some[List[Rose[A]]] = Some(xs.step)
  }
}
// specialized:
// sealed trait Rose[+A] { def flatten: List[A] }
// case class Leaf[+A](x: A) extends Rose[A] { override def flatten = List(x) }
// case class Branch[+A](x: List[Rose[A]]) extends Rose[A] { override def flatten = x.flatMap(_.flatten) }

Usage:

scala> Branch(Branch(Leaf(1)), Branch(Branch(Leaf(2)), Leaf(3)), Leaf(4)).flatten