פונקציה רקורסיבית שמכניסה איבר לרשימה ממוינת.

כתבתי תנאי עצירה:

 insert(X,[],[L|X]).

אבל, הרצה לדוגמא:

?- insert(5,[],L).

L = [H186 | 5] ;
no

למה?

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

מבחינת פרולוג, כשאת מבצעת את הקריאה שלך:

insert(5,[],L).

פרולוג מחפש כלל מתאים. בהתחלה הוא סורק את אוסף הכללים ומוצא את זה שמתאים בשם של הכלל ובמספר המשתנים בו. מהרגע שנמצא מועמד מתאים מתבצעת יוניפקציה (אין לי מושג איך קוראים לזה בעברית) של X עם 5, הרשימה הריקה מתאימה לרשימה ריקה (מכיוון שהם שניהם ערכים ולא משתנים אפשר לחשוב על זה כעל תנאי של שיוויון - כלומר כל קריאה לחוק הזה כשהרשימה לא ריקה יגרום לפרולוג לחפש כלל אחר שמתאים עם אותו שם ואותו מספר משתנים), ולבסוף מתבצעת יוניפיקציה של המשתנה L שלך עם רשימה של משתנה והערך של X (שעכשיו כבר עשה יוניפיקציה ולכן מקבל את הערך 5). צריך לשים לב, שהעובדה שכתוב L בהגדרת הכלל לא משנה את העובדה שזה משתנה של הכלל שאין ערך לשמו מחוץ לכלל!.

ולכן תנאי העצירה הנכון הוא:

 insert(X,[],[X]).

כלומר הכנסה לרשימה ריקה תחזיר את הרשימה עם האיבר המתאים.

כן, אבל אז מה אעשה כשצריך להכניס את האיבר למקומו ברשימה ממוינת??

בפונקציה הבאה- הוא תמיד מכניס לי את האיבר להתחלה.

מה לא תקין?

in(X,[H|T],L):- X>H, in(X,T,[H|L]).
in(X,L,[X|L]).

נראה לי יש בעיה עם הארגומנט השלישי בקריאה הרקורסיבית לפונקציה.

הסיבה שזה לא עובד היא לא הקריאה הרקורסיבית אלא ההגדרה של הכלל.

מה שכתוב בקוד ניתן לתרגום באופן הבא: כשיקראו לכלל עם ערך עבור X, ורשימה תחילית כלשהי [H|T], ואיזשהו משתנה שמחזיר את התוצאה(!) L, אז אם X גדול מהאיבר הראשון ברשימה המקורית תכניס את הרשימה המקורית לפני L. אם עוקבים אחרי מהלך התוכנית (יש פקודה בפרולוג שנקראית trace ומאפשרת לעשות זאת), רואים שהתוכנית מתקדמת ברקורסיה (ואגב כך הופכת לגמרי את הרשימה), ולבסוף בשלב שבו היא צריכה להכניס את האיבר היא נכשלת חוזרת את כל הרקורסיה ומפעילה את הכלל השלישי שלך.

ולכן הפתרון הוא:

in(X,[H|T],[H|L]):- 
	X>H, 
	in(X,T,L).

לא עובד.

מה כן?

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

כתבתי את הקוד הבא:

פונקציה INSERT המקבלת איבר ורשימה.

היא קוראת לפנוקצית עזר IN.

הבעיה התשובה המוחזרת היא YES / NO, ולא הרשימה המתוקנת.

insert(X,L):- in(X,L,M).

in(X,[],[X]).
in(X,[H|T],[X,H|T]):- X<H. 
in(X,[H|T],[H|L]):- X>=H, in(X,T,L).