Re: functional programming is great, but why lists?

["Ricardo H. Medel" <rmedel@cs.stevens-tech.edu>]

Bill:

Functional programming is great, but why numbers? Numbers seems pretty
cumbersome. Why not use functions instead? For example, there's a very
elegant number in your examples: 3. The easiest way to describe the
number 3 is by a function/non-number version of it:

(lambda (f) (lambda (x) (f (f (f x)))))

Sorry. I'm in funny mood.

Ricardo Medel
Stevens Institute of Technology
-------------------------------

On Wed, 10 Oct 2001, Bill Richter wrote:

> Date: Wed, 10 Oct 2001 22:42:36 -0500
> From: Bill Richter <richter@math.nwu.edu>
> To: plt-scheme@fast.cs.utah.edu
> Subject: functional programming is great, but why lists?
>
> 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)))
>
>