functional programming is great, but why lists?

[Bill Richter <richter@math.nwu.edu>]

Here's a pedagogical question, particularly affecting the PLT mission
of teaching Scheme to high school students.

I'm perfectly sold on functional programming, i.e. no mutators.  But
cons/list seems pretty cumbersome.  Why not use functions instead?
For instance, there's a very elegant program `scramble' on p 15 of
"The Seasoned Schemer", .  The easiest way to describe what `scramble'
is by a function/non-list version of it:

(define (scramble-fun tup-fun)
  (lambda (n)
    (tup-fun (add1 (- n (tup-fun n))))))

i.e. it takes a function f and returns n |--> f(n - f(n) + 1).  Boom,
no problem.  But F & F's elegant solution with lists is:

(define (scramble-b tup rev-pre)
  (letrec ((pick (lambda (n lat)
                   (if (= n 1)
                       (car lat)
                       (pick (- n 1) (cdr lat))))))
    (if (null? tup)
        '()
        (cons (pick (car tup)
                    (cons (car tup) rev-pre))
              (scramble-b (cdr tup)
                          (cons (car tup) rev-pre))))))

(define (scramble tup)
  (scramble-b tup '()))

OK, it's a skill to learn how to write such function as `scramble' and
`scramble-b', and I'm not quite there yet, but I ask: what is the
point of developing such a skill?  I assume that we're really trying
to teach recursion (and I'm not quite there yet either), so is the
idea, "let's pick some arcane area where we can practice recursion"?

Actually showing my function was equivalent to F&F's took some work,
but the output indicates that I've got the same function:

Welcome to DrScheme, version 103p1.
Language: Graphical Full Scheme (MrEd).
(1 1 1 1 1 1 1 1 1)
(1 1 1 1 1 1 1 1 1)
(1 1 1 1 1 1 1 1 2 8 2)
(1 1 1 1 1 1 1 1 2 8 2)
(1 1 1 1 1 4 1 1 1 9)
(1 1 1 1 1 4 1 1 1 9)


(require-library "functio.ss")

(define (increment-function funny)
  (lambda (n)
    (funny (add1 n))))


(scramble '(1 2 3 4 5 6 7 8 9))

(define (tup-fun2 n)
  ;; (1 2 3 4 5 6 7 8 9)
  (cond ((= n 1) 1)
        ((= n 2) 2)
        ((= n 3) 3)
        ((= n 4) 4)
        ((= n 5) 5)
        ((= n 6) 6)
        ((= n 7) 7)
        ((= n 8) 8)
        ((= n 9) 9)))


(build-list 9 (increment-function (scramble-fun tup-fun2)))

(scramble '(1 2 3 1 2 3 4 1 8 2 10))
 
(define (tup-fun1 n)
  ;; (1 2 3 1 2 3 4 1 8 2 10)   
  (cond ((= n 1) 1)
        ((= n 2) 2)
        ((= n 3) 3)
        ((= n 4) 1)
        ((= n 5) 2)
        ((= n 6) 3)
        ((= n 7) 4)
        ((= n 8) 1)
        ((= n 9) 8)
        ((= n 10) 2)
        ((= n 11) 10)))

(build-list 11 (increment-function (scramble-fun tup-fun1)))

(scramble '(1 1 1 3 4 2 1 1 9 2))
    ;;     (1 1 1 1 1 4 1 1 1 9)


(define (tup-fun3 n)
  (cond ((= n 1) 1)
        ((= n 2) 1)
        ((= n 3) 1)
        ((= n 4) 3)
        ((= n 5) 4)
        ((= n 6) 2)
        ((= n 7) 1)
        ((= n 8) 1)
        ((= n 9) 9)
        ((= n 10) 2)))

(build-list 10 (increment-function (scramble-fun tup-fun3)))