Looking up pairing lists in scheme

Question

I am trying to write recursive scheme function that returns the binding (pair) whose name equals the given name. If no such binding is found return the null list. An association list is a list of bindings of names to values: ((name1 val1) ... (namet valuet)).

(define (lookup name assoc_list) 
  (cond
    ((null? assoc_list) '())
    ((equal? name (car (car assoc_list))) car(assoc_list))
    (else (lookup name (cdr L)))))

I tested it out with

(define l1 '( (ben "short") (cara "walking") (dan "bald")))
(lookup (car(car l1)) l1)

and it failed but if i do

(define (look name assoc_list) 
  (cond
   ((null? assoc_list) #f)
   ((equal? name (car (car assoc_list))) #t)
   (else (lookup name (cdr L)))))

and run this in scheme

(define l1 '( (ben "short") (cara "walking") (dan "bald")))
(lookup (car(car l1)) l1)

it returns #t

why wont it return the car(assoc_list) next im going to write a recursive function (lookup-env name environment), which returns the binding with the specified name in an environment (i.e. list of association lists) and null if no such binding is found

An environment can be represented by a list of association lists (i.e. a list of symbol tables), where the first element in the list is nearest scope, the second the next surrounding scope, and the last the outermost scope.

Answer 1

The procedure you're implementing already exists in some Scheme interpreters, and it's a good idea to reuse existing functionality (don't reinvent the wheel!). Thus the implementation of lookup can be as simple as this:

(define (lookup name assoc_list)
  (or (assoc name assoc_list) '()))

The trick, of course, is using assoc (which uses equal? for the comparisons) or a similar procedure, check your interpreter's documentation to discover other search procedures. We need to use or to handle the case where the binding was not found, because by default assoc returns #f in that case, but you need a '(). Let's test it - works as expected:

(define l1 '( (ben "short") (cara "walking") (dan "bald")))

(lookup 'ben l1)
=> '(ben "short")

(lookup 'tom l1)
=> '()

In case you want to implement the procedure from scratch, @uselpa's answer is spot-on: there was a problem with the brackets. Remember, to call a function in Scheme we must do this: (f x), not this: f(x).

Answer 2

Ah those parentheses ;-) It's (car assoc_list), not car(assoc_list):

(define (lookup name assoc_list) 
  (cond
    ((null? assoc_list) '())
    ((equal? name (car (car assoc_list))) (car assoc_list)) ; <------
    (else (lookup name (cdr assoc_list)))))

Note that you can simplify (car (car x)) to (caar x):

(define (lookup name assoc_list) 
  (cond
    ((null? assoc_list) '())
    ((equal? name (caar assoc_list)) (car assoc_list))
    (else (lookup name (cdr assoc_list)))))