Suggestion: map-longest

[NoahTheDuke]

I've run into a scenario where I need to iterate over multiple collections until the longest one is exhausted, using some value as the fill for the other collections that are exhausted first. There are a couple good solutions on Stack Overflow, but I think it would be a useful function in medley too. I'm willing to write up an implementation.

[weavejester]

This isn't a bad idea, but I think the details make this difficult.

The first issue is: what about sequence? This operates in the same fashion as map when supplied with multiple collections:

(sequence (map +) [1 2 3] [4 5 6])
;=> (5 7 10)

This leads on to my second thought, which is whether a padding function would be simpler. For example:

(pad-with 0 [1 2 3] [4 5])
;=> ((1 2 3) (4 5 0))

(apply map + (pad-with 0 [1 2 3] [4 5]))
;=> (5 7 3)

(apply sequence (map +) (pad-with 0 [1 2 3] [4 5]))
;=> (5 7 3)

And this leads on to a performance question: should pad return seqs or use a custom type that implements IReduce as well as ISeq?

[NoahTheDuke]

I realize that pad-with is a generalization of map-longest (zip_longest in Python, for those searching), but I worry that it raises more questions than it answers.

Thinking out loud, pad-with would need to be lazy, producing a seq or vector of lazy-seqs, correct? So a naive printer might write (LazySeq@abc123 LazySeq@def456). Actually, having written that, is that even possible? You can't produce a lazy seq that relies on info from another object (unless you're going to be very naughty), so the processing has to happen while creating the sequences (counting as you go if lazy, counting ahead of time if eager).

We don't have access to multiple return values so we could lazily return tuples, but that has a different signature than map's multi-coll arity.

I am interested in hearing how you'd implement a pad-with, as I'm not currently able to imagine it.

[weavejester]

My thought was to either produce non-lazy lists, or tie them together such that iterating to the next lazy list item iterates each of the others in memory as well. This could be achieved by first transposing the collections, then transposing them back again:

(let [vs (apply map vector colls)]
  (map (fn [i] (map (fn [v] (v i)) vs))
       (range (count colls))))

However, that would lead to unintuitive behavior around memory. For instance, if you had three collections (a b c), then iterating through a would necessarily iterate through b and c as well.

In fact, thinking about it, any padding system has this problem with lazy seqs; once you get to the end of a collection, you need to check the other collections to check to see whether there's any padding required. This necessarily ties them together in memory - you can't keep a but discard b and c, as otherwise you won't know if a requires padding.

So on reflection, perhaps pad-with isn't a good solution if the collections are lazy.

Perhaps then we need both a map-longest and sequence-longest, though I think it would be more consistent to call them map-all and sequence-all, considering that we have interleave-all already. Or perhaps map-padded and sequence-padded?

[NoahTheDuke]

The naming is your domain, I have no attachment to map-longest except that it's similar to existing functions out there.

Looking at the implementation of sequence, it relies on map directly, so we could get away with sequence-all wrapping map-all.

(defn map-all
  [f coll & colls]
  ...)

(defn sequence-all
  [xform coll & colls]
  (clojure.lang.RT/chunkIteratorSeq
    (clojure.lang.TransformerIterator/createMulti
      xform
      (map-all #(clojure.lang.RT/iter %) (cons coll colls)))))

[NoahTheDuke]

Actually, I misspoke. createMulti is doing the iteration for us, not map. We'll have to write the iteration code ourselves. 😭

[weavejester]

There's also the question of which argument the padding value should be placed in, or if we just use nil.

If we're just using nil then map-all would be a good name as it fits in with interleave-all and partition-all. If we're explicitly choosing a padding value then map-padded emphasizes that such a value should be supplied.

(map-padded + 0 [1 2 3] [4 5])
(map-padded concat nil [[1 2] [1 2 3]] [[3 4]])

Adding an explicit padding value allows us to do things with arithmetic functions and the like that will throw an error on nil. Because the padding value may be placed in any of the function's arguments, we can't use fnil.

(map-padded + 0 [1 2 3] [4 5])
(map-padded * 1 [1 2 3] [4 5])
;; vs
(map-all #(+ (or %1 0) (or %2 0)) [1 2 3] [4 5])
(map-all #(* (or %1 1) (or %2 2)) [1 2 3] [4 5])

So I think I'm leaning toward the padded version. There's also the question of whether to go with:

• (map-padded f val coll & colls)
• (map-padded val f coll & colls)

My thought is that the former feels more intuitive, as that's similar to the function signature of (reduce f val coll).

We also probably want to enforce at least two collections, as there's no point in using the padded version with only one collection. So:

• (map-padded f val c1 c2 & colls)
• (sequence-padded xform val c1 c2 & colls)

[weavejester]

We could probably define map-padded as:

(defn map-padded
  ([f val c1 c2] (sequence-padded (map f) val c1 c2))
  ([f val c1 c2 & colls] (apply sequence-padded (map f) val c1 c2 colls)))

That would at least mean that only sequence-padded would need to be written.

It might also be worth taking a look through clojure.core to ensure that map and sequence are the only functions that act like this.

[NoahTheDuke]

I took a stab at sequence-padded and gave up because I was unable to figure out how to write the iteration logic in Clojure. So instead I wrote up map-padded in #102, which works well. I welcome input on both my implementation of map-padded and ideas for how to implement sequence-padded.

[NoahTheDuke]

Closed with #102 merged