Κλήση παραμέτρων στην SML & Πολυπλοκότητα

Question

Θα ήθελα να ρωτήσω με αφορμή την βελτιωμένη εκδοχή της reverse που είδαμε στη τελευταία διάλεξη:

fun reverse xs =
  let
    fun rev (nil, z) = z
      | rev (y::ys, z) = rev (ys, y::z)
  in
    rev (xs, nil)
  end

Οι παράμετροι πως γίνονται called από τις συναρτήσεις;
Ρωτάω διότι αν γινόντουσαν called by value, πρακτικά δεν θα είχαμε αντιγραφή $n$ συνολικά στοιχείων (εντός των δυο λιστών στο tuple) σε κάθε αναδρομική κλήση της rev, άρα και πάλι πολυπλοκότητα τάξης $O(n^2)$;

Answer 1

Technically, στην ML το πέρασμα των παραμέτρων γίνεται by value.

Όμως, σε μια αγνή συναρτησιακή γλώσσα, ο τρόπος περάσματος παραμέτρων δεν έχει μεγάλη σημασία γιατί η καλούμενη συνάρτηση δεν μπορεί να αλλάξει την τιμή ούτε της τυπικής ούτε της πραγματικής παραμέτρου. Αυτό σημαίνει ότι οι υλοποιήσεις της ML δε χρειάζεται να αντιγράφουν λίστες (ή άλλου είδους δεδομένα που είναι μεγάλου μεγέθους) όταν τα περνούν ως παραμέτρους. Το πέρασμα μιας λίστας σε μια συνάρτηση δεν προκαλεί αντιγραφή της λίστας --- η υλοποίηση απλά περνά ένα δείκτη στο πρώτο στοιχείο.

Comments

Ευχαριστώ πολύ για την απάντηση