אתר ללימוד מזורז> פונקציות

פונקציות

ביטויי lambda

הגדרת ביטוי כלשהו מחברת יחד שמות וערכים היא מהצורה הבאה:

(define id exp)

להלן דוגמא של הגדרה:

(define pi 3.14)

בדוגמא זו הגדרנו pi להיות בעל הערך 3.14. זוהי אינה צורה של השמה מאחר ולא יהיה ניתן לקשור מחדש שם עם ערך אחר.

ביטויי Lambda

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

      (lambda ( id...)  exp )

הביטוי (...id) מסמל רשימת פרמטרים ו-exp מייצג את גוף ביטוי ה-lambda.
להלן שתי דוגמאות הממחישות את יישום ביטויי ה-lambda:

 ((lambda (x) (* x x)) 3) is 9
 ((lambda (x y) (+ x y)) 3 4) is 7

להלן הגדרה של פונקצית הריבוע:

 (define square (lambda (x) (* x x)))

להלן דוגמא ליישום הפונקציה:

 1 ]=> (square 3)
;Value: 9

להלן הגדרות פונקציות עבור פונקצית העצרת (!), פונקצית מחלק משותף מקסימלי (gcd), פונקצית פיבונאצ'י ופונקצית אקרמן:

 (define fac 
      (lambda (n) 
              (if (= n 0) 
                     1 
                     (* n (fac (- n 1)))))) 
 
 
(define fib 
      (lambda (n) 
          (if (= n 0) 
                 0 
                 (if (= n 1) 
                       1 
                       (+ (fib (- n 1)) (fib (- n 2))))))) 
 
 
 (define ack 
      (lambda (m n) 
           (if (= m 0) 
                (+ n 1) 
                (if (= n 0) 
                      (ack (- m 1) 1) 
                      (ack (- m 1) (ack m (- n 1))))))) 
 
 
 (define gcd 
      (lambda (a b) 
           (if (= a b) 
                  a 
                  (if (> a b) 
                        (gcd (- a b) b) 
                        (gcd a (- b a))))))

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

 (define sum 
       (lambda (l) 
             (if (null? l) 
                      0 
                      (+ (car l) (sum (cdr l)))))) 


 (define product 
       (lambda (l) 
             (if (null? l) 
                      1 
                      (* (car l) (sum (cdr l)))))) 


 (define length 
       (lambda (l) 
               (if (null? l) 
                        0 
                        (+ 1 (length (cdr l)))))) 


(define reverse 
      (lambda (l) 
            (if (null? l) 
                     nil 
                     (append (reverse (cdr l)) (list (car l))))))

הגדרות מקוננות

Scheme מספקת אפשרות להגדרות מקומיות ע"י כך שמאפשרת להגדרות להיות מקוננות. הגדרות מקומיות מוצגות ע"י שימוש בפונקציות letrec ,*let ,let.
התחביר עבור פונקציות define מורחב כדי לאפשר הגדרות מקומיות.
התחביר עבור פונקציות define ופונקציות let הוא כדלהלן:

תחביר Scheme

E - מייצג ביטויים
I - מייצג משתנים
B - מייצג קשרים

E ::= (lambda (I...) E... ) |
(let Bo Eo) | (let* B1 E1) | (letrec B2 E2) |...
B ::= ((I E)...)

שים לב כי יכולה להיות סדרה של קשרים. למטרת ייעול, הקשרים מפורשים באופן שונה אחד מהשני ע"י פונקצית ה-let. ערכי ה let מחושבים במקביל ליצירת הקשרים מה שגורם לאי תלות ההגדרות.
לגבי *let, הערכים והקשרים מחושבים באופן סדרתי מה שגורם לכך שהגדרה מאוחרת יותר אולי תהיה תלויה בקודמות לה.
לגבי letrec, הקשרים הינם בתוקף כל עוד הערכים מחושבים כדי לאפשר הגדרות רקורסיביות הדדיות.

לצורך הדגמת הגדרות מקומיות להלן הגדרת מיון הכנסה (insertion sort) עם פונקצית הכנסה (insert) המוגדרת מקומית. שים לב כי הגוף של isort מכיל שני ביטויים:
הראשון הוא ביטוי letrec, והשני הוא הביטוי שערכו צריך להיות מוחזר.

(define isort (lambda (l)
        (letrec
           ((insert  (lambda (x l)
              (if (null? l)
                 (list x)
                 (if (<= x (car l))
                    (cons x l)
                    (cons (car l) (insert x (cdr l)))))))))

        (if (null? l)
                nil
                (insert (car l) (isort (cdr l))))))

אנו משתמשים ב-letrec מאחר ו-insert מוגדר רקורסיבית.
להלן מספר דוגמאות נוספות:

 ; this binds x to 5 and yields  10
(let ((x 5)) (* x 2))
; this bind x to 10, z to 5 and yields 50.
(let ((x 10) (z 5)) (* x z))

let יכולה להיות מקוננת. לדוגמא, הביטוי הבא ערכו 18:

(let ((a 3) (b 4) 
    (let ((double (* 2 a)) (triple (* 3 b))) (+ double triple))))