Code mini-golf

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.