Rückgabe des letzten Elements einer Liste in Haskell mit Rekursion

Question

Wie bekomme ich das letzte Element in einer Liste in Haskell? Ich habe etwas Code unten geschrieben:

lastList :: List a -> a 
lastList lst = 
    case lst of 
     Cons x xs -> lastList xs 
     Cons _ xs -> lastList xs 
     Empty -> error "lastList of empty list" 

Wie mache ich es ohne Verwendung der eingebauten Funktionen?

Answer 1

Sie müssen nur überprüfen, wenn ein Element Nachteile mit einem Empty ist:

lastList :: List a -> a 
lastList lst = 
    case lst of 
     Cons x Empty -> x 
     Cons _ xs -> lastList xs 
     Empty  -> error "lastList of empty list" 

Answer 2

Die Cons ist ein Lisp wie Liste, in der eine Liste als eine verknüpfte Liste dargestellt wird. Jeder Cons h t ist ein Knoten, bei dem sich h auf den Kopf dieses Knotens (ein Element) bezieht, ein t auf den Endabschnitt der Liste: der Rest. Außerdem wird hier das Ende der Liste (die leere Liste) mit Empty dargestellt.

Das heißt also, dass eine Liste mit einem Elementx als Cons x Empty dargestellt ist (dies ist äquivalent zu [x]). Falls wir auf dieses Problem stoßen, müssen wir x zurückgeben, da das letzte Element einer Liste mit einem Element dieses Element ist.

Also ist die Frage, was zu tun ist, wenn wir eine Cons h t haben, wo t nicht Empty ist. In diesem Fall sieht die Liste so aus wie [x1,x2,...]. Nun ist das letzte Element dieser Liste das selbe wie das letzte Element der [x2,x3,...]-Liste, so dass wir die Rekursion auf dem Tail verwenden können.

Schließlich müssen wir einen Weg finden, um den Fall zu lösen, wo wir der Funktion eine leere Liste zur Verfügung stellen. In diesem Fall bieten wir wahrscheinlich besser eine error.

So können wir implementieren es mögen:

lastList :: List a -> a 
lastList (Cons h Empty) = h 
lastList (Cons _ t) = lastList t 
lastList Empty = error "An empty list has no lastElement"