映射/减少具有多个for子句的列表推导的等效项

Question

我想编写一个功能等同的列表推导,只使用高阶函数,没有副作用.我这样做是出于严格的学习目的.我知道列表理解是Pythonic.在Python map(f, xs)中相当于[f(x) for x in xs].但是下面这些等价物是什么？

• A: [f(x, y) for x in xs for y in ys]
• B: [f(x, y) for x in range(1, 5) for y in range(x, 5)]

map只返回相同长度的列表.reduce更一般的,可以实现map和filter上面.

map(f, xs) == reduce(lambda a, e: a + [f(e)], xs, [])
filter(p, xs) == reduce(lambda a, e: a + [e] if p(e) else a, xs, [])

因此A可以实现为:

def map2(f, xs, ys):
    reduce(lambda a, x: a + map(lambda y: f(x, y), ys), xs, [])

但这并不能概括为> 2的条款.而且B更加棘手,因为1st for子句的迭代变量在第2个子句中使用.如何编写实现列表理解功能的函数(或函数集)？

Answer 1

这是monad的模式,特别是monad列表.在许多语言中,monad隐藏在某种语法糖之后,例如C#的LINQ,Scala的序列理解,Haskell的符号,或者甚至更多的语言,(多)列表推导(如Python中的这里).

从任何这些含糖语法转换为普通函数的关键术语是(在列表的特殊情况下)类型的函数([a], a -> [b]) -> [b],它是monad定义的基本部分.此功能以不同的名称已知,例如(>>=)或"绑定",flatMap或concatMap,或selectMany.

对于列表的情况,concatMap或者flatMap可能是最好的名称,因为它的作用是:在列表上映射一个返回列表的函数,给出一个列表列表; 然后,压扁该列表.

现在换一些更具体的事¹:

> from functools import reduce
> from operator import add
> def concatMap(xs, f):
      return reduce(add, map(f, xs), []) # only map and reduce!

测试:

> [x*y for x in range(1 ,5) for y in range(x, 5)]
> [1, 2, 3, 4, 4, 6, 8, 9, 12, 16]
> concatMap(range(1, 5), lambda x: concatMap(range(x, 5), lambda y:[x*y]))
> [1, 2, 3, 4, 4, 6, 8, 9, 12, 16]

而且更有趣:

> [x*y+z for x in range(1, 5) for y in range(x, 5) for z in range(x, y)]
> [3, 4, 5, 5, 6, 7, 8, 10, 11, 15]
> concatMap(range(1, 5),lambda x: concatMap(range(x, 5), lambda y: concatMap(range(x, y),lambda z: [x*y+z])))
> [3, 4, 5, 5, 6, 7, 8, 10, 11, 15]

最后,应该注意的是,虽然mapmonad总是需要类似函数,但通常reduce还不够 - 实际需要的是一个通用的"flattening"操作join,类型如m<m<a>>(使用模板/泛型语法),哪个m是有问题的monad的类型.

¹如评论中所述,这也可以定义为concatMap = lambda xs, f: chain.from_iterable(map(f, xs)),使用itertools和身份(>>=) ? join . fmap.