cartesian product on an arbitrary number of lists. inspired by haskellers saying this is "just `sequence` on the list monad"

cross_product.py

# sequence :: Monad m => [m a] -> m [a]
#
# a way of implementing this functionality is through a left fold
# that unwraps the each monad in the first list and accumulates it
# in the second list, rewrapped in the target monad:
#
# sequence actions = foldl unwrapAccumulateRewrap (return []) actions
#   where unwrapAccumulateRewrap wrappedAccumulator action = 
#     wrappedAccumulator >>= \accumulator -> action >>= \value -> return (value : accumulator)
#
# the first `>>=` in `unwrapAccumulateRewrap` above unwraps the acumulator (a list) from the
# containing monad. the second `>>=` unwraps the value of the current action in our list of actions
# the final step puts that value at the head of the accumulator and rewraps it in our target monad.
#
# for the case of the cartesian product our target monad is another list: we want a list
# of the combinbations among a list of lists. since we don't know how big each list is, each combination
# is itself a list so we have something like:
# 
# crossProduct :: [[a]] -> [[a]]
# 
# which, if we remember that the list is a monad looks suspiciously like `sequence`.
# `>>=` for lists is basically a list comprehension. that means we can rewrite
# `unwrapAccumulateRewrap` as:
#
# unwrapAccumulateRewrap lists currentList = 
#   [(value : list) | list <- lists, value <- list]
#
# this can be pretty directly translated into python, where it immediately becomes more imperative
# given python's "lack" of `fold`:
def cross_product1(*lists):
    initial = [[]]
    for list in lists:
      initial = [[x, *other] for other in initial for x in list]
    return initial

# and from there we can make it more imperative to get at what the list comprehension is doing:
def cross_product2(*lists):
    initial = [[]]
    for list in lists:
        accumulator = []
        for other in initial:
            for x in list:
                accumulator.append([x] + other)
        initial.append(accumulator)
    return initial
  
# when i started thinking about this problem i didn't have a good idea of how to implement it,
# even imperatively. looking up the haskell solution that uses sequence and working my way through
# the types for that function helped me better understand monads, list comprehensions, and cartesian products
# All At Once ™