Question regarding Higher-Order-Programming in Python

Discussion in 'Python' started by Mark Fink, Dec 22, 2010.

  1. Mark Fink

    Mark Fink Guest

    I am about to learn Higher-Order-Programming with Lisp, Haskell, and
    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, ...)?
     
    Mark Fink, Dec 22, 2010
    #1
    1. Advertising

  2. Mark Fink

    Peter Otten Guest

    Mark Fink wrote:

    > I am about to learn Higher-Order-Programming with Lisp, Haskell, and
    > 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
     
    Peter Otten, Dec 22, 2010
    #2
    1. Advertising

  3. Mark Fink

    Mark Fink Guest

    > >>> 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)]
     
    Mark Fink, Dec 22, 2010
    #3
  4. Mark Fink <> 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
     
    Arnaud Delobelle, Dec 22, 2010
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jonathan Bartlett

    Higher-Order Programming in C

    Jonathan Bartlett, Mar 31, 2005, in forum: C Programming
    Replies:
    4
    Views:
    305
    Jonathan Bartlett
    Apr 4, 2005
  2. Vijendra
    Replies:
    2
    Views:
    373
    Tim Slattery
    Sep 14, 2006
  3. Nickolay Kolev

    Higher Order Functions

    Nickolay Kolev, Jul 31, 2005, in forum: Ruby
    Replies:
    5
    Views:
    154
    Nickolay Kolev
    Aug 8, 2005
  4. Victor \Zverok\ Shepelev

    Higher-order messaging in Ruby

    Victor \Zverok\ Shepelev, Oct 11, 2006, in forum: Ruby
    Replies:
    0
    Views:
    125
    Victor \Zverok\ Shepelev
    Oct 11, 2006
  5. Nate Murray
    Replies:
    13
    Views:
    202
    Gregory Brown
    Jan 5, 2007
Loading...

Share This Page