Сгладить произвольно вложенный список в Scala

Извините, но этот код очень сложный. Я попытался упростить его и получил это решение:

    scala> :paste
    // Entering paste mode (ctrl-D to finish)

        def flatten(l : List[_]) : List[_] = l flatMap {
          case l1 : List[_] => flatten(l1)
          case otherwise => List(otherwise)
        }


    // Exiting paste mode, now interpreting.

    flatten: (l: List[_])List[_]

    scala> flatten(List(1,2,3))
    res3: List[Any] = List(1, 2, 3)

    scala> flatten(List(1,2,List(3,4)))
    res4: List[Any] = List(1, 2, 3, 4)

    scala> flatten(List(List(1,List(2),3),4,List(4,5)))
    res5: List[Any] = List(1, 2, 3, 4, 4, 5)

После исправления кода (добавления вызова iflat) я сделал следующие рефакторинги:

1. Удален внутренний метод
2. Использовал встроенный flatMap для итерации (и, следовательно, мог исключить или упростить некоторые выражения case)
3. Заменены instanceOf на защиту типа.

Я думаю, что более простым решением было бы использование библиотеки shapeless (подсказка: ищите "шаблонную" часть).

Я не получаю ту же ошибку, что и вы в отношении iflatten(h,ret). Я получаю ошибку found : Unit; required : List[?], но это относится к тому факту, что вы не вызываете ifflatten в самом flatten: после его определения вам нужно вызвать функцию в конце определения flatten.

def flatten(l: List[_]): List[_] = {
  def iflatten(l: List[_], ret: List[_]): List[_] = l match {
    case Nil => ret
    case (h:List[_]) :: tail => iflatten(tail,iflatten(h,ret))
    case h :: tail => iflatten(tail,h::ret)
  }
  iflatten(l,List()).reverse
}

Что касается самого кода, вы можете (и должны) проверять типы при сопоставлении. Также обратите внимание, что case h :: Nil соответствует только списку длиной 1.

Что касается алгоритма, то нужно вызывать iflatten внутри себя (вот тут и происходит произвольная вложенность).

Я думаю, вам просто не хватает актерского состава.

if( h.isInstanceOf[List[_]]) { iflatten(h.asInstanceOf[List[_]], ret) }

В качестве альтернативы: было бы красивее с сопоставлением с образцом.

h match {
  case hList: List[_] => 
    iflatten(hList, ret)
  case _ => 
    l.head :: ret
    iflatten(l.tail, ret)
}

(предостережение: это только что пришло мне в голову, и я ничего не пропускал через компилятор)

редактировать - решение Марта по объединению этого с предыдущим соответствием шаблону выглядит лучше, чем мое.

На самом деле, я подозреваю, что проблема заключается в том, что вы определяете внутренний метод iflatten, но никогда не вызываете его, так что внешний метод flatten ничего не возвращает (т.е. по умолчанию возвращается тип Unit, конфликтующий с заявленным типом возврата списка[_]).

Попробуйте добавить следующее в качестве последней строки внешнего метода flatten:

iflatten(l, Nil)

Помимо этого, у вас есть различные другие проблемы с вашим кодом, такие как не обработка всех случаев совпадения: вы обрабатываете случай списка с одним элементом — h :: Nil — но не с несколькими элементами. Вероятно, вы имели в виду что-то вроде h :: theRest, а затем где-то использовали theRest - возможно, в качестве параметра ret для рекурсивного вызова.

Вы также используете проверку h.isInstanceOf[List[_]] (как правило, любое использование isInstanceOf является плохим запахом кода в scala), но затем попробуйте рекурсивно передать h в iflatten без приведения его к List[_] (например, как в ответе @ChristopherMartin, хотя использование asInstanceOf еще больше запах кода). Ответ @Marth дает хороший пример того, как избежать этих явных проверок типов.

Я думаю, что это то, в чем хороша библиотека Shapeless.

https://github.com/milessabin/shapeless/blob/master/examples/src/main/scala/shapeless/examples/flatten.scala