|
בפרק החמישי למדנו על רשימות בפרולוג, והכרנו מתארים לפעולות על רשימות, ביניהן פעולת השרשור. ציינו אז שהפעולה append עשויה להיות לא יעילה. בפרק זה נלמד על סוג מיוחד של רשימות, רשימות הפרשים, שמאפשרות לבצע פעולות דוגמת שרשור ביעילות.
הרעיון הבסיסי הוא להימנע מיצירת מבנים חדשים ורשימות חדשות אם אין בכך צורך. אינטואיטיבית, הרבה יותר יעיל להוסיף מידע למבנה קיים מאשר ליצור עותק חדש שלו ולהוסיף את המידע לאותו עותק.
לדוגמא, יעיל יותר ליצור רשימה [hermione, harry, ron | X] , ולמלא את השם הנוסף על ידי השמה של neville לתוך X, מאשר להסתפק ברשימה קצרה [hermione, harry, ron] ולשרשר אותה לרשימה [neville].
רשימות פתוחות (open lists) הן רשימות שזנבן אינו מאותחל, כמו הרשימה [hermione, harry, ron | X]. רשימות הפרשים (difference lists) הן רשימות פתוחות עם גישה לזנב שאינו מאותחל. הן מאפשרות את הגמישות של רשימות פתוחות, יחד עם היכולת לגשת ישירות לחלק הלא מאותחל של הרשימה מבלי לעבור על כל יתר האיברים.
ברשימת הפרשים שומרים מעין מצביע (פוינטר) לזנב הרשימה. הנה מספר דרכים לכתוב רשימת הפרשים מסוימת:
dl([a, b, c | X], X).
[a, b, c | X] - X.
hefreshim([a, b, c | X], X).
שם המתאר שבוחרים אינו חשוב, מה שחשוב הוא לשמור גישה לזנב הרשימה הפתוחה. רבים משתמשים בסגנון הכתיבה המוצג בשורה השנייה לעיל, תוך שימוש באופרטור infix "-".
כדאי להתרגל להשתמש ברשימות הפרשים בעיקר משיקולי יעילות. בפרק הבא נראה כי פרולוג עצמו משתמש בהן, גם כאשר על פני השטח לא רואים אותן.
בינתיים, מספר דוגמאות שיבהירו איך משתמשים בהן.
נתחיל בהבהרת הקשר בין רשימה רגילה לרשימת הפרשים. איך הופכים רשימת הפרשים [List | T]-T לרשימה רגילה עם זנב "סגור"? פשוט "ממלאים" אותו עם הרשימה הריקה:
dl2list(List-[], List).
?- dl2list([a, b, c | T]-T, List).
T = []
List = [a, b, c]
Yes
כעת למשימה סבוכה יותר.
נכתוב מתאר לשרשור שתי רשימות הפרשים: diff_list_append/3. הוא יקבל שתי רשימות הפרשים ויחזיר רשימת הפרשים המורכבת מאברי שתי הרשימות, עם זנב הרשימה השנייה. למשל:
?- diff_list_append([1,2,3|X]-X, [4,5,6|Y]-Y, Result).
X = [4, 5, 6|_G490]
Y = _G490
Result = [1, 2, 3, 4, 5, 6|_G490]-_G490
Yes
הרעיון הבסיסי הוא למלא את זנב הרשימה הראשונה בתוכן הרשימה השנייה, ולקבוע את זנב הרשימה השנייה לזנב הרשימה המשורשרת.
בפרולוג זה נראה כך:
diff_list_append(DL1-T1, DL2-T2, DL1-T2) :-
T1 = DL2.
אם נשתמש בתכונות ההאחדה, נוכל לקצר עוד יותר ולבצע את ההשמה של DL2 לתוך T1 כבר בעת הקריאה עצמה:
diff_list_append(DL1-T1, T1-T2, DL1-T2).
שימוש חשוב של רשימות הפרשים נראה בפרק הבא כשנדון בדקדוקי DCG. שם רשימות ההפרשים ייצגו צירופי מילים. הנה "בקרוב" קצר:
את שם העצם כלב נייצג בעזרת רשימת הפרשים shem([kelev|X],X). מועיל לחשוב על ייצוג זה כאומר משהו כמו "השם כלב מיוצג באמצעות רשימה שמתחילה באבר kelev". כל רשימות ההפרשים הבאות (ועוד אינסוף אחרות) מייצגות את שם העצם כלב:
[kelev] []
[kelev, axal, daysa] [axal, daysa]
[kelev, 1, 2, 3] [1, 2, 3]
באופן דומה נעניק ייצוג לפועל אכל ולשם דייסה, ולבסוף נוכל להגדיר מהו הייצוג של משפט על בסיס מרכיביו אלה.
|
