28/05/2008

Lists and Lists: tail recursive fun

So, who's played Andrew Plotkin's Lists and Lists? It's a Scheme tutorial, and it's written in Inform, a language used to author interactive fiction.

What I find cool is that, despite (intentionally) being written for a platform not designed to host a programming language interpreter, Lists and Lists is exactly that—a very flexible interpreter, that allows you to write whatever program you like to solve its challenges. It simply verifies your programs according to the problem criteria, and you are not required to solve the problems ‘any particular way’.

Lists and Lists also has sample solutions, if you type help enough times for a given problem. These sample solutions are designed to be easy for beginners to understand, but are not necessarily optimised for any other criterion. So, variety being the spice of life and all, I've decided to post my answers to some of the questions. (I'm currently learning Scheme, so these are by no means any sort of ‘optimal’.)

My particular aim with my answers is that they should be tail recursive, so that when given a very large list to process, the programs don't use up huge amounts of stack.

In standard Scheme, the ‘named let’ syntax makes tail-recursive programs quite readable; sadly, this functionality is not available in Lists and Lists, so I also present my solution in both ‘formats’. Additionally, for extra functional-programming goodness, I present SRFI 1 versions where available.

(Sorry about the funny line wrapping; I wanted to help the two-column format display correctly on a variety of screen widths. I used Emacs to do the indentation, so hopefully the result is readable.)

  1. Define sum to be a function that adds up a list of integers. So (sum '(8 2 3)) should return 13. Make sure it works correctly for the empty list; (sum nil) should return 0.

    My approach here is: Why rewrite the + function when you can reuse it? Or, why take the high road when you can take the cheap road? :-P

    Standard SchemeLists and Lists
    (define (sum l)
      (apply + l))
    
    (define sum 
      (lambda (l)
        (eval (cons + l))))
    

    Okay, if I must actually write an iterative solution (if only so that we have something to compare the next problem against):

    SRFI 1Standard SchemeLists and Lists
    (define (sum l)
      (reduce + 0 l))
    
    (define (sum l)
      (let next ((sum 0) (tail l))
        (if (null? tail) sum
            (next (+ sum (car tail))
                  (cdr tail)))))
    
    (define sum
      (lambda (l)
        (letrec
            ((next 
              (lambda (sum tail)
                (cond
                 ((null? tail) sum)
                 (t (next (+ sum (car tail))
                          (cdr tail)))))))
          (next 0 l))))
    

    Yes, I quite deliberately reused the symbol sum, just to demonstrate that I'm not using sum to recurse. You can't, anyway, if you want a tail-recursive solution.

  2. This problem is like the last one, but more general. Define megasum to add up an arbitrarily nested list of integers. That is, (megasum '((8) 5 (2 () (9 1) 3))) should return 28.

    This solution is similar to the last one, but I'm not assuming that tail is a list, and more specifically, I only do the adding when I'm not dealing with a list. When I encounter a list, I just recurse; this catches cases where (car tail) is a list.

    SRFI 1Standard SchemeLists and Lists
    (define (megasum l)
      (let mega+ ((elem l) (sum 0))
        (cond
         ((null? elem) sum)
         ((list? elem) (fold mega+ sum elem))
         (else (+ elem sum)))))
    
    (define (megasum l)
      (let next ((sum 0) (tail l))
        (cond
         ((null? tail) sum)
         ((list? tail) 
          (next (next sum (car tail))
                (cdr tail)))
         (else (+ sum tail)))))
    
    (define megasum 
      (lambda (l)
        (letrec
            ((next 
              (lambda (sum tail)
                (cond
                 ((null? tail) sum)
                 ((list? tail) 
                  (next (next sum (car tail))
                        (cdr tail)))
                 (t (+ sum tail))))))
          (next 0 l))))
    
  3. Define max to be a function that finds the maximum of a list of integers. So (max '(5 14 -3)) should return 14. You can assume the list will have at least one term.

    My solution uses a pairmax helper function that simply returns the maximum between any two quantities.

    SRFI 1Standard SchemeLists and Lists
    (define (max l)
      (define (pairmax a b)
        (if (> a b) a b))
      (reduce pairmax #f l))
    
    (define (max l)
      (define (pairmax a b)
        (if (> a b) a b))
      (let next 
          ((best (car l)) (tail (cdr l)))
        (if (null? tail) best
            (next (pairmax best (car tail))
                  (cdr tail)))))
    
    (define max 
      (lambda (l)
        (letrec
            ((pairmax 
              (lambda (a b)
                (cond
                 ((> a b) a)
                 (t b))))
             (next 
              (lambda (best tail)
                (cond
                 ((null? tail) best)
                 (t (next (pairmax best (car tail))
                          (cdr tail)))))))
          (next (car l) (cdr l)))))
    

    You'll notice a pattern here, that there is a fairly mechanical way I'm translating from the original program to the Lists and Lists-compatible version. In fact, when tested with Guile, its macro expander actually expanded the named-let blocks on the left into something quite similar to the letrec blocks on the right.

    (Of course, in this problem, since Lists and Lists does not support internal define, the equivalent letrec is used instead.)

  4. Last problem. You're going to define a function called pocket. This function should take one argument. Now pay attention here: pocket does two different things, depending on the argument. If you give it nil as the argument, it should simply return 8. But if you give pocket any integer as an argument, it should return a new pocket function—a function just like pocket, but with that new integer hidden inside, replacing the 8.

    >>(pocket nil)
    8
    >>(pocket 12)
    [function]
    >>(define newpocket (pocket 12))
    [function]
    >>(newpocket nil)
    12
    >>(define thirdpocket (newpocket 3))
    [function]
    >>(thirdpocket nil)
    3
    >>(newpocket nil)
    12
    >>(pocket nil)
    8
    

    Note that when you create a new pocket function, previously-existing functions should keep working.

    My solution is pretty much the same as Lists and Lists' sample solution (just how many ways can you solve this one?!), just using a named let.

    Standard SchemeLists and Lists
    (define pocket
      (let construct ((num 8))
        (lambda (x)
          (if (null? x) num (construct x)))))
    
    (define pocket 
      (letrec
          ((construct 
            (lambda (num)
              (lambda (x)
                (cond
                 ((null? x) num)
                 ((construct x)))))))
        (construct 8)))
    

So, there you go. Feel free to comment with any corrections, improved answers, or whatever ideas you have. :-)

No comments: