Scala - patterny - odwracanie listy

Ćwiczę Scalę i robię prosty przykład na odwrócenie listy liczb, logika jest prosta:

• odwrócenie pustej listy -> pusta lista
• odwrócenie listy: odwrócenie ogona listy i dodanie głowy

Wykombinowałem w ten sposób:

def reverse(arr : List[Int]) : List[Int] =  {
    arr match {
      case Nil => Nil
      case (head:Int) :: (tail:List[Int]) => reverse(tail) ++ List[Int](head)
    }
  }

Czy to jest zgodne z "duchem Scali"? Chodzi mi tu o 2 rzeczy:

• składnię dla wzorców, może się to da inaczej/krócej/bardziej przejrzyście (czy ten match nie może być piętro wyżej?)
• czy Skala radzi sobie z tą rekurencją, czy tak się nie robi? (wiem, że istnieje iteracyjne reverse)

1. niezgodne z duchem scali jest List[Int]. Skoro nigdzie, przy odrwacaniu, nie korzystasz z tego, że elementy to Int - to powinieneś napisać generyczne List[A]
2. Co do rekursji, scala sobie czasem radzi. Możesz metodę adnotować @tailrec, żeby sprawdzić czy kompilator dał radę. Z tego co kojarzę to w tym prezypadku chyba głupek nie da rady :-) - potrzebna jest lekka przeróbka (ale mogę się mylić - nie bawię się tym za czesto).

Dzięki @jarekr000000, generyki jeszcze przede mną ;-) Co do rekurencji ogonowej, to gdzieś mi się w oczy rzuciło, że na JVM nie ma co liczyć na cuda ze względu na implementację security (mowa o wersji Sun/Oracle; może to zmienili w najnowszej wersji, nie wiem), która bazuje na zliczaniu ramek stosu, sprawdzaniu kto wywołuje, czy ma do tego prawo etc.

Jeszcze kilka rzeczy możesz wyrzucić - klamry, typy wewnątrz funkcji itp.

def reverse[A](arr : List[A]) : List[A] = arr match {
      case Nil => Nil
      case head::tail => reverse(tail) ++ List(head)
    }

Przy okazji wersja z rekursją ogonową jest do zrobienia, jak wprowadzisz drugą funkcję z dodatkowym argumentem (akumulatorem, który zbiera rezultat). I na tej funkcji robi się rekursje.
Jest to dość standardowy sposób - podobnie robi się ogonowego fibonacciego. W sieci są przykłady,

Tutaj rekurencji ogonowej nie ma, bo w wyrażeniu: reverse(tail) ++ List[Int](head) ostatnią operają jest złączanie list, a nie wywoływanie metody reverse. Jest rekurencja, ale nieogonowa.

Odwracanie z rekurencją ogonową wyglądałoby mniej więcej tak:

def reverse[A](list: List[A]): List[A] = {
  @tailrec
  def go(rest: List[A], result: List[A]): List[A] = {
    rest match {
      case head :: tail => go(tail, head :: result)
      case Nil => result
    }
  }
  go(list, Nil)
}

Ta wersja ma złożoność liniową, a wersje wcześniejsze podane tutaj mają złożoność kwadratową. Dzieje się tak dlatego, że złączanie dwóch list ma złożoność wprost proporcjonalną do wielkości pierwszej listy.

Więcej informacji o trwałych strukturach danych jest tutaj:
https://en.wikipedia.org/wiki/Persistent_data_structure
http://www.vavr.io/vavr-docs/
https://medium.com/@dtinth/immutable-js-persistent-data-structures-and-structural-sharing-6d163fbd73d2

Implementacja @tailrec w Scali polega na tym, że kompilator w czasie kompilacji zamienia rekurencję ogonową na pętlę. Aby dało się to zrobić metoda musi być finalna. Rekurencja w funkcji musi też polegać na wywoływaniu samej siebie - nie jest obsługiwana zamiana wzajemnej rekurencji ogonowej (np gdzie metoda a wywołuje na końcu metodę b, a metoda b wywołuje na końcu metodę a) na pętlę.

Uja się znam na scali, ale bym tak napisał:

  def reverse[T](xs: List[T]): List[T] = {
    @tailrec def reverseVisitor(xs: List[T], revXs: List[T]): List[T] = {
      if (xs.isEmpty) return revXs
      return reverseVisitor(xs.tail, xs.head :: revXs)
    }
    return reverseVisitor(xs, Nil);
  }

Edit: Wibowit był szybszy.

Jest jeszcze całkiem sensowna alternatywa na foldzie:

def reverse[A](list: List[A]): List[A] = list.foldLeft(List[A]()) { (acc, el) => el :: acc }

Nie znam Scali więc się wypowiem.
Wygląda na to że funkcja biblioteczna nie wymaga rekurencji:
https://stackoverflow.com/a/7282968

Funkcja biblioteczna nie ma czysto funkcyjnej implementacji, ale ma czysto funkcyjny interfejs, którego nie łamie. Jest to popularny wzorzec lokalnej mutowalności, gdzie efekty uboczne nie są obserwowalne spoza funkcji, a co za tym idzie można zastosować wobec jej (metody) użycia takie samo rozumowanie jak wobec funkcji z czysto funkcyjną implementacją. Lokalna mutowalność jest użyta w celach wydajnościowych (może chodzić o wydajność zarówno wykonania, jak i kompilacji).