Функционално програмиране (И) 2015/16

Това е третото и последно домашно на Scheme за всички студенти, които посещават упражненията на гр.1 и гр.2. Срокът е две седмици, но можете да го приемете като упражнение преди голямото контролно. Отново са позволени многократни предавания и ще давам обратна връзка в рамките на същия ден. Моля, предавайте всички задачи в един файл (името му няма значение).

Употребата на функциите от по-висок ред accumulate, map, filter, apply е позволена, но не е задължителна. Задачи 2,3,5 и бонуса могат да се решат сравнително просто, използвайки някои от тях.

Навсякъде, където извършвате някакви сравнения, използвайте предиката equal? - само в задачи 2 и 3 е гарантирано, че елементите на списъците са числа. Използвайте дадените примери за разбиране на задачата, както и за тестване (макар и непълно) на вашите решения

Зад.1. Да се напише функция (mash f g lst), която приема две едноаргументи функции и един списък и прилага f и g върху елементите на списъка, като ги редува:
(define (f1 x) (* x 10))
(define f2 prime?)
(mash f1 f2 '(1 2 3 4 5)) -> (10 #t 30 #f 50)

Зад.2. Да се напише функция (insert-after-evens x lst), която вмъква числото x след всяко четно число в простия списък от числа lst:
(insert-after-evens 10 '(1 2 3 4 5)) -> (1 2 10 3 4 10 5)

Зад.3. Да се напише функция (insert-after-deep x lst), която вмъква числото x след всяко четно число в дълбокия списък от числа lst:
(insert-after-deep 10 '(1 ((2) 3 4) (((5))) 6 7)) -> (1 ((2 10) 3 4 10) (((5))) 6 10 7)

Зад.4. Да се напише функция (sublist? lst1 lst2), която проверява дали списъкът lst1 е подсписък на lst2 (аналогична на проверката за подстринг):
(sublist? '(2 3 4) '(1 2 3 4 5)) -> #t
(sublist? '(2 3 5) '(1 2 3 4 5)) -> #f ; тъй като търсените елементи не са последователни
(sublist? '(4 3 5) '(1 2 3 4 5)) -> #f
(sublist? '() '()) -> #t ;(!)

Упътване: можете да използвате помощна функция (begins-with? lst1 lst2), която да проверява дали списъка lst2 "започва със" списъка lst1:
(begins-with? '(2 3 4) '(2 3 4 5)) -> #t
(begins-with? '(2 3 4) '(2 3)) -> #f ;(!)

Зад.5. Да се напише функция (make-set lst), която взима произволен списък (вида на елементите му няма значение) и връща списък от същите елементи, без повторения.
Последователността на елементите в резултата няма значение, не се гони и сложност по време.
(make-set '(1 2 2 4 3 2 1 3 4)) -> (1 2 4 3)                               ; или друга тяхна пермутация
(make-set '("iei" 10 "oops" "iei" #t #t 10 #f)) -> ("iei" 10 "oops" #t #f) ; или друга тяхна пермутация

Бонус: Да се напише функция (descartes lst1 lst2), която намира декартовото произведение на два списъка - наредените двойки от всеки елемент на единия списък със всеки елемент на другия.
Последователността на елементите в резултата няма значение.
(descartes '(1 2 3) '(a b)) -> ((1 . a) (2 . a) (3 . a)
                                (1 . b) (2 . b) (3 . b)) ; или друга тяхна пермутация