Fplists

N на брой задачи за списъци, които всеки трябва да реши ;)


Няма да ви убеждавам, че Scheme е най-великият език на света(защото не е :)), нито ще пиша, че "Ако не разбираш Scheme, ти си един тъп Javar!". Агресията е за през друг час на деня :)
Та ако ви е интересна функционалната парадигма и искате да порешавате малко задачи (в частност свързани със списъци) - добре сте дошли :)


Основни функции, с които ще работим

Няма как да минем без car, cdr, cons, list + няколко предиката като null? и list?.
Какво е списък ще си прочетете в учебниците/лекциите. Тук ще го караме на интуитивно ниво.

В Scheme, списъците се създават по следния начин:

> (list 1 2 3)
(1 2 3)

Или със шорткът-а

> '(1 2 3) ; апострофче и скоби
(1 2 3)

car взима главата на списъка, а cdr - всичко от главата назад (опашката) - те ще са основния инструмент за създаване на рекурсивните функции, с които ще оперираме в/у списъци.

> (car (list 1 2 3))
1
> (cdr (list 1 2 3))
(2 3)

null? проверява дали списъкът е празен, а list? дали аргумента е списък(не е атом)

> (null? '())
#t
> (null? '(1 2 3))
#f
> (list? 1337)
#f
> (list? (list 1))
#t

Задачи

Ще започнем с най-основните и лесни задачки :)

Намиране на i-ти елемент

Това е просто. Просто като рекурсията ;)

(define
  (get-ith list i)
  (if(= i 0)  ;дъно, стигнали сме до търсения елемент
     (car list) 
     (get-ith (cdr list) (- i 1))
  )
)

Намиране на дължина на списък

Тук прилагаме подобна акробатика.

(define 
  (len list)
  (if(null? list) 
   0 
   (+ (len (cdr list)) 1)
  )
)

Слепване на два списъка

Тази задача е полезна и се използва в доста други :)

(define 
  (app list1 list2)
   (if(null? list1) list2 ;дъното е, когато сме изчерпали първия списък
   (cons (car list1) (app (cdr list1) list2))
   )
)

Слепване на всички списъци в даден списък

Тази задача е малко по-труден вариант на горната.
При дадено

(list (list 1 2 3) (list 4 5 6))

Функцията трябва да върне (1 2 3 4 5 6)
Ще използваме вече написаният app от по-горе
; appends all lists in the given list
(define
  (app-all list-of-lists)
  (define 
    (app-all-inner list-of-lists result) ;вътрешна функция с втори параметър, за да пазим резултатния списък
      (if(null? list-of-lists) result
        (app-all-inner (cdr list-of-lists) (app result (car list-of-lists)))
      ) 
   )
  (app-all-inner list-of-lists '())
)

Обръщане на списък

Вход : (rev '(1 2 3))
Изход : (3 2 1)

На пръв поглед, задачата изглежда тежка, защото в Scheme няма хубав начин да лепиш елементи отзад в даден списък.
За да решим задачата, ще използваме опашкова рекурсия, като в един от параметрите ще пазим обърнатия списък.
(define (rev list) 
  (define (rev-inner list result) ; В result ще  натрупваме обърнатия списък
    (if(null? list) result
       (rev-inner (cdr list) 
                  (cons (car list) result))) ; при връщане от рекурсията, извикванията ще бъдат с елементите на списъка подредени отзад напред
   )
  (rev-inner list '())
)

Намиране на екстремален елемент (най-голям или най-малък)

Тази задачка е доста важна :) Отново ще използване вътрешна функция и опашкова рекурсия, за да пазим намерения до момента екстремален елемент.
Функцията изглежда по този начин :

; oper е или > или < в зависимост дали търсим най-големият или най-малкият елемент
(define (extreme list oper)
  (define (extreme-inner list oper element) ; в елемент ще пазим екстремалния до сега елемент
    (if(null? list) element 
       (if(oper (car list) element) 
          (extreme-inner (cdr list) oper (car list)) ; ако намерим нов екстремален елемент, запазваме го в променливата 
          (extreme-inner (cdr list) oper element)) ; иначе продължаваме рекурсията по списъка
       )
   ) ; край на вътрешната функция
  (if(null? list) 
     '() 
     (extreme-inner list oper (car list)))
)

И сега като имаме тази прекрасна функция, може да направим следното нещо:

Правене на списък от екстремалните елементи

Имаме списък от списъци, целта е да построим списък с всеки екстремален елемент от списъците.

Вход : (list-of-extremes (list (list 1 2 3) (list 1 5 6) (list 7 8 9)) <)
Изход : (1 1 7)

Нещото става лесно :)
(define (list-of-extremes list oper) 
  (if(null? list) '()
     (cons (extreme (car list) oper) (list-of-extremes (cdr list) oper)) ; тук строим списък като използваме стека на рекурсията. Възможно е да използваме и опашкова рекурсия
  )
)

Предикат за принадлежност на елемент към списък

Този предикат може да го има в повечето диалетки, но е важно да се знае как работи ;)
При дадени елемент и списък, връща #t, ако елемента се съдържа и #f ако го няма.
Реализация - обхождаме списъка и проверяваме всеки елемент ;)

(define (member? X list)
  (cond ((null? list) #f) ; не сме намерили ==> не се среща
        ((= (car list) X) #t)
        (else (member? X (cdr list)))
  )
)

Линеализиране на списък от списъци (по-известно като flatten)

Тази задачка е по-трудна от обичайното. Трябва да направим всички списъци от всякаква дълбочина на един.
От нас се изисква това:

Вход : (flatten (list (list 1 2 3 (list 1 2 3))))
Изход : (1 2 3 1 2 3)

Ще използваме app функцията за слепване на два списъка и специалната форма cond, защото с if ще стане грозно.
(define (flatten list)
  (cond ((null? list) '()) ; дъно на рекурсията
        ((list? (car list)) (app (flatten (car list)) (flatten (cdr list)))) ; тук влизаме рекурсивно на дълкобо в списъка
        (else (cons (car list) (flatten (cdr list)))) ; ако елементът не е списък, добавяме го и продължаваме по списъка
  )
)

Важната част е
((list? (car list)) (app (flatten (car list)) (flatten (cdr list))))

Първият аргумент на app ще влезе в дълбочина, а вторият ще продължи рекурсията до края на дадения списък.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License