Scala - рекурсия анонимной функции

Question

Я работаю с материалами Scala Labs и создаю функцию, которая, в конце концов, возвращает что-то вроде этого: tails(List(1,2,3,4)) = List(List(1,2,3,4), List(2,3,4), List(3,4), List(4), List())

Я получил эту работу, используя две функции ииспользование некоторой рекурсии для второго.

def tails[T](l: List[T]): List[List[T]] = {
    if ( l.length > 1 )trailUtil(List() ::: List(l))
    else List() ::: List(l);
}

def trailUtil[T](l:List[List[T]]) : List[List[T]] = {
    if ( l.last.length == 0)l
    else trailUtil(l :+ l.last.init);
}

Все это хорошо, но меня беспокоит, что мне нужны две функции для этого.Я попытался переключиться: trailUtil(List() ::: List(l)) для анонимной функции, но я получил эту ошибку type mismatch; found :List[List[T]] required:Int из IDE.

val ret : List[List[T]] = (ll:List[List[T]]) => {
    if ( ll.last.length == 0) ll else ret(ll :+ ll.last.init)
}
ret(List() ::: List(1))

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

(Я смотрел на это ТАК сообщение, но другой тип просто не работает для меня):

Answer 1

Что по этому поводу:

def tails[T](l: List[T]): List[List[T]] = 
  l match {
    case h :: tail => l :: tails(tail)
    case Nil => List(Nil)
  }

И чуть менее идиоматическая версия:

def tails[T](input: List[T]): List[List[T]] =
    if(input.isEmpty)
        List(List())
    else
        input :: tails(input.tail)

Кстати, старайтесь избегать List.length, он запускается за O (n) раз.

ОБНОВЛЕНИЕ: как предложено тенши , хвостово-рекурсивное решение:

@tailrec def tails[T](l: List[T], init: List[List[T]] = Nil): List[List[T]] =
    l match {
        case h :: tail => tails(tail, l :: init)
        case Nil => init
    }

Answer 2

Вы действительно можете определить def внутри другого def. Это позволяет определить функцию, которая на самом деле имеет имя, на которое можно ссылаться и использовать для рекурсии. Вот как можно реализовать tails:

def tails[T](l: List[T]) = {
    @annotation.tailrec
    def ret(ll: List[List[T]]): List[List[T]] =
        if (ll.last.isEmpty) ll 
        else ret(ll :+ ll.last.tail)

    ret(l :: Nil)
}

Эта реализация также является хвостовой рекурсивной. Я добавил @annotation.tailrec аннотацию, чтобы убедиться, что это действительно так (код не будет компилироваться, если это не так).

---

Вы также можете использовать встроенную функцию tails (см. ScalaDoc ):

List(1,2,3,4).tails.toList

tails возвращает Iterator, поэтому вам нужно преобразовать его в список (как я), если хотите. Кроме того, результат будет содержать один лишний пробел в конце (в моем примере результат будет List(List(1, 2, 3, 4), List(2, 3, 4), List(3, 4), List(4), List())), поэтому вам нужно разобраться с ним.

Answer 3

Вы также можете использовать складывание:

val l = List(1,2,3,4)

l.foldLeft(List[List[Int]](l))(  (outerList,element) => {
    println(outerList)
    outerList.head.tail :: outerList
})

Первый список параметров - это ваше начальное значение / аккумулятор. Вторая функция - модификатор. Как правило, он изменяет начальное значение, которое затем передается каждому элементу в списке. Я включил println, чтобы вы могли видеть аккумулятор, поскольку список повторяется.

Answer 4

То, что вы делаете неправильно, это:

val ret : List[List[T]]

Итак, ret - это список из списка T. Затем вы делаете это:

ret(ll :+ ll.last.init)

Это означает, что вы вызываете метод apply в списке списка T. Метод apply для списков принимает параметр Int и возвращает элемент с этим индексом. Например:

scala> List("first", "second", "third")(2)
res0: java.lang.String = third

Полагаю, вы хотели написать val ret: List[List[T]] => List[List[T]], то есть функцию, которая принимает List[List[T]] и возвращает List[List[T]]. Тогда у вас будут другие проблемы, потому что val ссылается на себя в своем определении. Чтобы обойти это, вы можете заменить его на lazy val:

def tails[T](l: List[T]): List[List[T]] = {
  lazy val ret : List[List[T]] => List[List[T]] = { (ll:List[List[T]]) => 
    if ( ll.last.length == 0) ll 
    else ret(ll :+ ll.last.init)
  }
  if ( l.length > 1 )ret(List() ::: List(l))
  else List() ::: List(l);
}

Но, конечно, простое решение - поместить один def внутрь другого, как предложено тенши .