search through nested list in scheme to find a num

问题:

How would I search through the nested list to find a certain number?

For example, the list is:

((1 2) (2 3) (3 4) (3 5) (4 5))

and I'm looking for 1.

Expected output:

(1 2)

since 1 is in the sub list (1 2).

回答1:

First of all create function to flatten list. Something like this:

> (flatten '((8) 4 ((7 4) 5) ((())) (((6))) 7 2 ()))
(8 4 7 4 5 6 7 2)

And then search your number in the ordinary list.

This quesion looks like the homework so try to develop this function on your own and if you can not do it - post your code here and I'll try to help you.

Updated

Ok. As I understand we need to create function which get the list of pairs and return another list of pairs, where first element of pair equal some number.

For example:

(define data '((1 2)(2 3)(3 4)(3 5)(4 5)))
(solution data 3)
-> '((3 4) (3 5))

(define data '((1 2)(2 3)(3 4)(3 5)(4 5)))
(solution data 1)
-> '((1 2))

In the other words we need to filter our list of pairs by some condition. In the Scheme there is a function to filter list. It takes a list to filter and function to decide - to include or not the element of list in the result list.

So we need to create such function:

(define (check-pair num p)
  (cond 
    [(= (first p) num) #t]
    [else #f]))

This function get a pair (element of list), number and decide - incude or not this pair to result list. This function have 2 parameters, but the filter function require the function with only one parameter, so we rewrite our function such way:

(define (check-pair num)
  (lambda (p)
    (cond 
      [(= (first p) num) #t]
      [else #f])))

I have created function wich produce another function. It is currying.

So, we have all to create our solution:

(define (check-pair num)
  (lambda (p)
    (cond 
      [(= (first p) num) #t]
      [else #f])))

(define (solution list num)
  (local 
    ((define check-pair-by-num (check-pair num)))
    (filter check-pair-by-num list)))

(define data '((1 2)(2 3)(3 4)(3 5)(4 5)))

(solution data 1)

回答2:

Flattening isn't the approach I'd prefer here, but that doesn't mean it's incorrect. Here's an alternative:

    (define (solve lst num)
      (cond 
        [(null? lst) null]
        [(cons? (first lst)) (solve (first lst) num)]
        [(member num lst) (cons lst (solve (rest lst) num))]
        [#t (solve (rest lst) num)]))

This just recursively deals with nested listing as needed, so I prefer it a little bit stylistically. In addition, the call to member can be replaced with check-pair from above, but member will let you grab values from cdrs as well as cars, if you want that.

回答3:

Use find to select a member of a list meeting a condition:

(find contains-1? '((1 2)(2 3)(3 4)(5 6)))

How to implement contains-1? Hint: consider the member function:

(member 1 '(1 2)) => #t
(member 1 '(3 4)) => #f