Created
February 17, 2018 01:15
-
-
Save clarkenciel/d99775b6b0ea32c141247b7b67fb5e62 to your computer and use it in GitHub Desktop.
cartesian product on an arbitrary number of lists. inspired by haskellers saying this is "just `sequence` on the list monad"
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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 ™ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment