Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Python (http://www.velocityreviews.com/forums/f43-python.html)
-   -   Question regarding Higher-Order-Programming in Python (http://www.velocityreviews.com/forums/t740619-question-regarding-higher-order-programming-in-python.html)

 Mark Fink 12-22-2010 08:50 AM

Question regarding Higher-Order-Programming in Python

Python. Some people who have gone completely out of their mind call
this FP.

In Haskell I learned that when I use map on a list it starts nesting
as soon as I start adding elements. If I do not like the nesting I use
ConcatMap.

In Python I have a similar scenario. I have a generator which creates
some combinatorics of a input dictionary. The list starts nesting. Now
I could use reduce(concat, ...) which would be the correct thing from
a functional perspective. But from a resource utilization perspective
it is not a good idea since the reduce is executing the generator.

I tried to illustrate this using a small example (the often in
combinatorics the real thing would be much bigger that is why I need
to use a generator):

>>> from operator import itemgetter, concat
>>> import itertools as it
>>> from functools import partial
>>>
>>> dims = {'number': [1,2,3], 'letter': ['a', 'b'], 'special': ['+', '-']}
>>> dims

{'special': ['+', '-'], 'number': [1, 2, 3], 'letter': ['a', 'b']}
>>> def get_products(keys):

.... # helper to get products from keys in the following form:
.... # [('bold', True), ('color', 'black')]
.... values = itemgetter(*keys)(dims)
.... product = it.product(*values)
.... return map(partial(zip, keys), product)
....
>>> comb = it.combinations(dims, 2)
>>> comb_l = list(comb)
>>> comb_l

[('special', 'number'), ('special', 'letter'), ('number', 'letter')]
>>> res = map(get_products, comb_l)
>>> res

[[[('special', '+'), ('number', 1)], [('special', '+'), ('number',
2)], [('special', '+'), ('number', 3)], [('special', '-'), ('number',
1)], [('special', '-'), ('number', 2)], [('special', '-'), ('number',
3)]], [[('special', '+'), ('letter', 'a')], [('special', '+'),
('letter', 'b')], [('special', '-'), ('letter', 'a')], [('special',
'-'), ('letter', 'b')]], [[('number', 1), ('letter', 'a')],
[('number', 1), ('letter', 'b')], [('number', 2), ('letter', 'a')],
[('number', 2), ('letter', 'b')], [('number', 3), ('letter', 'a')],
[('number', 3), ('letter', 'b')]]] # the resulting list is nested one
level to deep caused by the map(get_products, ..
>>>

My problem is that I want to get single elements from the generator
like [('special', '+'), ('number', 1)]. But this does not work because
the list is now nested to deep.

That is what I expect: (I could get something like that with the
following >>> res = reduce(concat, res)
[[('special', '+'), ('number', 1)], [('special', '+'), ('number', 2)],
[('special', '+'), ('number', 3)], [('special', '-'), ('number', 1)],
[('special', '-'), ('number', 2)], [('special', '-'), ('number', 3)],
[('special', '+'), ('letter', 'a')], [('special', '+'), ('letter',
'b')], [('special', '-'), ('letter', 'a')], [('special', '-'),
('letter', 'b')], [('number', 1), ('letter', 'a')], [('number', 1),
('letter', 'b')], [('number', 2), ('letter', 'a')], [('number', 2),
('letter', 'b')], [('number', 3), ('letter', 'a')], [('number', 3),
('letter', 'b')]]

I have seen the problem many times but so far I could not google a
solution on the web.

By the way do you know any substantial example using FP in Python
(generators, imap, ifilter, ...)?

 Peter Otten 12-22-2010 12:57 PM

Re: Question regarding Higher-Order-Programming in Python

Mark Fink wrote:

> Python. Some people who have gone completely out of their mind call
> this FP.
>
> In Haskell I learned that when I use map on a list it starts nesting
> as soon as I start adding elements. If I do not like the nesting I use
> ConcatMap.
>
> In Python I have a similar scenario. I have a generator which creates
> some combinatorics of a input dictionary. The list starts nesting. Now
> I could use reduce(concat, ...) which would be the correct thing from
> a functional perspective. But from a resource utilization perspective
> it is not a good idea since the reduce is executing the generator.
>
> I tried to illustrate this using a small example (the often in
> combinatorics the real thing would be much bigger that is why I need
> to use a generator):
>
>>>> from operator import itemgetter, concat
>>>> import itertools as it
>>>> from functools import partial
>>>>
>>>> dims = {'number': [1,2,3], 'letter': ['a', 'b'], 'special': ['+', '-']}
>>>> dims

> {'special': ['+', '-'], 'number': [1, 2, 3], 'letter': ['a', 'b']}
>>>> def get_products(keys):

> ... # helper to get products from keys in the following form:
> ... # [('bold', True), ('color', 'black')]
> ... values = itemgetter(*keys)(dims)
> ... product = it.product(*values)
> ... return map(partial(zip, keys), product)
> ...
>>>> comb = it.combinations(dims, 2)
>>>> comb_l = list(comb)
>>>> comb_l

> [('special', 'number'), ('special', 'letter'), ('number', 'letter')]
>>>> res = map(get_products, comb_l)
>>>> res

> [[[('special', '+'), ('number', 1)], [('special', '+'), ('number',
> 2)], [('special', '+'), ('number', 3)], [('special', '-'), ('number',
> 1)], [('special', '-'), ('number', 2)], [('special', '-'), ('number',
> 3)]], [[('special', '+'), ('letter', 'a')], [('special', '+'),
> ('letter', 'b')], [('special', '-'), ('letter', 'a')], [('special',
> '-'), ('letter', 'b')]], [[('number', 1), ('letter', 'a')],
> [('number', 1), ('letter', 'b')], [('number', 2), ('letter', 'a')],
> [('number', 2), ('letter', 'b')], [('number', 3), ('letter', 'a')],
> [('number', 3), ('letter', 'b')]]] # the resulting list is nested one
> level to deep caused by the map(get_products, ..
>>>>

>
> My problem is that I want to get single elements from the generator
> like [('special', '+'), ('number', 1)]. But this does not work because
> the list is now nested to deep.

Like this?

>>> [(k, v) for k, vv in dims.iteritems() for v in vv]

[('special', '+'), ('special', '-'), ('number', 1), ('number', 2),
('number', 3), ('letter', 'a'), ('letter', 'b')]

But these are just glorified for-loops, so:

>>> list(chain.from_iterable(starmap(product, izip(izip(dims.iterkeys()),

dims.itervalues()))))
[('special', '+'), ('special', '-'), ('number', 1), ('number', 2),
('number', 3), ('letter', 'a'), ('letter', 'b')]

Peter

 Mark Fink 12-22-2010 02:35 PM

Re: Question regarding Higher-Order-Programming in Python

> >>> list(chain.from_iterable(starmap(product, izip(izip(dims.iterkeys()),
>
> dims.itervalues()))))
> [('special', '+'), ('special', '-'), ('number', 1), ('number', 2),
> ('number', 3), ('letter', 'a'), ('letter', 'b')]
>
> Peter

so far I have never noticed chain.from_iterable, but many thanks to
you Peter, I have now a beautiful solution to this problem.
>>> from itertools import chain
>>> comb = it.combinations(dims, 2)
>>> l = chain.from_iterable(it.imap(get_products, comb))
>>> l.next()

[('special', '+'), ('number', 1)]
>>> l.next()

[('special', '+'), ('number', 2)]

 Arnaud Delobelle 12-22-2010 09:45 PM

Re: Question regarding Higher-Order-Programming in Python

Mark Fink <mark@mark-fink.de> writes:

> so far I have never noticed chain.from_iterable, but many thanks to
> you Peter, I have now a beautiful solution to this problem.
>>>> from itertools import chain
>>>> comb = it.combinations(dims, 2)
>>>> l = chain.from_iterable(it.imap(get_products, comb))

You can also write this as:

l = (p for c in comb for p in get_products(c))

>>>> l.next()

> [('special', '+'), ('number', 1)]
>>>> l.next()

> [('special', '+'), ('number', 2)]

Also in your original post you define get_products:

>>>> def get_products(keys):

> ... # helper to get products from keys in the following form:
> ... # [('bold', True), ('color', 'black')]
> ... values = itemgetter(*keys)(dims)
> ... product = it.product(*values)
> ... return map(partial(zip, keys), product)
> ...

You could define it as e.g.

def get_products(keys):
key_values = [[(k, v) for v in values] for k in keys]
return it.product(*key_values)

But maybe for some reason you are trying to avoid list comprehensions
and generator expressions?

--
Arnaud

 All times are GMT. The time now is 09:04 AM.