эквивалентная процедура assoc не работает должным образом

Я пытаюсь написать процедуру, аналогичную процедуре Scheme assoc. Единственная разница между ними заключается в том, что я хочу, чтобы моя процедура возвращала только значение, связанное с заданным ключом, где as assoc дает всю пару (key . value). Вот моя процедура:

(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) В Схеме не следует использовать 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

Проблема заключалась в вызове (или, скорее, в отсутствующем вызове) search-list в последней строке. Поскольку это не было заключено в круглые скобки, процедура никогда не вызывалась рекурсивно, и процедура возвращала (список cdr) вместо (ключ списка поиска (список cdr)). Этот код работает по назначению:

(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