CODEWITHSUNDEEP
listhaskellmonads
J. Doe
J. Doe

Reputation: 477

Map, where each input element can correspond to multiple output elements

Being new to haskell, I am wondering what a more efficient way of doing the following is:

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

My lists are going to be thousands to millions of elements long, and it seems a shame to create a list of N lists just to concatenate them together.

Alternatively and preferably, is there some more general (probably monadic) way to have haskell create a list progressively from the results of a function, such that the list is built progressively without creating an O(n) sized recursive expression tree to evaluate?

Upvotes: 1

Views: 75

Answers (1)

chi
chi

Reputation: 116139

Just use

mapmulti = concatMap

from the library.

Moreover, even using your own implementation, the compiler might be able to optimize the intermediate lists away using a technique known as "deforestation".

Even if this is not done, at runtime the intermediate lists would be not completely produced before they are consumed, since Haskell is lazy. Rather, one list element will be produced and immediately consumed, making it available for garbage collection before the next one is produced. This would improve the memory footprint greatly, since everything might be done in constant space.

Upvotes: 6

Related Questions