Umkehr einer Liste (rekursiv)

[jbs]

inplace mit Vertauschen

Code: Alles auswählen

def reverse(seq, i=0):
    if i < len(seq)/2:
        seq[i],seq[-(i+1)] = seq[-(i+1)], seq[i]
        reverse(seq, i+1)

[Defnull]

Na jetzt ist es ja eh offen. Meine Lösung wäre gewesen:

Code: Alles auswählen

def stupidhomework(l):
  return l[-1:] + stupidhomework(l[0:-1]) if l else []

[EyDu]

Aber natürlich darf bei so etwas reduce nicht fehlen:

Code: Alles auswählen

reduce(lambda xs, x: [x]+xs, [1,2,3], [])

@Defnull: Deine ist quasi meine Lösung. Nur von der anderen Richtung und if/else statt einem and.

[cofi]

Na dann packen wir noch Scheme dazu

Code: Alles auswählen

(define (reverse alist)
    (foldl cons '() alist))

[Leonidas]

Ist die Frage wo dann eure Lösungen rekursiv sind. Und nein, ich lasse bei ``fold`` nicht gelten dass es ja rekursiv sein könnte

[EyDu]

Und nein, ich lasse bei ``fold`` nicht gelten dass es ja rekursiv sein könnte

Ich schon

[HWK]

Ganz abgesehen davon überschreibst du ein buildin. Böse!

Schlimmer noch: Er "löscht" die Ausgangsliste.

Code: Alles auswählen

>>> l
[0, 1, 2]
>>> reversed(l)
[2, 1, 0]
>>> l
[]

MfG
HWK

[HWK]

Und Haskell:

Code: Alles auswählen

reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

MfG
HWK

[DasIch]

Schlimmer noch: Er "löscht" die Ausgangsliste.

Das lässt sich ja dokumentieren.

[bords0]

Divide-and-conquer darf natürlich nicht fehlen!

Code: Alles auswählen

def f(a):
    if len(a) > 1:
        m = len(a) / 2
        return f(a[m:]) + f(a[:m])
    return a

[lunar]

Ocaml:

Code: Alles auswählen

let rec reverse = function
  | [] -> []
  | x :: xs -> (reverse xs) @ [x]

[jbs]

Das ist das was ich an so einem Thread mag!

[Defnull]

Divide-and-conquer darf natürlich nicht fehlen!

Code: Alles auswählen

def f(a):
    if len(a) > 1:
        m = len(a) / 2
        return f(a[m:]) + f(a[:m])
    return a

Die bisher coolste Lösung finde ich.

[numerix]

Divide-and-conquer darf natürlich nicht fehlen!

Code: Alles auswählen

def f(a):
    if len(a) > 1:
        m = len(a) / 2
        return f(a[m:]) + f(a[:m])
    return a

Die bisher coolste Lösung finde ich.

Ja, gefällt mir auch gut. Ließe sich auch so schreiben:

Code: Alles auswählen

f = lambda a: f(a[len(a)/2:])+f(a[:len(a)/2]) if len(a)>1 else a

[derdon]

Ocaml:

Code: Alles auswählen

let rec reverse = function
  | [] -> []
  | x :: xs -> (reverse xs) @ [x]

Danke für die Lösung. Ich war schon am verzweifeln, weil ich immer das hier versucht habe: [...]

Edit: Ich merke grade, dass meine Versuche noch viel schlimmer waren. Die behalte ich doch lieber für mich...

[Dackel]

Ich versuch mich gerade an Scala. Da kann ich auch mal was beisteuern:

Code: Alles auswählen

...
def reverse(l: List[Any]): List[Any] = l match {
    case List() => l
    case _ => reverse(l.tail) ::: l.head
  }
...

[Leonidas]

Hier eine (etwas gecheatete) Lösung in Factor. Entspricht quasi 1:1 der Scheme-Lösung.

Code: Alles auswählen

USING: sequences syntax ;
IN: reverser

: reverse ( seq -- newseq ) { } [ prefix ] reduce ;

(Ist schon erstaunlich wie kurz Factor-Code sein kann)

Der Vollständigkeit halber hier der Code der von Factor genutzt wird (self-hosting hat schon Vorteile, zweifellos):

Code: Alles auswählen

USING: kernel ;
IN: sequences
: reverse ( seq -- newseq )
    [
        dup [ length ] keep new-sequence [ 0 swap copy ] keep
        reverse!
    ] keep like ;

Ist allerdings nichtmal ansatzweise rekursiv.

[BlackJack]

Io fehlt noch:

Code: Alles auswählen

List myReverse := method(
    if(self isEmpty, List clone, self slice(0, -1) myReverse prepend(self last))
)