Here are some simple puzzles to exercise your brain.
1. Write partial-apply-left, a function that takes a
binary function and the left input of the binary function and
returns the unary function that takes the right input and then applies
the binary function to both inputs.
For example:
;; Define *foo* as a procedure that conses 'a onto its argument. > (defvar *foo* (partial-apply-left #'cons 'a)) > (funcall *foo* 'b) (A . B) > (funcall *foo* 42) (A . 42)
2. Write distribute, a function that takes a binary
function, a left input, and a list of right inputs, and returns a
list of the results of applying the binary function to the left
input and each of the right inputs. (Hint:
Use partial-apply-left)
For example:
> (distribute #'cons 'a '( (b c d) e 42)) ((A B C D) (A . E) (A . 42))
3. Write removals, a function that takes a list
and returns a list of lists, where each sublist is the original
list with exactly one element removed.
For example:
> (removals '(a b c)) ((B C) (A C) (A B))
Hint:
- One removal is the CDR of the list.
- Other removals can be constructed by (distributed) consing the CAR onto the removals of the CDR.
4. Write power-set, a function that takes a list and
returns the power set of that list (the set of all subsets of the
original list).
For example:
> (power-set '(a b c)) (() (C) (B) (B C) (A) (A C) (A B) (A B C))
Hint:
Note how the power set of a list can be constructed from the power set of its CDR by adding the CAR to each subset in the power set of the CDR.
5. Write power-set-gray that returns the subsets
sorted so each subset differs from the previous subset by a change
of one element (i.e., each subset is equal to the next subset with
either one element added or one element removed). This is called a Gray
code ordering of the subsets.
For example:
> (power-set-gray '(a b c)) (() (C) (B C) (B) (A B) (A B C) (A C) (A))
Hint:
When appending the two halves of the power set, reverse the order of the second half.
