Общий, безопасный по типу способ сгладить произвольно вложенные коллекции в Scala?

Иногда я занимаю некоторое время, чтобы играть с Scala, чей набор функций обращается ко мне, несмотря на невозможность использовать его в моей собственной работе (пока). Для ударов я решил попробовать первые несколько 99 Haskell Problems самым общим способом - использовать и возвращать любую подходящую коллекцию. Первые несколько вопросов были слишком сложными, но я обнаружил, что я полностью оштрафован на flatten. Я просто не могу понять, как набрать такую вещь.

Чтобы быть конкретным о моем вопросе: возможно ли написать безопасную для типа функцию, которая выравнивает произвольно-вложенные SeqLike s? Итак, скажем,

flatten(List(Array(List(1, 2, 3), List(4, 5, 6)), Array(List(7, 8, 9), List(10, 11, 12))))

вернет

List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12): List[Int]

? Обратите внимание, что это не тот же вопрос, что и в наборах задач Haskell и Scala; Я пытаюсь написать функцию, которая выравнивает не гетерогенные списки, а скорее однородные, но вложенные последовательности.

Поиск в Интернете Я нашел перевод в Scala этого вопроса, но он работает и возвращает List [Any]. Правильно ли, что для этого потребуется какая-то рекурсия типа? Или я делаю это сложнее, чем это?

Ответ 1

В Scala 2.10.0-M7 работает следующее. Вам нужно будет добавить дополнительные случаи для поддержки Array и, возможно, уточнить его, чтобы иметь более конкретные типы выходных коллекций, но я думаю, что все это можно сделать, начиная с этого момента:

sealed trait InnerMost {
  implicit def innerSeq[A]: CanFlatten[Seq[A]] { type Elem = A } =
    new CanFlatten[Seq[A]] {
      type Elem = A
      def flatten(seq: Seq[A]): Seq[A] = seq
    }
}
object CanFlatten extends InnerMost {
  implicit def nestedSeq[A](implicit inner: CanFlatten[A]) 
  : CanFlatten[Seq[A]] { type Elem = inner.Elem } =
    new CanFlatten[Seq[A]] {
      type Elem = inner.Elem
      def flatten(seq: Seq[A]): Seq[inner.Elem] =
        seq.flatMap(a => inner.flatten(a))
    }
}
sealed trait CanFlatten[-A] {
  type Elem
  def flatten(seq: A): Seq[Elem]
}

implicit final class FlattenOp[A](val seq: A)(implicit val can: CanFlatten[A]) {
  def flattenAll: Seq[can.Elem] = can.flatten(seq)
}

// test        
assert(List(1, 2, 3).flattenAll == Seq(1, 2, 3))
assert(List(Seq(List(1, 2, 3), List(4, 5, 6)), Seq(List(7, 8, 9),
                List(10, 11, 12))).flattenAll == (1 to 12).toSeq)

Ответ 2

Кажется, что правильная вещь - просто позвонить .flatten правильное количество раз:

scala> val x = List(Array(List(1, 2, 3), List(4, 5, 6)), Array(List(7, 8, 9), List(10, 11, 12)))
x: List[Array[List[Int]]] = List(Array(List(1, 2, 3), List(4, 5, 6)), Array(List(7, 8, 9), List(10, 11, 12)))

scala> x.flatten.flatten
res0: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)

Так как набирается Scala, вы всегда знаете заранее, насколько глубока вложенность для конкретной переменной. Поскольку вы знаете это заранее, не так много значения при обработке произвольной структуры, как если бы вы были не уверены в том, сколько раз требуется .flatten.

Ответ 3

Вы сталкиваетесь с теми же проблемами, которые они описывают в Haskell solution: в Scala нет гетерогенного List. К счастью, вы можете следовать точно так же, как они идут в решении Haskell.

Определите тип данных, который может быть вложен:

sealed trait NestedList[A]
case class Elem[A](a: A) extends NestedList[A]
case class AList[A](a: List[NestedList[A]]) extends NestedList[A]

А затем напишите общую функцию сглаживания для этого типа:

def flatten[A](l: NestedList[A]): List[A] = l match {
  case Elem(x) => List(x)
  case AList(x :: xs) => flatten(x) ::: flatten(AList(xs))
  case AList(Nil) => Nil
}

или даже

def flatten[A](l: NestedList[A]): List[A] = l match {
  case Elem(x) => List(x)
  case AList(x) => x.flatMap(flatten)
}

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

flatten(AList(Elem(1) :: Elem(2) :: AList(Elem(3) :: Nil) :: Nil))

Конечно, мы могли бы также добавить это как метод непосредственно к признаку NestedList.