פרוייקט "התלמיד והמחשב", בעיה 8

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

טוב, זה לא היה קשה כל כך. נלך על המקרה הכללי!

בעיה מס' 8

בספר הבעיה הייתה “נתונים שלושה מספרים, הוצא כפלט את המקסימלי מביניהם”. שזה נחמד בתור המחשה להסתעפות של תוכנית על בסיס משפטי תנאי: אם a גדול מ-b, אז השווה את c ל-a והדפס את הגדול מביניהם, ואחרת השווה את c ל-b והדפס את הגדול מביניהם. אבל אני מקווה שכבר הבנו את העקרונות הללו בתרגילים קודמים, ולא נרוויח הרבה מהתרגיל הזה בתור המחשה של עבודה עם תנאים נטו. אז במקום לדבר על מציאת המקסימום של שלושה מספרים, בואו נדבר על מציאת המקסימום של כמות כלשהי של מספרים, ששמורים במערך. מערך הוא רשימה של אובייקטים מאותו הסוג, כך שאפשר לעבור על הרשימה באופן סדרתי. למשל, לכל איבר במערך יש אינדקס (ובדרך כלל האינדקס מתחיל מ-0 ולא מ-1 כמו שאפשר לצפות מהחיים האמיתיים) ואפשר לגשת לכל איבר על ידי מעבר סדרתי על האינדקסים. אלא שאני הולך לנקוט גישה קצת שונה למעבר על מערך, שקצת יותר מתאימה לאופי של רובי:

# puts "The maximum among #{ARGV.join(", ")} is #{ARGV.collect{|x| x.to_i}.max}"
array = ARGV.collect{|x| x.to_i}
max = array.first
for x in array
  max = x if x > max
end
puts "The maximum among #{ARGV.join(", ")} is #{max}"

תתעלמו לרגע מהשורה הראשונה והשניה. בואו נניח שהמערך כבר נתון לנו - מה עושים איתו? ובכן, ראשית מגדירים את max להיות האיבר הראשון במערך; עכשיו עוברים סדרתית על כל האיברים במערך. כל איבר שכזה מכניסים לרגע למשתנה x, ואז משווים את x ל-max. אם x גדול יותר, אז משנים את max כך שיכיל את הערך של x. די בבירור, אחרי שסיימנו לעבור על כל המערך כך, הערך של max יהיה של האיבר המקסימלי במערך.

שורת המחץ המעניינת כאן היא השורה “for x in array”. מה שהשורה הזו אומרת לתוכנית הוא לעבור על כל האיברים ב-array, להכניס כל אחד מהם למשתנה x בתורו (על פי הסדר של האיברים ב-array, לא באופן אקראי), ואז להפעיל את בלוק הקוד שנמצא החל מהשורה הבאה ועד ל-end. זו הדוגמה הבסיסית ביותר ברובי לאיטרטור; איטרטור הוא משהו שמקבל מבנה נתונים מורכב ועובר בצורה סדרתית זו או אחרת על האיברים שבו ועושה איתם משהו. למעשה, ה-for הוא סוג מיוחד של איטרטור במובן זה שהתחביר שלו שונה מהתחביר ה”רגיל” של איטרטורים; ליתר דיוק, ה-for הוא פשוט דרך אחרת לכתוב איטרטור שכבר קיים בשפה בצורה אחרת ונקרא each ואציג אותו בהמשך. למה שיהיו שתי דרכים שונות לכתוב את אותו הדבר? ובכן, זה דבר די נפוץ בשפות תכנות שמטרתו להקל על הקריאות של התוכנית ולאפשר גיוון סגנוני; לדברים כאלו נהוג לקרוא Syntactic Sugar (למרות זאת יש הבדל בין שתי הגישות, שלא רלוונטי למי שלא מכיר עדיין את השפה; למי שסקרן, משתנים שמוגדרים בתוך בלוק ה-for יהיו קיימים גם אחריו, ומשתנים שמוגדרים בתוך בלוק ה-each לא יהיו).

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

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

a = [1,2,3,4,5]
b = a.collect{|x| x*x}
puts a.inspect
puts b.inspect

הפלט של קטע הקוד הזה יהיה

[1, 2, 3, 4, 5]
[1, 4, 9, 16, 25]

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

למי שזה עדיין קשה לו - לא לדאוג, נמשיך לראות את הדברים הללו עוד ועוד בהמשך.

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

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

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

import System.Environment

toIntArray :: [String] -> [Int]
toIntArray array = [read(x) | x <- array]

getMax :: [Int] -> Int
getMax [x] 	= x
getMax (x:xs)
  | x > m  	= x
  | x <= m 	= m
  where m = getMax xs

main = do
  args <- getArgs
  putStrLn (show(getMax(toIntArray args)))

ה-import למעלה הוא בגלל שאני רוצה להתחיל להשתמש ב-ARGV גם כאן. אפשר לראות את השימוש הזה למטה, בקוד של ה-main: אני קולט את ARGV לתוך המשתנה args ואז מתעלל בו כרגיל. עדיין לא הסברתי מה בעצם קורה ב-main ומה זה החץ הזה וכדומה - אני בכוונה מסתיר את הפרטים הללו לבינתיים כי הגישה של הסקל לענייני קלט/פלט נראית הזויה לחלוטין במבט ראשון (אבל יש בה הגיון לא קטן).

