CODEWITHSUNDEEP
scheme
Bim Sala
Bim Sala

Reputation: 3

Where is the error in this Scheme program?

I am getting "Error: Invalid lambda: (lambda (insert-all))."

(define permutations
 (lambda (L)
  (let
   ((insert-all
    (lambda (e Ls)
     (let
     ((insert-one
      (lambda (L)
       (letrec
        ((helper
         (lambda(L R)
         (if (null? R)
          (list (append L(list e)R))
          (helper (append L (list (car R) ) ) (cdr R) )
          ))))
          (helper '() L)))))
          (apply append(map insert-one Ls)))))))

  (cond ((null? L) '() )
  ((null?(cdr L)) (list L))
  (else (insert-all (car L) (permutations ((cdr L))))))))

It is supposed to return all permutations of a given list.

Upvotes: 0

Views: 812

Answers (1)

GoZoner
GoZoner

Reputation: 70135

The form that you have provided in not valid scheme. Specifically, your highest-level let form does not have a body. You might be thinking that the cond clause is the body but owing to your parenthesis it is not part of the let. Honestly, this is the fault of your formatting. Here is a 'properly' formatted Scheme form:

(define (permutations L)
  (let ((insert-all
         (lambda (e Ls)
           (let ((insert-one
                  (lambda (L)
                    (let helper ((L '()) (R L))
                      (if (null? R)
                          (list (append L (list e) R))
                          (helper (append L (list (car R)))
                                  (cdr R)))))))
             (apply append (map insert-one Ls))))))

    (cond ((null? L)       '())
          ((null? (cdr L)) (list L))
          (else (insert-all (car L)
                            (permutations (cdr L)))))))

At least it compiles and runs, although it doesn't produce the right answer (although I don't know what the proper input it):

> (permutations '(a b c))
((c b a))
> (permutations '((a b) (1 2)))
(((1 2) (a b)))

Here is an implementation that works:

(define (permutations L)
  (define (insert-all e Ls)
    (apply append 
           (map (lambda (e) 
                  (map (lambda (x) (cons e x)) Ls))
                e)))
  (cond ((null? L)       '())
        ((null? (cdr L)) (map list (car L)))
        (else (insert-all (car L)
                          (permutations (cdr L))))))


> (permutations '((a b) (1 2) (x y)))
((a 1 x) (a 1 y) (a 2 x) (a 2 y) (b 1 x) (b 1 y) (b 2 x) (b 2 y))

The basic structure of your code was fine; just the implementation of your insert-one and helper were lacking.

Upvotes: 1

Related Questions