Scheme function

Question

I am trying to interpret what this scheme function does:

 (define (y s lis)
    (cond
      ((null? lis) '() )
      ((equal? s (car lis)) lis)
      (else (y s (cdr lis)))))

It runs but I am not exactly sure what it is doing or trying to do. Does it need a list to sort or something? I am using DrRacket to run it. I have never seen scheme before and any help would be greatly appreciated.

Answer 1

It's a search function, that given a value and a list looks for the value in the list. If it finds it, returns the part of the list starting at the point where the element was found. If the value isn't in the list, it returns an empty list. Let's see how this works, step by step:

; define a function called `y` that receives
; as parameters a value `s` and a list `lis`
(define (y s lis)
  ; we're going to test three possible conditions
  (cond
    ; if the list is empty    
    ((null? lis)
     ; then we didn't find the value, return the empty list
     '())
    ; if the first element in the list equals the `s` value
    ((equal? s (car lis))
     ; then return the list up to this point
     lis)
    ; otherwise
    (else
     ; keep looking in the rest of the list, by recurring over it
     (y s (cdr lis)))))

To see the function in action, let's test it with some values:

; call the function with a value that is present in the list
(y 3 '(1 2 3 4 5))
; see how the list is returned starting at the point where the value was found
=> '(3 4 5)

; call the function with a value that is not present in the list
(y 7 '(1 2 3 4 5))
; an empty list is returned
=> '()

To really, really understand how this works, you have to realize that in the last line of the function we're calling the function itself - it's the magic of recursion! Also, it'll help you to understand what each one of the primitive operations used is doing, click on each link to read the documentation, I'm simplifying and summarizing the key points:

• define: give a name to a value (in particular, it can be a function)
• cond: test for different conditions, execute some expressions depending on which condition was true
• null?: test to see if a list is empty
• equal?: compare two objects for equality
• car: get the first element in a list
• cdr: get the rest of the elements in a list

Answer 2

We can go on a mystic journey and treat this definition as it is, a definition. Cryptic? This means equational reasoning, i.e. reasoning through equations, i.e. definitions. Here's what I mean. You have

(define (y s lis)
   (cond
      ((null? lis) '() )
      ((equal? s (car lis)) lis)
      (else (y s (cdr lis)))))

We can re-write this as two equations,

y s lis = lis             , if (null? lis) || (equal? s (car lis))
        = y s (cdr lis)   , otherwise

Here y s lis stands for "the result of Scheme call (y s lis)" and so on.

Clearly we have two cases. One is base case, another describes a reduction step. Re-writing again,

y s lis = y s (cdr lis)   , if (not (null? lis)) && (not (equal? s (car lis)))
        = lis             , otherwise

This is practically in English now. So while lis is not null, and its car isn't s, we proceed along to its cdr, and so on and so forth until either we hit the list's end, or its car is s, and then we stop. So when we've found s, we return the list, otherwise the list is exhausted and the empty list is returned. This is otherwise known as member in Common Lisp. R5RS Scheme's member, as well as Racket's, returns #f when no x is found in the list.

Where is the equational reasoning here, you ask? In treating the RHS as the answer, and re-applying the same set of rules for each reduction step. For example:

y x [a,b,x,c,d,e]                         ; A
    = y x [b,x,c,d,e]    ; by 1st rule    ; B
    = y x [x,c,d,e]      ; by 1st rule    ; C
    = [x,c,d,e]          ; by 2nd rule    ; D

When we get to apply the 2nd rule, we arrive at the end of the reduction chain, i.e. we get our answer. The result of the Scheme call corresponding to A will be the same as the Scheme call's corresponding to B, or C, or finally D:

(y x (cons a (cons b (cons x z)))) ==
(y x (cons b (cons x z))) ==
(y x (cons x z)) ==
(cons x z)

What's so mystic about it, you ask? Here probably not much; but usually what that means is that by assuming the meaning of a function, and by interpreting the RHS through it, we arrive at the meaning of the LHS; and if this is the same meaning, that is our proof for it. Induction is kind of magical. For more involved examples see How to recursively reverse a list using only basic operations?.

Incidentally structural recursion is also known as folding, so your function is really

y s lis = para (λ (xs x r) (if (equal? x s) xs (r))) '() lis   

using one type of folding, paramorphism, with explicit laziness,

para f z lis = g lis 
  where 
     g xs = z                                  , if (null? xs)
          = f xs (car xs) (λ () (g (cdr xs)))  , otherwise

Answer 3

I think its a test to see if element s is found inside the list lst. I'm still learning Scheme (but I did get through The Little Schemer so let me try (this has likely been typed and submitted before I I finish this but I'll try anyways).

So define is creating a function called y that takes the arguments s and lst. The first line of this function is cond which goes though each list and tries to find some expression that evaluates to true. The first condition is the exit condition (always have an exit when you iterate) it checks to see if lis is null, if so it returns a quoted empty list (like the null of lists)

The next condition looks to see if the first element of lst (car takes the first element of a list) equals s if so then it returns the rest f the list (this means it found the element).

The last condition is else which is alway true and it calls the function y with the same s and the list minus the first element (cdr returns a sublist of the list minus the first element). Hope this helps (and I hope I was right)

Here is an example of calling this function:

(y 'b (list 'a 'b 'c))

And this returns

('b 'c)

Answer 4

Looks like homework.

Since you are using DrRacket you should add

(y 'e '(q w e r t y))

And hit Debug Q >| and step through it. A different way to write the same code is:

(define (y s lis)
  (if (null? lis) 
      '()
      (if (equal? s (car lis)) 
          lis
          (y s (cdr lis)))))

Or you can choose Intermediate student with lambda from the language menu in the bottom left and then press Step >|. That language doesn't support all of Scheme but a small subset, including everything in this procedure. It's great to see how things are evaluated.