Jump to content
  • Advertisement
Sign in to follow this  

[Python] Does This Concept/function Have A Name?

This topic is 888 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Consider a simple cartesian product:

>>> p = lambda xs, ys: [(x,y) for x in xs for y in ys]
>>> p([1,2],[3,4])
[(1, 3), (1, 4), (2, 3), (2, 4)]

The function that I have in mind is very similar, but it introduces nesting:

>>> q = lambda xs, ys: [[(x,y) for y in ys] for x in xs]
>>> q([1,2],[3,4])
[[(1, 3), (1, 4)], [(2, 3), (2, 4)]]

Of course, that in itself is not very interesting, but we can use it as a higher order function:

>>> q = lambda func: lambda xs, ys: [[func(x,y) for y in ys] for x in xs]
>>> import operator
>>> add = q(operator.add)
>>> add([1],[1])
>>> add([1],[1,2,3])
[[2, 3, 4]]
>>> add([1,2,3],[1])
[[2], [3], [4]]
>>> add([1,2,3],[1,2,3])
[[2, 3, 4], [3, 4, 5], [4, 5, 6]]

That is kind of cool and probably useful in its own right, but we can go even further:

>>> def magic(func):
...   def _magic(xs, ys):
...     if isinstance(xs, list):
...       if isinstance(ys, list):
...         return [[_magic(x, y) for y in ys] for x in xs]
...       else:
...         return [_magic(x, ys) for x in xs]
...     else:
...       if isinstance(ys, list):
...         return [_magic(xs, y) for y in ys]
...       else:
...         return func(xs, ys)
...   return _magic
>>> add = magic(operator.add)
>>> add(1,1)
>>> add(1,[1,2,3])
[2, 3, 4]
>>> add([1,2,3],1)
[2, 3, 4]
>>> add([1,2],[1,2,3])
[[2, 3, 4], [3, 4, 5]]
>>> add([1,2,3],[1,2])
[[2, 3], [3, 4], [4, 5]]

As you can see, this can be used to map functions over nested lists of values. Might seem a bit esoteric at first, but I have had some concrete uses for it.

Now, the reason I made this thread is because 1) this seems like a pretty general concept, and I would be curious if it is already implemented somewhere, and 2) the magic function could of course be generalized further to take arbitrary numbers of arguments, but I haven't found an elegant way to do it.

Edited by Josh Petrie

Share this post

Link to post
Share on other sites

Passing functions around as data into other function, and applying them at a later stage is known as higher order functions

https://en.wikipedia.org/wiki/Higher-order_function where functions are first-class citizens too, like 'normal' data, such as integers or reals.


Python also has an old-style "[f(x) for x in xs]", namely "map(f, xs)". The new style with square brackets is however easier to read, and recommended.


A common use of higher order functions is in sorting where the sort order function is passed into the sort() call.


About your code, in your "magic" function, you treat x and y arguments in the same way, I would think you could write that as an iterative or recursive function, processing each argument in turn, instead of expanding all possible combinations of lists and integers for x and y.


Strongly related to your idea seems the Python concept "generator", where you switch from lists (collections of values that you move between operations) to streams (where you create a pipeline of operations, sort of "streaming" values from the first to the last operation, without ever building a large intermediate result list).

David Beazley made a very nice presentation about it, worth a read!  http://www.dabeaz.com/generators/



PS Using "isinstance" for case differentiation is very non-pythonic. If I would make my own list class, your test would fail. In general, you should know what you get (ie something in the environment should tell you that). It could be in the name of the function, or in a value you get from the caller, or something else.

Edited by Alberth

Share this post

Link to post
Share on other sites
Those are all very relevant, yes. Thanks Alberth! I was after information for this specific higher-order function, but I think outer product covers it pretty well. Typical case of the answer popping up minutes after you start a new thread. :)

I don't see any alternative to using "isinstance" in this case. I could have used "isinstance(obj, collections.Iterable)" to avoid the problem you mention, but sometimes you do not want to iterate just because an object is iterable.

>>> add("Hello", "World")
[['HW', 'Ho', 'Hr', 'Hl', 'Hd'], ['eW', 'eo', 'er', 'el', 'ed'], ['lW', 'lo', 'lr', 'll', 'ld'], ['lW', 'lo', 'lr', 'll'
, 'ld'], ['oW', 'oo', 'or', 'ol', 'od']]

Share this post

Link to post
Share on other sites

Yeah, your use case is a bit tricky. Normally "addValue" verses a "addList" function would be sufficient to know what you should do.


The only option I can think of is adding a data field, like

add(("value", "Hello"), ("list", "World"))

which would then treat the first argument as a single value, and the second argument as a sequence of values. Nice thing would be that operator.add can be used for list or string concatenation too then :)

Edited by Alberth

Share this post

Link to post
Share on other sites
Yes, that is probably not a bad way to do it if you really want to make the function work on any iterable. Somehow, the user would have to disambiguate (is x an iterable that should be iterated or not). However, for my purposes it is perfectly fine to assume that only certain types will be iterated over (I chose list in my example to keep it simple). Edited by kloffy

Share this post

Link to post
Share on other sites
In case anyone is interested, here is a recursive version for arbitrary numbers of arguments.
def outer(func):
    def _outer(*args, **kwargs):
        def __outer(args, items):
            if items:
                xs, *tail = items
                if isinstance(xs, list):
                    return [__outer(args, [x] + tail) for x in xs]
                    return __outer(args + [xs], tail)
                return func(*args, **kwargs)
        return __outer([], args)
    return _outer

Seems fairly straightforward now, not sure why I was scratching my head over it at the time... :) Edited by kloffy

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!