Scheme homework help

Question

Okay so I have started a new language in class. We are learning Scheme and i'm not sure on how to do it. When I say learning a new language, I mean thrown a homework and told to figure it out. A couple of them have got me stumped.

My first problem is:

Write a Scheme function that returns true (the Boolean constant #t) ifthe parameter is a list containing n a's followed by n b's. and false otherwise.

Here's what I have right now:

(define aequalb
  (lambda (list)
    (let ((head (car list)) (tail (cdr list)))
      (if (= 'a head)
          ((let ((count (count + 1)))
             (let ((newTail (aequalb tail))))
             #f
             (if (= 'b head)
                 ((let ((count (count - 1)))
                    (let ((newTail (aequalb tail))))
                    #f
                    (if (null? tail)
                        (if (= count 0)
                            #t
                            #f)))))))))))

I know this is completely wrong, but I've been trying so please take it easy on me. Any help would be much appreciated.

Answer 1

Isn't list a keyword? I always used to use "alist" as my variable name to get around it.

You could use counters like you are, but I might go for a recursive function that has the following conditions:

params: alist

returns true if the list is nil,

false if the first element is not a,

false if the last element is not b,

(aequalb (reverse (cdr (reverse (cdr alist))))) ;; pick off the front and back, and recurse

in this case, you may need to write a reverse function... can't remember if it was there already.

---

Also, from a syntax perspective, you don't need to introduce a lambda expression...

(define (foo arg) (+ 1 arg))

is a function called foo, takes a number, and adds one to it. You would call it (foo 1)

Answer 2

I'd take a look at andmap, take and drop, which (between them) make this pretty trivial. Oh and at least for now, I'd probably try to forget that let even exists. Not that there's anything particularly wrong with it, but I'd guess most of the problems you're going to get (at least for a while) don't/won't require it.

Answer 3

A trick I picked up from Essentials of Programming Languages is to always write recursive list functions by handling the two important cases first: null (end of list) and not null.

So, the basic structure of a list function looks something like this:

(define some-list-function 
  (lambda (list)
    (if (null? list)
        #f
        (do-some-work-here (head list)
                           (some-list-function (tail list))))))

Usually you (1) check for null (2) do some work on the head and (3) recur on the tail.

The first thing you need to do is decide what the answer is for a null list. It's either #t or #f, but which? Does a null list have the same number of a as b?

Next, you need to do something about the recursive case. Your basic approach is pretty good (although your example code is wrong): keep a count that goes up when you see a and down when you see b. The problem is how to keep track of the count. Scheme doesn't have loops* so you have to do everything with recursion. That means you'll need to pass along an extra counter variable.

(define some-list-function 
  (lambda (list counter)
    (if (null? list)
        ; skip null's code for a second

Now you have to decide whether the head is 'a or not and increment count if so (decrement otherwise). But there's no count variable, just passing between functions. So how to do it?

Well, you have to update it in-line, like so:

(some-list-function (tail list) (+ 1 count))

By the way, don't use = for anything but numbers. The newer, cooler Lisps allow it, but Scheme requires you to use eq? for symbols and = for numbers. So for your 'a vs 'b test, you'll need

(if (eq? 'a (head tail)) ...)
; not
(if (= 'a (head tail)) ...)

I hope this helps. I think I gave you all the pieces, although there are a few things I skipped over. You need to change the null case now to check count. If it's not = 0 at the end, the answer is false.

You should also maintain a separate flag variable to make sure that once you switched to 'b, you return #f if you see another 'a. That way a list like '(a a a b b a b b) won't pass by mistake. Add the flag the same way I added counter above, by adding another function parameter and passing along the value at each recursive call.

Finally, if your teacher really isn't giving you any help, and won't, then you might want to read a basic book on Scheme. I haven't used any of these myself, but I've heard they're good: The Scheme Programming Language, How to Design Programs or err umm I thought there was a third book online for free, but I can't find it now. I guess if you have lots of extra time and want to blow your mind, you can read Structure and Interpretation of Computer Programs. It teaches a little Scheme and lot about programming languages.

*It does have some of these things, but it's better to ignore them for now.

Answer 4

Here's a first-cut that may help you. It handles the basic problem, although you need to test to make sure there are no edge cases.

Anyway, the function checks several conditions:

• It first checks a base case (recursive functions need to have this, to avoid the possibility of infinite recursion). If the input list is empty then return true (assumption is that all items have been removed, so at this point we are done).

• Then the code checks to see if the first items is an a and the last is a b. If so, it strips these chars off and recurses.

• Otherwise something is wrong, so the function returns false

    (define (aeqb items)
     (cond
      ((equal? '() items) #t)
      ((and (equal? "a" (car items))
             (equal? "b" (car (reverse items))))
           (aeqb (cdr (reverse (cdr (reverse items)))))) 
      (else #f)))

    (aeqb '("a" "a" "b" "b"))