אתר ללימוד מקיף> פרק 2 - תבניות נתונים

פרק 2 - תבניות נתונים

הנושאים בדף זה:
2.1.     הנתונים הפשוטים.
          2.1.1. בוליאניים.
          2.1.2. מספרים.
          2.1.3. characters.
          2.1.4. symbols.
2.2     סוגי נתונים מורכבים.
          2.2.1. מחרוזות.
          2.2.2. וקטורים.
          2.2.3. רשימות ו-dotted pairs.
          2.2.4. המרות בין תבניות נתונים.
2.3     תבניות נתונים נוספות.
2.4     S-expressions.

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

2.1 הנתונים הפשוטים:

הנתונים הפשוטים מכילים את הנתונים הבאים: symbols ,characters ,booleans ומספרים.

2.1.1 בוליאניים:

ה-booleans בשפה Scheme הם: f# - מייצג שקר ו-t# - מייצג אמת. ב-Scheme ישנו פרדיקט הנקרא
?boolean, אשר בודק אם הארגומנט הוא boolean.
לדוגמא,

(boolean? #t)              => #t
(boolean? "Hello, World!") => #f

הפרוצדורה not מחזירה ההפך מהארגומנט עליו היא מופעלת, בתנאי שהוא boolean. לדוגמא,

(not #f) => #t
(not #t) => #f 
(not "Hello, World!") => #f

הביטוי האחרון מדגים את הנוחות של Scheme: במקרה ודרוש Scheme ,boolean תתייחס לכל משתנה שהוא לא f#, כאל ערך אמת.

2.1.2 מספרים:

המספרים ב-Scheme יכולים להיות מספרים שלמים (42), רציונלים (22/7), ממשים (3.1416) או מרוכבים
(2+3i). מספר שלם הוא בפרט רציונלי שהוא בפרט מספר ממשי שהוא בפרט מספר מרוכב והוא בפרט מספר. ישנם פרדיקטים הבודקים את הסוגים השונים של המספרים:

(number? 42)       => #t
(number? #t)       => #f
(complex? 2+3i)    => #t
(real? 2+3i)       => #f
(real? 3.1416)     => #t
(real? 42)         => #t
(rational? 3.1416) => #f
(rational? 22/7)   => #t
(integer? 22/7)    => #f
(integer? 42)      => #t

המספרים השלמים ב-Scheme לא מוכרחים להיות מיוצגים כמספרים דצימליים (בסיס 10). הם יכולים להיות מיוצגים כמספרים בינארים, אך צריך להוסיף קידומת b#. לדוגמא, b1100 #, מייצג את המספר שנים עשר. הקידומת של מספר אוקטלי היא o# ושל מספרים הקסאדצימליים הקידומת היא x#. (הקידומת של מספרים דצימלים היא d#).
ניתן לבדוק שוויון בין מספרים ע"י הפרדיקט ?eqv.

(eqv? 42 42) => #t
(eqv? 42 #f) => #f
(eqv? 42 42.0) => #f

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

(= 42 42) => #t 
(= 42 #f) -->ERROR!!!
(= 42 42.0) => #t

ניתן לעשות השוואות אחרות:

(< 3 2) => #f
(>= 4.5 3) => #t

לפרוצדורות האריתמטיות +,-,*,/ יש התנהגות צפויה:

(+ 1 2 3) => 6
(- 5.3 2) => 3.3
(- 5 2 1) => 2
(* 1 2 3) => 6
(/ 6 3)   => 2
(/ 22 7)  => 22/7

לארגומנט יחיד, - ו-/ נקבל את המספר הנגדי לחיבור ואת ההפכי לכפל בהתאמה:

(- 4) => -4
(/ 4) => 1/4

הפרוצדורות max ו-min מחזירות את המקסימום והמינימום בהתאם למספרים שסופקו להם. ניתן לספק לפרוצדורות אלו מספר בלתי מוגבל של ארגומנטים.

(max 1 3 4 2 3) => 4
(min 1 3 4 2 3) => 1

טיפ נוסף על קצה המזלג: Scheme מספקת כמות גדולה של פרוצדורות אריתמטיות מורכבות וכן פרוצדורות טריגונומטריות .

2.1.3 characters:

ה-char ב-Scheme מיוצג ע"י הקידומת #\ .לכן c#\ מייצג את ה-c char. ישנם characters לא גרפיים ולהם יש שמות תיאוריים לדוגמא, newline\# ו-tab\#. ה-char המציין רווח יכול להיות מיוצג כך #\, או בצורה יותר קריאה space#\.
הפרדיקט הבוליאני של ה-char הוא ?char.

(char? #\c) => #t
(char? 1) => #f 
(char? #\;) => #t

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

(char=? #\a #\a)  => #t
(char<? #\a #\b)  => #t
(char>=? #\a #\b) => #f

כדי לבצע השוואות בין תווי אותיות קטנות וגדולות נשתמש בפרדיקט char-ci במקום char:

(char-ci=? #\a #\A) => #t
(char-ci #t

פרוצדורות ההמרה בין אותיות קטנות וגדולות הן char-downcase ו-char-upercase :

(char-downcase #\A) => #\a
(char-upcase #\a)   => #\A

2.1.4 symbols

תבניות הנתונים שראינו לעיל מוערכות להיות עצמן. כלומר, אם ניתן אחת מתבניות אלו ל-listener, התוצאה המוערכת שתוחזר ע"י ה-listener תהיה אותה התבנית בעצמה. לדוגמא:

#t => #t 

42 => 42 

#\c => #\c

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

על מנת לציין שמדובר בסמל על המשתמש לציין זאת ע"י quote:

(quote xyz)

=>  xyz

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

'E

שקול לביטוי:

(quote E)

ה-symbols ב-Scheme הם רצף של תווים. אך ישנה מגבלה על שמות ה-symbols, אסור לבלבל אותם עם שאר סוגי המשתנים תווים, בוליאנים, מספרים או נתונים מורכבים.
כלומר:

this-is-a-symbol, i18n, <=> ,$, ! ,# ,*

הם SYMBOLS אך 16, i (מס' מרוכב), "t, "this-is-a-string# ו-(barf) (רשימה) לא.

הפרדיקט המיועד לבדיקת סמלים הוא :?symbol.

 (symbol? 'xyz) =>  #t
 (symbol? 42)   =>  #f

ב-Scheme אין הבדל בין אות גדולה לאות קטנה ב-symbols, לכן הסמל Calorie זהה לסמל calorie:

(eqv? 'Calorie calorie')
=>  #t

ניתן להשתמש בסמל xyz כמשתנה גלובלי ע"י שימוש בתבנית define:

(define xyz 9)

כתיבה זו מציינת שהמשתנה xyz מכיל את הערך 9. אם נספק נתון זה ל-listener התוצאה תהיה הערך של xyz:

xyz
=>  9

נתן להשתמש בתבנית !set על מנת לשנות את הערך שמכיל המשתנה הנ"ל :

(set! xyz #\c)

וכעת

xyz
=>  #\c

2.2 סוגי נתונים מורכבים

הנתונים המורכבים הם ע"י צרוף נתונים אחרים בדרכים שונות והגיוניות.

2.2.1 מחרוזות

מחרוזת היא רצף של תווים (לא לבלבל עם symbols שהם נתונים פשוטים שמוערכים לעצמם).
המשתמש יכול לציין מחרוזות ע"י צרוף התווים ע"י גרשיים.
המחרוזות מוערכות לעצמן:

"Hello, World!"
=>  "Hello, World!"

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

(string #\h #\e #\l #\l #\o)
=>  "hello"

כעת נגדיר את המשתנה הכללי greeting:

(define greeting "Hello; Hello!")

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

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

(string-ref greeting 0)

=>  #\H

הפרוצדורה !string-set מחליפה את התו במקום האינדקס בתו אחר:

(string-set! greeting 1 #\a)
greeting
=>  "Hallo; Hello!"

המחרוזות יכולות להיווצר ע"י צרוף מחרוזות שונות ע"י הפרדיקט string-append:

(string-append "E "
               "Pluribus "
               "Unum")
=>  "E Pluribus Unum"

ניתן ליצור מחרוזת באורך ספציפי ולמלא אותו בעזרת !string-set.

(define a-3-char-long-string (make-string 3))

הפרדיקט המשמש לבדיקת מחרוזות הוא: ?string.

2.2.2 וקטורים

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

להלן דרך ליצור וקטור המכיל חמישה מספרים שלמים:

(vector 0 1 2 3 4)
=>  #(0 1 2 3 4)

Scheme מייצגת וקטור ע"י #, המלווה בתוכן הוקטור ומוקף בסוגריים.
בהקבלה ל-make-string הפרוצדורה make-vector יוצרת וקטור באורך ספציפי :

(define v (make-vector 5))

הפרוצדורות vector-ref ו-!vector-set יכולות לגשת ולשנות את האלמנטים הוקטור. הפרדיקט המשמש לבדיקת וקטור הוא: ?vector.

2.2.3 רשימות ו-dotted pairs

dotted pair הוא תבנית מורכבת המצרפת שני ערכים שרירותיים לזוג סדור. האלמנט הראשון בזוג נקרא car, האלמנט השני נקרא cdr ופרוצדורת השילוב ביניהם נקראת cons.

(cons 1 #t)
=> (1 . #t)

dotted pairs אינם מוערכים להיות עצמם לכן כדי להתייחס אליהם כאל נתונים (כלומר, לא לפרש אותם באמצעות הקריאה ל-cons) בפירוש חייבים לשים לפניהם גרש בודד.

'(1 . #t) => (1 . #t)

(1 . #t)  -->ERROR!!!

פרוצדורות העזר הן car ו-cdr:

(define x (cons 1 #t))

(car x)=> 1
(cdr x)=> #t

האלמנטים של הזוג יכולים להיות מוחלפים באמצעות הפרוצדורות !set-car ו- !set-cdr:

(set-car! x 2)
(set-cdr! x #f)
x
=> (2 . #f)

זוגות יכולים להכיל זוגות אחרים. לדוגמא:

(define y (cons (cons 1 2) 3))
y
=> ((1 . 2) . 3)

ה-car של ה-car של הרשימה הוא 1. ה-cdr של ה-car הרשימה הוא 2. כלומר:

(car (car y))
=> 1
(cdr (car y))
=> 2

Scheme מספקת קיצורים לפרוצדורות car ו-cdr מורכבות יותר. כלומר, caar הוא קיצור ל-car של car וכן cdar הוא קיצור ל-cdr של car וכו'.

(caar y)
=> 1

(cdar y)
=> 2

c...r - קיצור לארבעה דרוגים קיימים. הביטויים cdar ,cdadar, cdaddr תקינים. נשתמש בקיצור זה כדי להימנע מטעויות.

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

(cons 1 (cons 2 (cons 3 (cons 4 5))))
=> (1 2 3 4 . 5)

כלומר, (1234.5) הוא קיצור ל-

(1.(2.(3.(4.5)))).

ה-cdr האחרון של הביטוי הוא 5.

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

'() => ()

הקיצור של הזוג מהתבנית:

(1 . (2 . (3 . (4 . ()))))

הוא: (4 3 2 1).
זוג מקונן מיוחד זה נקרא רשימה .אורך רשימה ספציפית זו הוא ארבע. ניתן ליצור אותה ע"י:

(cons 1 (cons 2 (cons 3 (cons 4 '()))))

אך Scheme מספקת פרוצדורה הנקראת list שיוצרת רשימות בצורה נוחה יותר. list יכולה לקבל מספר כלשהו של ארגומנטים וליצור מהם רשימה.

(list 1 2 3 4)
=> (1 2 3 4)

למעשה אם אנו יודעים מהם האלמנטים של הרשימה, נוכל לשים גרש בודד כדי לפרש רשימה זו:

'(1 2 3 4)
=> (1 2 3 4)

ניתן לגשת לאברי הרשימה ע"י אינדקס:

(define y (list 1 2 3 4))
(list-ref y 0) => 1
 (list-ref y 3) => 4
(list-tail y 1) => (2 3 4)
(list-tail y 3) => (4)

list- tail - מחזירה את הזנב של הרשימה החל מאינדקס נתון. הפרדיקטים ?pair, ?list ו-?null בודקים האם הארגומנט הוא זוג, רשימה או רשימה ריקה בהתאמה:

(pair? '(1 . 2)) => #t 
(pair? '(1 2)) => #t (pair? '()) => #f 
(list? '()) => #t 
(null? '()) => #t
(list? '(1 2)) => #t 
(list? '(1 . 2)) => #f
(null? '(1 2)) => #f 
(null? '(1 . 2)) => #f

2.2.4 המרות בין תבניות נתונים:

ל-Scheme ישנן פרוצדורות המשמשות להמרה בין סוגי נתונים. אנו כבר יודעים כיצד להמיר בין תווים ע"י הפרוצדורות char-downcase ו-char-upcase. ניתן להמיר תווים למספרים שלמים ע"י הפרוצדורה: char->integer וניתן להמיר מספרים שלמים לתווים ע"י הפרוצדורה:
integer->char (המספר השלם המתקבל מההמרה הוא בד"כ הקוד ה-ascii של התו).

(char->integer #\d) => 100
(integer->char 50) => #\2

ניתן להמיר מחרוזת לרשימת תווים מתאימה.

(string->list "hello") => (#\h #\e #\l #\l #\o)

שאר ההמרות הן מהסגנון של: list->string, vector->list ,ו-list->vector.
ניתן להמיר מספרים למחרוזות:

(number->string 16) => "16"

ניתן להמיר מחרוזות למספרים. אם המחרוזת לא מתאימה לאף מספר יוחזר f#.

(string->number "16")
=>16

(string->number "Am I a hot number?")
=> #f

במידה ונוסיף איבר שני לפרוצדורה string->number היא תתייחס אליו כאל הבסיס שבו המספר יהיה מיוצג.

(string->number "16" 8) => 14

התוצאה אכן נכונה כי 16 בבסיס 8 הוא המספר 14.

ניתן להמיר סמלים למחרוזות ולהפך:

(symbol->string 'symbol)
=>"symbol"
(string->symbol "string")
=> string

2.3 תבניות נתונים נוספות:

Scheme מכילה תבניות נוספות של נתונים ,לדוגמא פרוצדורות .ראינו לא מעט פרוצדורות כמו cons ,+ ,display. למעשה אלו הם משתנים המכילים את ערכי הפרוצדורה אשר אינם ברורים כמו מספרים תווים וכו'.

cons
=> <procedure>

הפרוצדורות שראינו עד כה הינן פרימיטיביות שמשתנים גלובליים מכילים אותם. משתמשים יכולים ליצור ערכי פרוצדורה נוספים.
סוג נוסף של נתון הוא port. port הוא צינור שדרכו ניתן לנהל את הפלט והקלט. Ports בד"כ קשורים לקבצים ול-consoles.
בתוכנית הראשונה שלנו "!Hello World", הארגומנט השני של הפרוצדורה display לא מפורש. ברירת המחדל לאמצעי הפלט הוא ה-standard output. אנו יכולים לקבל את אמצעי הפלט הנוכחי ע"י הקריאה לפרוצדורה (current-output-port). אנו יכולים להיות מפורשים יותר כך:

(display "Hello, World!" (current-output-port))

S-expressions 2.4:

כל סוגי הנתונים שדנו בהם יכולים להיכלל למושג אחד הנקרא: s-expression (ה-s - מיצג symbolic). לכן

42,
#\c,
(1.2),
#(a b c ),
"hello", 
(quote xyz),
(string->number "16") ו-
(begin( display "Hello ,World!") (newline))

הם s-expression.