Η συνάρτηση List.last για τη λίστα στην ML

Question

Στο μάθημα (αν θυμάμαι καλά) είχαμε αναφέρει ότι στην ML δεν είναι εφικτό να πάρεις κατ' ευθείαν το τελευταίο στοιχείο μιας λίστας, σε αντίθεση με το πρώτο (hd x). Εδώ βρήκα ότι υπάρχει η συνάρτηση val last : 'a list -> 'a (List.last), που δίνει πράγματι το τελευταίο στοιχείο. Δυστυχώς, ο ιστότοπος δεν αναφέρει κάτι για την πολυπλοκότητά της. Η ερώτηση μου, λοιπόν, είναι εάν έχει καλή πολυπλοκότητα η List.last, δηλαδή $Ο(1)$ κι όχι $Ο(n)$ (=κάθε φορά που την καλώ να διατρέχει όλη τη λίστα μέχρι να φτάσει στο τέλος).

Comments

Η απάντηση είναι από κάτω. Αφήνω εδώ και το πώς υλοποιεί η smlnj την last :

fun last [] = raise Empty
      | last [x] = x
      | last (_::r) = last r

Answer 1

Αυτό ακριβώς κάνει και έχει πολυπλοκότητα $O(n)$. Οι λίστες της ML είναι κατ' ουσίαν απλά συνδεδεμένες λίστες και δεν υπάρχει αποδοτικός τρόπος να πάρεις το τελευταίο στοιχείο τους.