פרק 5: רשימות

5.2 פעולות על רשימות

בדיקת שייכות

פעולה בסיסית על רשימות היא היכולת לבדוק אם אבר נתון, A, הוא אבר ברשימה נתונה, L.

נכתוב מתאר שיבצע פעולה זו. החוקים לבדיקת שייכות יהיו רקורסיביים, ומבוססים על המבנה הרקורסיבי של הרשימה:

מבחינה הצהרתית, החלק הראשון בהגדרה הוא העובדה: אם האבר המבוקש הוא האבר הראשון ברשימה, אזי הוא אבר ברשימה. החוק הרקורסיבי מטפל במקרה שהאבר הוא חלק מזנב הרשימה.

כעת נבדוק את פניה הפרוצדורליים של התכנית: נבדוק אם היא מחזירה תשובות נכונות, ונתחקה אחר אופן פעולתה במספר דוגמאות.

התשובה נכונה, ומבוססת על האחדה של המשתנה A בסעיף הראשון של הגדרת הפרדיקאט. 1 הוא ראש הרשימה, ועל כן חבר ברשימה.

על מנת לגלות את התשובה הנכונה במקרה זה, פרולוג נזקק לסעיף השני של ההגדרה. המטרה להוכחה הופכת להיות myMember(2, [2, 3, 4]), והיא מוכחת בעזרת הסעיף הראשון של ההגדרה.

האם התכנית תעבוד גם במקרה שהאבר עליו שואלים איננו חלק מהרשימה? האם היא תצליח לצאת מהרקורסיה ולתת תשובה שלילית?
נראה כעת דוגמא כזו שלב-שלב (בעזרת הפונקציה trace, אשר מציגה כל שלב ושלב בתהליך החישוב של שאילתא):

זה השלב בו הרקורסיה נעצרת. מכיוון שלא ניתן לפרק את הרשימה הריקה, ולא ניתן להוכיח את המטרה בדרך אחרת – התהליך ייעצר ונקבל תשובה שלילית בסוף.

לסיום, נאיר פן נוסף של בדיקת השייכות. נוסף על השימוש הטבעי בבדיקה, כדי לקבוע אם אבר שייך לרשימה נתונה או לא, ניתן להשתמש בבדיקה בצירוף משתנים על מנת לברר מיהם כל האברים השייכים לרשימה. עושים זאת על ידי השאילתא הבאה, שמשמעותה "מיהו איבר ברשימה?":

שרשור

נכתוב מתאר לשרשור רשימות. בהינתן שתי רשימות, נרצה לקבל רשימה שלישית שהיא תוצאת השרשור של הרשימה השניה לראשונה. הפעולה, myAppend, מודגמת להלן:

המתאר לשרשור משמש אותנו לארבע מטרות:

1. לבדיקת השערה בדבר היותה של רשימה נתונה תוצאת שרשור של שתי רשימות נתונות.
2. לקבלת הרשימה שהיא תוצאת שרשור שתי רשימות נתונות.
3. לשחזור אחת הרשימות בשרשור נתון, כאשר נתונה הרשימה השניה.
4. למציאת כל האפשרויות של שרשור שתי רשימות שתוצאתן היא שרשור נתון.

ההגדרה עצמה היא רקורסיבית, כמובן. נסו לכתוב אותה בעצמכם!

היפוך

הפעולה הבאה שנממש על רשימות הנה היפוך. בהינתן רשימה, נרצה להחזיר את הרשימה המתקבלת מהיפוך סדר אבריה. המתאר ייקרא myReverse, ופעולתו מודגמת להלן:

המתאר להיפוך משמש אותנו לשתי מטרות:

1. לבדיקת השערה בדבר היותן של שתי רשימות נתונות הפוכות זו לזו.
2. לקבלת הרשימה שהיא תוצאת היפוך של רשימה נתונה.

בעזרת ההיפוך נוכל גם לגשת ביתר קלות לאברים בסוף הרשימה המקורית, דבר שאיננו יכולים לעשות בקלות בשלב זה. כל שיהא עלינו לעשות הוא להפוך את הרשימה המקורית, ולגשת לאברים הראשונים (וזה קל).

יש יותר מדרך אחת להגדיר את מתאר ההיפוך. נראה שתי דרכים: הדרך הנאיבית בעזרת שרשור, ודרך יעילה יותר בעזרת צובר (accumulator).

הדרך הנאיבית מבוססת על הרעיון הבא: כדי להפוך רשימה [Head | Tail], אפשר להפוך את זנבה, reverse(Tail), ולשרשר את הראש אל ההיפוך:
append(reverse(Tail), [Head]).

הנה ההגדרה בשיטה הנאיבית:

השיטה עובדת, אך היא אינה יעילה. באופן מיוחד, הקריאות הרקורסיביות של פעולת השרשור הן רבות ולא יעילות.

דרך אחרת לבצע היפוך מבוססת על צבירת אברי הרשימה המקורית ברשימה חדשה בסדר הפוך. בהגדרה זו של ההיפוך, אחד המתוארים יהיה צובר אשר בו תיבנה הרשימה החדשה צעד אחר צעד: תחילה נקפד את ראשה של הרשימה המקורית ונכניס אותו לראש של הצובר. אחר כך נוריד את הראש של מה שנשאר (הזנב), ונכניס אותו כראש חדש של הצובר. כך עד האבר האחרון. בסיום התהליך יכיל הצובר את הרשימה בסדר הפוך. בפרולוג זה נראה כך:

נעטוף את המתאר בקריאה המאתחלת את הצובר (לרשימה הריקה) לפני התחלת הצבירה:

הצובר הוא פשוט משתנה שמשמש אותנו לשמירת תוצאות ביניים בחישוב. כאן, הוא צובר בזה אחר זה את אברי הרשימה המקורית בסדר הפוך, ובסיום מכיל את הרשימה ההפוכה כולה.
השימוש בצובר יעיל יותר וברור יותר מבחינה פרוצדורלית מאשר ההיפוך באמצעות שרשור. נראה כעת כיצד עקרון הצבירה משמש אותנו גם בפעולות נוספות על רשימות.

מבוא

נושאים בסיסיים

נושאים מתקדמים

סיכום