3

Note: This is kind of homework, kind of not -- the end goal is to have a function that produces a powerset of a set of numbers supplied to the function as a list of numbers. I have a recursive version of the function but I now need to find some ways of replacing each explicitly recursive function in the solution I have (append, mapm etc.) with an equivalent lambda-only expression.

As such, I am starting with smaller problems and hope to combine them all to write a full function. I've managed to come up with a non-recursive factorial function using pure-lambda (Y combinator) but I am now trying to come up with a nice function that squares every number in a list -- trying to solve smaller problems before jumping up to a multiply-recursive function:

(define (sqrlist numlist)
  (((lambda (f)
   ((lambda (x) (x x))
    (lambda (g)
     (f (lambda (x) ((g g) x))))))
  (lambda (f)
   (lambda (x)
    (cons (sqr (first x)) (rest x))))) numlist))

The code above doesn't recurse, despite the presence of the Y combinator before it -- I'm obviously having some issues passing the proper parameters to the functions within -- any ideas?

Will Ness
  • 70,110
  • 9
  • 98
  • 181
David
  • 113
  • 3
  • 8
  • Solved! Can I delete this question? – David Nov 24 '11 at 17:36
  • 1
    If you've solved it, can you post the answer here (or on your original question?) It's a pretty interesting question and answer IMHO. –  Nov 24 '11 at 17:54
  • Hi, I'd love to but my profs are pretty strict about posting code publicly until past the deadline.. I can email you a file with it though (the deadline isn't until Tuesday night. Also, I should clarify that my solution isn't for the whole problem... yet - it's just for the function I created above... – David Nov 24 '11 at 18:19
  • yes, `(lambda (f) (lambda (x) (cons (sqr (first x)) (rest x))))` does not use `f`. it should have been `(lambda (f) (lambda (x) (cons (sqr (first x)) (f (rest x)) )))`, for it to recurse. – Will Ness Nov 19 '20 at 17:46

2 Answers2

5

If you have a working procedure, converting to anonymous procedures is relatively straightforward and mechanical. Give each lambda an extra argument, which is "itself", and duplicate the procedure. So

(define (add-list list) 
  (if (empty? list) 
      0 
      (+ (first list) (add-list (rest list)))))

Becomes

(λ(list) (if (empty? list) 0 (+ (first list) (add-list (rest list)))))

This is of course a problem because add-list isn't defined. So we're going to have to ensure that we pass ourselves around every time.

(λ(self list) (if (empty? list) 0 (+ (first list) (self self (rest list)))))

But where do we get ourselves in the first place? Well, we copy and paste (and give it an argument)

((λ(self list) (if (empty? list) 0 (+ (first list) (self self (rest list)))))
 (λ(self list) (if (empty? list) 0 (+ (first list) (self self (rest list)))))
 '(1 2 3 4))

Abstracting this "copy and paste" to the Y combinator is developed excellently in "The Why of Y" (PDF) and you should definitely check it out.

But remember the first step was "get it working." Do this before you abstract away defines.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
law-of-fives
  • 643
  • 4
  • 8
1

Here's a possible answer, I know that you solved it already, but it could be useful to have a second opinion :)

((lambda (X)
    ((lambda (proc)
       (proc proc))
     (lambda (proc)
       (X (lambda (arg)
            ((proc proc) arg))))))
  (lambda (sqrlist)
    (lambda (lst)
      (if (null? lst)
          '()
          (cons (* (car lst) (car lst))
                (sqrlist (cdr lst)))))))

It's "lambda-only" since it's written exclusively in terms of anonymous functions, it doesn't even use define. Here's how to call it:

(((lambda (X)
     ((lambda (proc)
        (proc proc))
      (lambda (proc)
        (X (lambda (arg)
             ((proc proc) arg))))))
   (lambda (sqrlist)
     (lambda (lst)
       (if (null? lst)
           '()
           (cons (* (car lst) (car lst))
                 (sqrlist (cdr lst)))))))
 '(1 2 3 4 5))
Óscar López
  • 232,561
  • 37
  • 312
  • 386
  • Nice! Now how can I further abstract that to take two parameters... say I wanted to cons all squared values in one list to all squared values in another list... without using append :D – David Nov 24 '11 at 18:46
  • I basically now am trying to write a non-recursive version of the append function.. Problem is, i'm trying to pass it two parameters and no-go. – David Nov 24 '11 at 18:47
  • For more than one parameter things might be a bit trickier. Perhaps by using currying? – Óscar López Nov 24 '11 at 18:51
  • ! I got it without resorting to currying! (Thank god, it's so messy already!) Take a peek: `(define (my-append3 lst1 lst2) (((lambda (f) ((lambda (x) (x x)) (lambda (g) (f (lambda (x) ((g g) x)))))) (lambda (f) (lambda (x) (cond [(empty? x) lst2] [else (cons (first x) (f(rest x)))]))))lst1))` – David Nov 24 '11 at 19:18
  • Excelent! I hope that you can share the code after your homework is done and graded – Óscar López Nov 24 '11 at 19:32