Map,每个输入元素可以对应多个输出元素

Question

作为haskell的新手,我想知道更有效的方法是:

mapmulti :: (a -> [b]) -> [a] -> [b]
mapmulti fn list = concat $ map fn list

我的列表将长达数千到数百万个元素,创建一个N列表列表只是为了将它们连接在一起似乎是一种耻辱.

或者并且优选地,是否存在一些更通用(可能是monadic)的方式让haskell从函数的结果中逐步创建列表,以便逐步构建列表而不创建O(n)要评估的大小的递归表达式树？

Answer 1

只是用

mapmulti = concatMap

来自图书馆.

此外,即使使用您自己的实现,编译器也可以使用称为"砍伐森林"的技术来优化中间列表.

即使没有这样做,在运行时中间列表也不会在消耗之前完全生成,因为Haskell是懒惰的.相反,将生成一个列表元素并立即使用,使其在生成下一个列表元素之前可用于垃圾收集.这将极大地改善内存占用,因为一切都可以在恒定的空间内完成.