|
בפרק 2 למדנו לבצע בפרולוג פעולות חשבון בסיסיות על מספרים שלמים. כעת נשתמש בידע זה כדי לכתוב מתארים נוספים על רשימות, כאלה שעושים חישובים על גבי רשימות.
אורך רשימה
בהינתן רשימה נרצה לגלות מה אורכה, כלומר כמה אברים יש בה. נציג כאן שתי הגדרות חלופיות לאורך רשימה: אחת שבה ספירת האברים נעשית אחרי מעבר על הרשימה, ואחרת שבה הספירה נעשית תוך כדי מעבר על האברים.
הנה הגדרה רקורסיבית לחישוב אורך רשימה:
- אורך רשימה ריקה הוא 0.
- אורך רשימה לא ריקה הוא 1 ועוד אורך רשימת הזנב שלה.
קל לתרגם הגדרות אלה לפרולוג. נגדיר את המתאר myLength לחישוב אורך רשימה:
myLength([],0).
myLength([_|Tail],N) :- myLength(Tail, N1),
N is N1+1.
מתאר זה פועל כנדרש, ואפשר בעזרתו לברר ולמצוא אורך של רשימות. אולם, שימו לב שספירת האברים נעשית כאן רק אחרי שסיימנו לעבור על כל הרשימה. אז אנו מחברים אחדות כמספר האברים ומקבלים את אורך הרשימה. בכל רמה ברקורסיה אנו נזקקים להמתין לתוצאת הרמה הבאה על מנת לסיים את החישוב: על מנת לחשב את N יש להמתין עד שיודעים את N1.
ננסה לחשוב על פתרון אחר, שבו נתקדם בספירת האברים בכל שלב ברקורסיה כך שבסוף התהליך מיד יהיה בידנו מספר האברים. לשם כך נשתמש בצובר, משתנה מיוחד בו נשמור את תוצאות הביניים של הספירה.
myLenAcc([_|Tail],Acc,R) :-
Acc1 is Acc+1,
myLenAcc(Tail,Acc1,R).
myLenAcc([],R,R).
בכל שלב ברקורסיה אנו מקדמים ב-1 את הצובר. בסיום אנו משתמשים בהאחדה כדי לקבל את אורך הרשימה במתואר השלישי.
יש לאתחל את הצובר ל-0 בתחילת התהליך, זאת נעשה מפורשות בגוף השאילתא:
?- myLenAcc([1,2,[1,2,0],[]],0,R).
R = 4
Yes
את האתחול אפשר לעשות גם בפרדיקאט מיוחד כפי שעשינו בהגדרת myRevAcc, המתאר להיפוך רשימה בעזרת צובר.
ראינו שתי הגדרות רקורסיביות לחישוב אורך רשימה. ההבדל ביניהן נעוץ בסוג הרקורסיה בה השתמשנו בחישוב. השיטה השניה, עם הצובר, היא דוגמא של "רקורסיית זנב" (tail recursion), רקורסיה שבה חישובים נעשים תוך כדי המעבר הרקורסיבי כך שהתוצאה כבר מחושבת בסיומו. השיטה הראשונה לא הייתה רקורסיית זנב, ונדרשנו לבצע חישובים לאחר תום המעבר הרקורסיבי על מנת לקבל את התוצאה.
אבר מקסימלי ברשימה
בהינתן רשימה שכל אבריה מספרים טבעיים, נרצה לגלות את האבר המקסימלי.
נעבור על הרשימה אבר אחר אבר ונשמור בכל שלב את האבר המקסימלי עד אותו שלב. אם ניתקל במספר גדול יותר, נעדכן את האבר השמור. נאתחל את המקסימום ל-0, בהנחה שהרשימות הנתונות מכילות רק מספרים חיוביים.
max_list([], Max, Max).
max_list([H|T], Max, Result) :-
NewMax is max(H,Max),
max_list(T, NewMax, Result).
maximum(List, N) :- max_list(List, 0, N).
שימו לב שעשינו כאן שימוש במתאר המובנה max/2.
|