מה ש-getArgs הכניס ל-args היה מערך של מחרוזות. אני רוצה מערך של מספרים, אז אני כותב פונקציה שעושה את ההמרה הזו (אפשר היה לעשות את זה גם בגוף הקוד בלי פונקציה מיוחדת אבל אז זה היה נראה מכוער). כאן כבר נכנס לתמונה מבנה חדש ומגניב של הסקל, שבאופן מצער מאוד אין ברובי (למרות שבאח הגדול של רובי, פייתון, יש אותו): List Comprehension. זו דרך לבנות רשימה חדשה מתוך רשימה קיימת באמצעות כתיב שנראה ממש כמו הגדרת קבוצה מתמטית: בצד ימין יש לנו תיאור של הטווח שממנו x נלקח (הקלט array במקרה זה), באמצע יש לנו סימן של קו אנכי, ובצד שמאל יש לנו את מה שעושים ל-x לפני שמכניסים אותו לרשימה. זה ודאי לא נראה לכם שונה מ-collect של רובי למעט בתחביר, אבל כשרוצים לבנות רשימה מתוך כמה רשימות קיימות בו זמנית העסק מסתבך (קצת) ברובי אבל נשאר מאוד פשוט בהסקל.

אגב, הפונקציה read היא פונקציה רב תכליתית; היא מקבלת מחרוזת ויכולה להמיר אותה לשלל טיפוסים שונים ומשונים. איך היא יודעת איך להתנהג? כי כתבתי במפורש את הגדרת הפונקציה toIntArray ושם נכתב במפורש שהפונקציה מחזירה מערך של Int-ים, אז read מבינה שהיא מצופה להחזיר Int. אם לא הייתי כותב את הגדרת toIntArray במפורש, הייתי צריך לכתוב אחרי read נקודותיים ואז Int כדי לומר לה לאיזה פלט אני מצפה.

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

f 1 = 0
f 2 = 42
f x = x*x

זו הגדרה בשפת הסקל של הפונקציה הבאה:

\( f\left(x\right)=\begin{cases} 0 & x=1\\ 42 & x=2\\ x^{2} & \mbox{otherwise} \end{cases} \)

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

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

פורמלית, הנקודותיים הם אופרטור שמקבל איבר ורשימה ומוסיף את האיבר לתחילת הרשימה. למעשה, כשכותבים [1,2,3] בהסקל, זה סתם Syntactic Sugar: המשמעות האמיתית של זה היא []:1:2:3.

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

בואו נשתמש בגרסת הג’אווהסקריפט כדי ללמוד את הדרך ה”קלאסית” להגדיר איטרטורים - לולאת for “רגילה”, מהסוג שבו משתמשים בשפות כמו C ו-++C:

<html>
<head>
<title>Targil 8</title>
</head>
<body>
  <script type="text/javascript">
    find_max = function(){
		var nums = document.getElementById("nums").value.split(" ");
		var max = parseInt(nums[0])
		for (var i = 1; i < nums.length; i++){
			var x = parseInt(nums[i]);
			max = (x > max)?(x):(max);
		}
		document.getElementById("max").value = max;
    }
  </script>
  List = <input type="textbox" id="nums" value = "0" onkeyup = "find_max()"/>
  <br />
  Max = <input type="textbox" id="max" value = "0"/>
</body>
</html>

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

לולאת for כוללת שלושה מרכיבים: אתחול, תנאי עצירה, וקידום, שכתובים כולם בסוגריים שאחרי ה-for ומופרדים בנקודה פסיק. האתחול מתבצע בפעם הראשונה שבה אנחנו מגיעים לשורה הזו, ובמקרה שלנו הוא מגדיר משתנה חדש בשם i (השם הזה הוא מוסכמה; נהוג להשתמש בו תמיד למטרה הזו בלולאות for) ומאתחל את הערך שלו ל-1 (מכיוון שאת האיבר במקום 0 במערך כבר בדקנו). אחר כך נכתב תנאי העצירה; ליתר דיוק, כל עוד התנאי שנכתב מתקיים, הלולאה ממשיכה לרוץ, ולכן היא נעצרת כאשר התנאי אינו מתקיים. במקרה שלו, אנחנו דורשים ש-i יהיה קטן מאורך המערך. למה לא קטן שווה? מה עם האיבר האחרון במערך? ובכן, נקודה מצויינת שמבלבלת אנשים בכל רחבי העולם, כל הזמן. ברוב השפות, וגם בג’אווהסקריפט, האינדקס הקטן ביותר במערך הוא 0. יש לזה יתרונות רבים שאולי נראה יום אחד, אבל גם את החסרון שהאינדקס של האיבר האחרון במערך שאורכו n אינו n אלא n-1, ולכן כאשר האינדקס הרץ שלנו i הגיע ל-n צריך כבר לעצור.

אחרי תנאי העצירה מגיעה פעולת הקידום. היא מתבצעת בכל פעם שגוף הלולאה מסיים את הריצה שלו, ובמקרה שלנו מגדילה את i ב-1. בתוך הלולאה (מה שבין הסוגריים המסולסלים) לא קורה שום דבר מפתיע: אנחנו שולפים את האיבר ה-i מהמערך, ממירים ל-int, משווים ל-max ומעדכנים בהתאם. במילים אחרות, מה שעשינו ברובי, אבל עם קצת יותר הנהלת חשבונות - במקום לקבל ליד מייד את האיבר עצמו אנחנו צריכים לתחזק את האינדקס שלו ולשלוף אותו ידנית מהמערך, ולוודא שהאינדקס לא חורג מגודל המערך וכו’. איטרטורים מודרניים יותר מבטלים את הצורך בהנהלת החשבונות הזו ובכך מקטינים את השגיאות שהמתכנת עשוי לעשות (ותאמינו לי, הנהלת החשבונות הזו עשויה לגרום לבאגים שיידרשו ימים לתקן).

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