assoc-equivalent процедура не функционира правилно

Опитвам се да напиша процедура, подобна на Scheme's assoc. Единствената разлика между двете е, че искам моята процедура да връща само стойността, свързана с дадения ключ, където assoc дава цялата двойка (ключ. стойност). Ето моята процедура:

(define alist '((a . 1) (b . 2) (c . 3)))

(define (search-list key list)
  (cond ((null? key) #f)
        ((eq? (caar list) key) (cdar list))
        ((null? (cdr list)) #f)
        (else search-list key (cdr list))))

Изглежда съм на прав път -- (search-list 'a alist) връща 1. Въпреки това, когато тествам с (search-list 'b alist), това е моят резултат: ((b . 2) (c . 3 ))

Не мога да разбера защо моята процедура не функционира, както възнамерявам. Много ще се радвам, ако ми посочите грешката в моята процедура. Благодаря предварително.


associative-array scheme r5rs
person Henrik Hillestad Løvold    schedule 21.05.2014    source източник

Отговори (3)


arrow_upward
2
arrow_downward

Открихте грешката си, но бих предложил други промени:

1) трябва да проверите дали списъкът е празен, преди да използвате caar и други подобни, защото вашата процедура ще се провали, когато се извика с празен списък.

2) OTOH, няма нужда да проверявате дали ключът е нула.

3) В Scheme не трябва да използвате list като име на параметър, за да не засенчвате процедурата list.

Така че бих избрал

(define (search-list key lst)
  (cond
    ((null? lst) #f)
    ((eq? key (caar lst)) (cdar lst))
    (else (search-list key (cdr lst)))))
person uselpa    schedule 21.05.2014
comment
Благодаря ви за приноса! - person Henrik Hillestad Løvold; 21.05.2014

arrow_upward
0
arrow_downward

Проблемът беше извикването (или по-скоро липсващото повикване) към списък за търсене на последния ред. Тъй като това не беше обвито в скоби, процедурата никога не беше рекурсивно извикана и процедурата върна (cdr list) вместо (search-list key (cdr list)). Този код работи по предназначение:

(define alist '((a . 1) (b . 2) (c . 3)))

(define (search-list key list)
  (cond ((null? key) #f)
        ((eq? (caar list) key) (cdar list))
        ((null? (cdr list)) #f)
        (else (search-list key (cdr list)))))
person Henrik Hillestad Løvold    schedule 21.05.2014

arrow_upward
0
arrow_downward

Обърнете внимание, че не искате точно поведението на assq (което assoc използва eq?, а не equal?), но все пак можете да използвате assq в изпълнението:

(define (search-list key lst)
  (cond ((assq key lst) => cdr)
        (else #f)))

> (search-list 'b '((a . 1) (b . 2) (c . 3)))
2

Освен това вашият съществуващ код ще има проблеми със списък от '(), защото caar ще се провали. Обикновено в рекурсивните алгоритми основният случай, който е (null? lst) във вашия случай, се тества първо.

person GoZoner    schedule 21.05.2014