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.)

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? :-PStandard Scheme Lists 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 1 Standard Scheme Lists 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.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 1 Standard Scheme Lists 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))))

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 1 Standard Scheme Lists 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.)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 Scheme Lists 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:

Post a Comment