CODEWITHSUNDEEP
listcountscheme
Muspel
Muspel

Reputation: 1

Counting in Scheme without recursion?

So, I have a homework assignment that is asking me to make a function that counts the number of elements in a list without using recursion. (Which seems crazy to me, since Scheme is all about recursion from what I've learned so far, but that's a different discussion.) We're also not allowed to use the built-in length function.

I'm assuming this involves map somehow, but beyond that, I'm stuck, and everything I've googled for help offers a recursive solution (or uses !set, which the class hasn't taught us about and which I'm assuming is not the answer they're looking for).

Upvotes: 0

Views: 346

Answers (1)

user5920214
user5920214

Reputation:

If you take a rather fussy definition of recursion: a function is recursive iff it calls its own name, either directly or indirectly, then you can write things which are not 'recursive' in this very limited sense, by, really, noting that functions that don't have names can't be recursive (again: in this limited sense).

So you can start with this slightly odd function:

(λ (f)
  (λ (l)
    (if (null? l)
        0
        (+ 1 ((f f) (cdr l))))))

This is a function which takes another function, f as an argument and returns a function which takes a list as an argument and which:

  • if the list is empty will correctly compute its length;
  • if the list is not empty, then if (f f) is a function which will correctly compute the length of the cdr of the list, this function will compute the length of the whole list, by adding one to it.

So, wait: this function, if given another function which, when called with itself as an argument, will return a function which will compute the length of the rest of a list, will compute the length of a list. That means that this function itself is a candidate for this f function: when called with itself as an argument it should return a function which computes the length of a list. So, OK, we can wrap it up a bit to make this proposed length-computing function:

((λ (g)
   (g g))
 (λ (f)
   (λ (l)
     (if (null? l)
         0
         (+ 1 ((f f) (cdr l)))))))

Should be a function which computes the length of a list. And we can try it:

> (((λ (g)
      (g g))
    (λ (f)
      (λ (l)
        (if (null? l)
            0
            (+ 1 ((f f) (cdr l)))))))
   '(1 2 3))
3

Well, it does seem to compute the length of the list. So we can, finally, give this thing a name to make it easier to call:

(define list-length
  ((λ (g)
     (g g))
   (λ (f)
     (λ (l)
       (if (null? l)
           0
           (+ 1 ((f f) (cdr l))))))))

And now

> (list-length '())
0
> (list-length '(a b c d))
4

OK.

So, conventionally, this is done by giving the thing that applies a function to itself a name: it's the U combinator:

(define U
  (λ (f) (f f)))

And then we can rewrite list-length in terms of U:

(define list-length
  (U (λ (f)
       (λ (l)
         (if (null? l)
             0
             (+ 1 ((U f) (cdr l))))))))

And the question is: is list-length recursive? Well, maybe?

Upvotes: 1

Related Questions