How to decompose a list like this in scheme/lisp?

Question

Input1:

(decompose '(* 1 2 3 4))

Output1:

'(* 1 (* 2 (* 3 4)))

Input2

(decompose '(+ 1 2 3 (* 5 6 7)))

Output2

'(+ 1 (+ 2 (+ 3 (* 5 (* 6 7)))))    

Does anyone have ideas about this?

Answer 1

Modified from Chris Jester-Young's solution:

(define (decompose x)
  (if (pair? x)
      (let ((operator (car x))
            (expanded-x (map decompose x)))
        (let decompose-helper ((operands (cdr expanded-x)))
          (if (<= (length operands) 2)
              (cons operator operands)
              (list operator (car operands) (decompose-helper (cdr operands))))))
      x))

Answer 2

I see you posted your own solution, so I guess it's ok to show my complete answer. Here's another possible implementation, as a mutually-recursive pair of procedures. I like the fact that this solution doesn't require using length or list? (which might entail unnecessary traversals over the list), and uses only elementary functions (no foldr, reverse, map or any other higher-order procedures are needed.)

(define (decompose lst)
  (if (or (null? lst)                     ; if the list is empty
          (null? (cdr lst))               ; or has only one element
          (null? (cddr lst)))             ; or has only two elements
      lst                                 ; then just return the list
      (process (car lst)                  ; else process car of list (operator)
               (cdr lst))))               ; together with cdr of list (operands)

(define (process op lst)
  (cond ((null? (cdr lst))                ; if there's only one element left
         (if (not (pair? (car lst)))      ; if the element is not a list
             (car lst)                    ; then return that element
             (decompose (car lst))))      ; else decompose that element
        ((not (pair? (car lst)))          ; if current element is not a list
         (list op                         ; build a list with operator,
               (car lst)                  ; current element,
               (process op (cdr lst))))   ; process rest of list
        (else                             ; else current element is a list
         (list op                         ; build a list with operator,
               (decompose (car lst))      ; decompose current element,
               (process op (cdr lst)))))) ; process rest of list

It works for your examples, and then some:

(decompose '(* 1 2 3 4))
=> '(* 1 (* 2 (* 3 4)))

(decompose '(+ 1 2 3 (* 5 6 7)))
=> '(+ 1 (+ 2 (+ 3 (* 5 (* 6 7)))))

(decompose '(+ 1 (* 4 5 6) 2 3))
=> '(+ 1 (+ (* 4 (* 5 6)) (+ 2 3)))

(decompose '(+ 1 2 3 (* 5 6 7) 8))
=> '(+ 1 (+ 2 (+ 3 (+ (* 5 (* 6 7)) 8))))

(decompose '(+ 1 2 3 (* 5 6 7) (* 8 9 10) (* 11 12 (- 1))))
=> '(+ 1 (+ 2 (+ 3 (+ (* 5 (* 6 7)) (+ (* 8 (* 9 10)) (* 11 (* 12 (- 1))))))))

Answer 3

Same way as you would evaluate it, but instead of outputting the result, you simply output the expression that would be used.

Here's my implementation, tested on Racket:

(define (decompose expr)
  (define (expand x)
    (if (list? x)
        (decompose x)
        x))
  (define oper (car expr))
  (let next ((args (map expand (cdr expr))))
    (if (<= (length args) 2)
        (cons oper args)
        (list oper (car args) (next (cdr args))))))