אתר ללימוד מקיף> פרק 10 - Alists and tables

פרק 10 - Alists and tables

רשימות מקושרות או כפי שהן מכונות - alists, הן צורות של רשימות ב-Scheme במבנה מיוחד. כל אלמנט ברשימה נחשב כרכיב 'cons', ה-'car' נקרא המפתח וה-'cdr' הוא ערך המשורשר עם המפתח הנ"ל.

לדוגמא:

((a . 1) (b . 2) (c . 3))

פרוצדורה הנקראת (assv k al) מוצאת את כל רכיבי ה-cons המקושרים עם מפתח k ברשימה המקושרת al. מפתחות הרשימות המקושרות השונות משווים עם ה-k הנתון באמצעות פרדיקט ההשוואה ?eqv. באופן כללי, בכל זאת נרצה פרדיקט אחר להשוואת מפתחות.
לדוגמא, אם המפתחות הם מחרוזות מסוג case-insensitive, הפרדיקט ?eqv אינו יעיל כ"כ.
כעת נרצה להגדיר מבנה הנקרא table שהוא רשימה מקושרת משופרת, המאפשר למשתמש להגדיר פרדיקטים על המפתחות שלו. השדות שלו הם: equ ו-alist.

(defstruct table (equ eqv?) (alist '()))

(פרדיקט ברירת המחדל הוא eqv? באשר לרשימה מקושרת רגילה כאשר הרשימה מאותחלת להיות ריקה).
נשתמש בפרוצדורה table-get כדי לקבל את הערך (בניגוד ל-cons cell) המשורשר עם מפתח נתון. table-get מקבלת table ומפתח כארגומנטים וערך ברירת מחדל אופציונלי שיוחזר במקרה שהמפתח לא נמצא ב-table.

(define table-get 
  (lambda (tbl k . d) 
    (let ((c (lassoc k (table.alist tbl) (table.equ tbl))))
      (cond (c (cdr c)) 
            ((pair? d) (car d))))))

הפרוצדורה lassoc שהשתמשנו בה ב-table-get מוגדרת להלן:

(define lassoc
  (lambda (k al equ?)
    (let loop ((al al))
      (if (null? al) #f
          (let ((c (car al)))
            (if (equ? (car c) k) c
                (loop (cdr al))))))))

הפרוצדורה !table-put משמשת לעדכון ערך המפתח ב-table נתון:

(define table-put!
  (lambda (tbl k v)
    (let ((al (table.alist tbl)))
      (let ((c (lassoc k al (table.equ tbl))))
        (if c (set-cdr! c v)
            (set!table.alist tbl (cons (cons k v) al)))))))

הפרוצדורה table-for-each קוראת לפרוצדורה נתונה עבור כל זוג מפתח/ערך ב-table:

(define table-for-each
  (lambda (tbl p)
    (for-each
     (lambda (c)
       (p (car c) (cdr c)))
     (table.alist tbl))))