NetLogo: How to implement `sentence-map` (aka `flatMap`)?

Question

NetLogo has a map primitive that runs a reporter task on each element of an input list and collects a list of the results.

Many programming languages that have map also have something called flatMap (or monadic bind or collect or SelectMany or mapcan or append-map) that does the same thing, but allows (or requires) the reporter task to report a list of results instead. The end result is a single list containing all of the result lists concatenated.

In Logo (including in NetLogo), the concatenation part is called sentence, so a good name for the operation combining mapping with concatenation might be sentence-map.

So for example, we want:

observer> show sentence-map task [list ? ?] [1 2 3]
observer: [1 1 2 2 3 3]

Note that sentence doesn't require all of its inputs to be lists. For example, (sentence 1 [2 3] 4) evaluates to [1 2 3 4]. So our definition of sentence-map will follow suit. Example:

observer> show sentence-map task [ifelse-value (? mod 2 = 0) [(list ? ?)] [?]] [1 2 3]
observer: [1 2 2 3]

How can sentence-map be implemented, and is the implementation efficient?

Answer 1

The easiest way to define sentence-map is as follows:

to-report sentence-map [f xs]
  report reduce sentence map f xs
end

As for efficiency, if you are using NetLogo 5.0.5 or newer, this definition should perform well (O(n)-ish runtime).

In NetLogo 5.0.4 and earlier versions, the repeated use of sentence will make the overall time O(n²) due to this NetLogo bug (where the underlying cause was this Scala bug).

If for some reason you're stuck using an older version of NetLogo, you could work around it by writing your own version of sentence that does concatenation by repeatedly calling lput, and then using that inside sentence-map.