План:

  • Преговор - cons, car и cdr
  • Списъци. Основни функции - list, length, nth, append
  • Функции от по-висок ред за работа със списъци - fold, filter, map
  • Функции с променлив брой аргументи (varargs)
  • Threading macros - -> и ->>


Задача 1: Имплементирайте функциите (length lst), (nth lst index) и (append lst1 lst2).


Задача 2: Имплементирайте функцията (reverse lst).

(reverse (list 1 2 3)) ; => (3 2 1)


Задача 3: Имплементирайте функцията (map f lst).

(map square (list 1 2 3)) ; => (1 4 9)


Задача 4: Имплементирайте функцията (filter pred lst).

(filter odd? (list 1 2 3)) ; => (1 3)


Задача 5: Имплементирайте функциите (fold f val lst) и (fold1 f lst).

(fold + 0 (list 1 2 3)) ; => 6
(fold1 + (list 1 2 3)) ; => 6
(fold1 + (list 1)) ; => 1
(fold1 + ()) ; => #f


Задача 6: Имплементирайте функциите (index-of lst val) и (last-index-of lst val). За сравняване използвайте предиката (equal? val1 val2).

(index-of (list 0 1 2 3 1) 1) ; => 1
(last-index-of (list 0 1 2 3 1) 1) ; => 4


Задача 7: Имплементирайте функциите (distinct? lst) и (distinct lst).

(distinct? (list 1 2 3 4)) ; => #t
(distinct? (list 1 2 3 2)) ; => #f
(distinct (list 1 2 3 2)) ; => (1 2 3)


Задача 8: Имплементирайте функциите (every? pred lst) и (any? pred lst).

(every? odd? (list 1 2 3)) ; => #f
(every? odd? (list 1 5 3)) ; => #t
(any? even? (list 1 2 3)) ; => #t
(any? even? (list 1 5 3)) ; => #f


Задача 9: Имплементирайте функцията (range n), която връща списък с числата от 1 до n.

(range 5) ; => (0 1 2 3 4)


Задача 10: Имплементирайте функциите (take n lst) и (drop n lst).

(take 5 (range 100)) ; => (0 1 2 3 4)
(take 100 (range 3)) ; => (0 1 2)
(drop 20 (range 23)) ; => (20 21 22)
(drop 20 (range 10)) ; => ()


Задача 11: Имплементирайте функцията (remove lst val), която премахва всички срещания на val в списъка lst.

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


Задача 12: Имплементирайте функцията (sort lst), която сортира списъка lst чрез вмъкване.

(sort (list 1 9 7 4 6)) ; => (1 4 6 7 9)


Задача 13: Имплементирайте функцията (compose . fns), която връща композицията на подадените аргументи.

(define f (compose double square inc)) ; 2 * (x + 1)^2
(f 3) ; => 32
(f 4) ; => 50


Задача 14: Имплементирайте функцията (flip fn), която обръща реда на аргументите на функцията fn незвисимо от броя им.

(define list^ (flip list))
(list^ 1 2 3) ; => (3 2 1)


Задача 15: Имплементирайте по-общ вариант на функцията (map fn . lsts), която прилага fn с аргументи поредните елемени на списъците докато някой от тях не се  изчерпа.

(map + (list 1 2 3) (list 4 5 6) (list 7 8 9)) ; => (12 15 18)
(map cons (list 1 3 5) (list 2 4 6 8 10 12)) ; => ((1 . 2) (3 . 4) (5 . 6))


Задача 16: Имплементирайте функцията (juxt . fns) (от англ. juxtaposition - съпоставяне). Резултатът от (juxt f g h ...) e функция с променлив брой аргументи, която връща списък с резултатите от прилагането на всяка една от функциите f, g, h ... въргу тези аргументи.

(define f (juxt inc dec square double)) ; (f x) = (list (inc x) (dec x) (square x) (double x))
(f 5) ; => (6 4 25 10)

(define g (juxt + *))
(g 3 4 5) ; => (12 60)



Бонус: Threading macros

Макросите в Scheme ни позволяват да дефинираме свои специални форми, като сами указваме как да се интерпретират. Те трансформират кода преди той да бъде оценен. Голяма част от специалните форми в Scheme са дефинирани именно като макроси - and, or, cond, let ...

(%macroexpand
  (cond (test-1 expr-1)
        (test-2 expr-2)
        (test-3 expr-3)
        (else default-expr)))
; => (if test-1 expr-1 (if test-2 expr-2 (if test-3 expr-3 default-expr)))

(%macroexpand
  (let ((x (+ 1 2))
        (y (- 5 1)))
    (* x y)))
; => ((lambda (y x) (* x y)) (- 5 1) (+ 1 2))

(%macroexpand
  (%macroexpand something))
; => (quote something)


Да разгледаме следния проблем - искаме да намерим сумата от квадратите на нечетните числа от 1 до 9. Едно възможно решение е следното: (sum (map square (filter odd? (range 10)))). Когато оценяваме израза, обаче, трябва да го четем наобратно - вземи числото 10, подай го на range, резултатът филтрирай с помощта на odd?, повдигни числата на квадрат и накрая сумирай чрез sum. Понякога е по-удобно да описваме тези трансформации точно от ляво надясно, например:

(->> 10 range (filter odd?) (map square) sum)


Макросът ->> трансформира горния израз точно по следния начин:

(sum (map square (filter odd? (range 10))))


Разликата между -> и ->> е в позицията, на която се вмъква резултатът от предишната операция във веригата:

(-> 4 (- 1) (* 2) (/ 3)) ; => 2
(%macroexpand (-> 4 (- 1) (* 2) (/ 3)))
; => (/ (* (- 4 1) 2) 3)

(->> 4 (- 1) (* 2) (/ 3)) ; => -0.5
(%macroexpand (->> 4 (- 1) (* 2) (/ 3)))
; => (/ 3 (* 2 (- 1 4)))


Имплементация:

;; Thread-first
(define-macro (-> x . forms)
  (if (null? forms)
      x
      (let ((form (car forms)))
        (if (list? form)
            `(-> (,(car form) ,x ,@(cdr form)) ,@(cdr forms))
            `(-> (,form ,x) ,@(cdr forms))))))

;; Thread-last
(define-macro (->> x . forms)
  (if (null? forms)
      x
      (let ((form (car forms)))
        (if (list? form)
            `(->> (,@form ,x) ,@(cdr forms))
            `(->> (,form ,x) ,@(cdr forms))))))



Последно модифициране: понеделник, 31 октомври 2016, 18:15