WARNING: You should seriously try to answer this question before looking at the solution -- it's just a good study skill. Also, some answers on this page may be more brief than you would want to put down in an actual exam. If you want any type of partial credit, you should write more than just the solution.
Proof by Induction on ?
Base Case: lst is (list x) for some value x
(all-pairs (list x))
(cond
((empty? (tail (list x)) empty)
((empty? (tail (tail (list x)) (list (list x)))
(else (append (pair-with-list (head (list x) (tail (list x)))
(all-pairs (tail (list x))))))
empty
Inductive Case:
Inductive Hypothesis: Assume that (all-pairs lst) produces a list
containing all the pairs for any lst, except the empty list
Prove: (all-pairs (cons x lst) produces a list containing all the pairs
for the list (cons x lst)
(all-pairs (cons x lst))
(cond ((empty? (tail (cons x lst))) empty)
(empty? (tail (tail (cons x lst))) (list (cons x lst)))
(else (append (pair-with-list (head (cons x lst) (tail (cons x lst)))
(all-pairs (tail (cons x lst))))))
(append (pair-with-list x lst)
(all-pairs lst))
[by IH, assumption that pair-with-list works, and assumption that append works]
((en en-1) (en en-2) ... (en e1) (en-1 en-2) (en-1 en-3)
... (en-1 e1) (en-2 en-3)... ... (e2 e1))