Как создать функцию, которая бы делала плоский List из сколь угодно глубоко вложенных списков? - PullRequest
Новая
       12

Как создать функцию, которая бы делала плоский List из сколь угодно глубоко вложенных списков?

6 голосов
/ 28 апреля 2019

Можно ли написать в scala функцию, которая бы взяла список произвольно глубоко вложенных списков и рекурсивно преобразовала его в плоский список?Например: 

flatten(List(List(1), List(List(2), 3), 4))

должен вернуть 

List(1,2,3,4)

Я сделал несколько попыток с shapeless, но без эффекта: 

object flatten extends (List ~> List) {
    def apply[T](s: List[T]) = s.map {
       case l: List[T] => apply(s)
       case x => x
    }
}

Это дает мне:

несоответствие типов

найдено: Список [Любой]

обязательно: Список [T]

Было бы также здорово, если бы он мог вычестьправильный тип (в случае примера List[Int], а не List[Any])

Ответы [ 2 ]

8 голосов
/ 28 апреля 2019

Дело в том, что вы не получаете List[T] на входе, а List[Any], где Any - это смесь T и List[Any].

Таким образом, если вы знаете тип конечных элементов, вы могли бы потенциально использовать параметр типа T для его представления и элементов плоской карты путем рекурсивного сопоставления с шаблоном либо T, либо 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)
2 голосов
/ 29 апреля 2019

Ваш желаемый flatten по сути не типизирован. Вы помещаете элементы (скажем, у них есть тип E), их списки (List[E]), списки там из (List[List[E]]) и т. Д. В один список, который должен иметь тип List[Any] потому что его элементы не имеют ничего общего. Shapeless - это все о наличии описательных типов и трансформации между ними, поэтому для вас это ничего не значит. Кроме того, посмотрите на определение вашей функции: 

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
}

Итак, s - это List[T], а s.map дает вам каждый из T по очереди. Затем вы используете type- case и в одном из плеч проверяете, действительно ли l: T является l: List[T]. То есть вы проверяете, что List[T] <: T. Это странно и означает, что ваша функция неверна.

Если вы действительно хотите использовать Shapeless, точно опишите ваш ввод с типами. Мы хотим этот интерфейс для flatten[T]:

  • Если он получает t: T, то он возвращает List(t): List[T].
  • Если он получает l: List[X], где X является действительным входным значением для flatten[T], он выравнивает каждый X, а затем выводит объединение результатов как единое целое, большое List[T].
  • Если он получает h: H, где H <: HList, где каждый элемент H является действительным входным значением для flatten[T], каждый элемент сглаживается и результаты объединяются в один List[T].

Это его реализация: 

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
}

При использовании: 

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)

Альтернатива - просто использовать правильную структуру данных. В этом контексте правильная структура называется свободной монадой на List, также известной как розовое дерево: 

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) }

Использование: 

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