Saturday, August 22, 2009

A harder puzzle

The previous puzzle was inspired by this one:
(define (f l)
  (if (null? l) 
      #f
      (let ((r (fold-left kernel k0 l)))
        (f (if (car r) (cadr r) (caddr r))))))

(define (kernel l e)
  (list (not (car l))
        (if (car l) (cons e (cadr l)) (cadr l))
        (cons e (cons e (cons e (caddr l))))))

(define k0 (list #f '() '(#t #t #t)))
Q1 (easy): Show that for any non-negative integer n, (f (make-list n)) can return no value other than #f.

Q2 (very hard): Show that for any non-negative integer n, (f (make-list n)) returns #f.

1 comment:

Arcane Sentiment said...

By "very hard" you mean "famous open problem". :)