Cartesian product of two or more lists: Difference between revisions
Content added Content deleted
(→{{header|Python}}: Added a compact native approach (no imports), in a more mathematical idiom, demonstrating use of Python for functional programming) |
|||
Line 2,045: | Line 2,045: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
Using itertools |
===Using itertools=== |
||
<lang python>import itertools |
<lang python>import itertools |
||
Line 2,103: | Line 2,103: | ||
(3, 30, 100)] |
(3, 30, 100)] |
||
((1, 2, 3), (), (500, 100)) => |
((1, 2, 3), (), (500, 100)) => |
||
[] |
[]</pre> |
||
</pre> |
|||
===Using the 'Applicative' abstraction=== |
|||
This task calls for alternative approaches to defining cartesian products, and one particularly compact alternative route to a native cartesian product (in a more mathematically reasoned idiom of programming) is through the Applicative abstraction [[wp:Applicative_functor|Applicative Functor]], which is slightly more general than the possibly better known '''monad''' structure. Applicative functions are provided off-the-shelf by languages like Agda, Idris, Haskell and Scala, and can usefully be implemented in any language, including Python, which supports higher-order functions. |
|||
If we write ourselves a re-usable Python '''ap''' function for the case of lists (applicative functions for other 'data containers' can also be written – this one applies a list of functions to a list of values): |
|||
<lang python># ap (<*>) :: [(a -> b)] -> [a] -> [b] |
|||
def ap(fs): |
|||
return lambda xs: foldl( |
|||
lambda a: lambda f: a + foldl( |
|||
lambda a: lambda x: a + [f(x)])([])(xs) |
|||
)([])(fs)</lang> |
|||
then one simple use of it will be to define the cartesian product of two lists (of possibly different type) as: |
|||
<lang python>ap(map(Tuple, xs))</lang> |
|||
where Tuple is a constructor, and xs is bound to the first of two lists. The returned value is a function which can be applied to a second list. |
|||
For an nAry product, we can then use a '''fold''' (catamorphism) to lift the basic function over two lists ''cartesianProduct :: [a] -> [b] -> [(a, b)]'' to a function over a list of lists: |
|||
<lang python># nAryCartProd :: [[a], [b], [c] ...] -> [(a, b, c ...)] |
|||
def nAryCartProd(xxs): |
|||
return foldl1(cartesianProduct)( |
|||
xxs |
|||
)</lang> |
|||
For example: |
|||
<lang python># Two lists -> list of tuples |
|||
# cartesianProduct :: [a] -> [b] -> [(a, b)] |
|||
def cartesianProduct(xs): |
|||
return ap(map(Tuple, xs)) |
|||
# List of lists -> list of tuples |
|||
# nAryCartProd :: [[a], [b], [c] ...] -> [(a, b, c ...)] |
|||
def nAryCartProd(xxs): |
|||
return foldl1(cartesianProduct)( |
|||
xxs |
|||
) |
|||
# main :: IO () |
|||
def main(): |
|||
# Product of lists of different types |
|||
print ( |
|||
'Product of two lists of different types:' |
|||
) |
|||
print( |
|||
cartesianProduct(['a', 'b', 'c'])( |
|||
[1, 2] |
|||
) |
|||
) |
|||
# TESTS OF PRODUCTS OF TWO LISTS |
|||
print( |
|||
'\nSpecified tests of products of two lists:' |
|||
) |
|||
print( |
|||
cartesianProduct([1, 2])([3, 4]), |
|||
' <--> ', |
|||
cartesianProduct([3, 4])([1, 2]) |
|||
) |
|||
print ( |
|||
cartesianProduct([1, 2])([]), |
|||
' <--> ', |
|||
cartesianProduct([])([1, 2]) |
|||
) |
|||
# TESTS OF N-ARY CARTESIAN PRODUCTS |
|||
print('\nSpecified tests of nAry products:') |
|||
for xs in nAryCartProd([[1776, 1789], [7, 12], [4, 14, 23], [0, 1]]): |
|||
print(xs) |
|||
for xs in ( |
|||
map_(nAryCartProd)( |
|||
[ |
|||
[[1, 2, 3], [30], [500, 100]], |
|||
[[1, 2, 3], [], [500, 100]] |
|||
] |
|||
) |
|||
): |
|||
print( |
|||
xs |
|||
) |
|||
# GENERIC ------------------------------------------------- |
|||
# Applicative function for lists |
|||
# ap (<*>) :: [(a -> b)] -> [a] -> [b] |
|||
def ap(fs): |
|||
return lambda xs: foldl( |
|||
lambda a: lambda f: a + foldl( |
|||
lambda a: lambda x: a + [f(x)])([])(xs) |
|||
)([])(fs) |
|||
# foldl :: (a -> b -> a) -> a -> [b] -> a |
|||
def foldl(f): |
|||
def go(v, xs): |
|||
a = v |
|||
for x in xs: |
|||
a = f(a)(x) |
|||
return a |
|||
return lambda acc: lambda xs: go(acc, xs) |
|||
# foldl1 :: (a -> a -> a) -> [a] -> a |
|||
def foldl1(f): |
|||
return lambda xs: foldl(f)(xs[0])( |
|||
xs[1:] |
|||
) if xs else None |
|||
# map :: (a -> b) -> [a] -> [b] |
|||
def map_(f): |
|||
return lambda xs: list(map(f, xs)) |
|||
# Tuple :: a -> b -> (a, b) |
|||
def Tuple(x): |
|||
return lambda y: ( |
|||
x + (y,) |
|||
) if tuple is type(x) else (x, y) |
|||
# TEST ---------------------------------------------------- |
|||
if __name__ == '__main__': |
|||
main()</lang> |
|||
{{Out}} |
|||
<pre>Product of two lists of different types: |
|||
[('a', 1), ('a', 2), ('b', 1), ('b', 2), ('c', 1), ('c', 2)] |
|||
Specified tests of products of two lists: |
|||
[(1, 3), (1, 4), (2, 3), (2, 4)] <--> [(3, 1), (3, 2), (4, 1), (4, 2)] |
|||
[] <--> [] |
|||
Specified tests of nAry products: |
|||
(1776, 7, 4, 0) |
|||
(1776, 7, 4, 1) |
|||
(1776, 7, 14, 0) |
|||
(1776, 7, 14, 1) |
|||
(1776, 7, 23, 0) |
|||
(1776, 7, 23, 1) |
|||
(1776, 12, 4, 0) |
|||
(1776, 12, 4, 1) |
|||
(1776, 12, 14, 0) |
|||
(1776, 12, 14, 1) |
|||
(1776, 12, 23, 0) |
|||
(1776, 12, 23, 1) |
|||
(1789, 7, 4, 0) |
|||
(1789, 7, 4, 1) |
|||
(1789, 7, 14, 0) |
|||
(1789, 7, 14, 1) |
|||
(1789, 7, 23, 0) |
|||
(1789, 7, 23, 1) |
|||
(1789, 12, 4, 0) |
|||
(1789, 12, 4, 1) |
|||
(1789, 12, 14, 0) |
|||
(1789, 12, 14, 1) |
|||
(1789, 12, 23, 0) |
|||
(1789, 12, 23, 1) |
|||
[(1, 30, 500), (1, 30, 100), (2, 30, 500), (2, 30, 100), (3, 30, 500), (3, 30, 100)] |
|||
[]</pre> |
|||
=={{header|R}}== |
=={{header|R}}== |