# Searching for variant of map/flatMap which applies function to successive sublists rather than to list elements

#1

Both map and flatMap take a function which is applied to successive elements of the list/sequence/…
Is there a variant already in the standard library which applies the function to successive lists/sequences/… instead? I’m not sure if this idea even makes sense for non-lists. I’m interested to see how it might.

Here is my implementation for List. which is not tail recursive, but a robust version of course should be.

`````` def maplist[A1,R](f:List[A1]=>R,data:List[A1]):List[R] = {
data match {
case Nil => Nil
}
}
``````

#2

Seems you are replacing every element in `data` with `f`(data)` not sure I get the purpouse but this may be what you are looking foor

``````
`def maplist[A1,R](f:List[A1]=>R,data:List[A1]):List[R] = data.map(_ => f(data))
``````

#3

That’s not correct.
His `maplist`:

``````scala> maplist((_: List[Int]).length, List(1,1,1,1))
res0: List[Int] = List(4, 3, 2, 1)
``````

Your `maplist`:

``````scala> maplist((_: List[Int]).length, List(1,1,1,1))
res1: List[Int] = List(4, 4, 4, 4)
``````

#4

yes you are right, I miss to consider that data was changing in the recursive call.

#5

It “almost” exists, in the form of the method `tails`:

``````scala> List(1,1,1,1).tails.map(_.length).toList
res2: List[Int] = List(4, 3, 2, 1, 0)

scala> def maplist[A1, R](f: List[A1] => R, data: List[A1]): List[R] =
|   data.tails.collect{ case t if t.nonEmpty => f(t) }.toList
maplist: [A1, R](f: List[A1] => R, data: List[A1])List[R]

scala> maplist((_: List[Int]).length, List(1,1,1,1))
res3 List[Int] = List(4, 3, 2, 1)
``````

#6

That’s right, Jasper-M, maplist iterates over the cons-cells of a list. It is useful in lisp in cases very similar to mapcar (scala map) where you need to make a decision about what’s coming later in the list. a simple example is uniquifying or counting duplicates, but there are other reasons as well. I’ve used it very often when traversing lists of points which indicate vertices of a polygon. Looking forward helps decide whether we are approaching left-turns or right-turns in the polygon.

#7

Hi Jasper-M, does your implementation allocate all the lists before calling the function f the first time? If so, I can just stick with the version I have, and fix the problem of the tail-call.

#8

`tails` returns an `Iterator[List[A]]` which is lazy. In other words: it should deconstruct the cons cells on demand. However according to https://github.com/scala/bug/issues/9892 it only got decent efficiency since 2.12.5.

#9

Hi Jasper, I like your solution. It is concise and memory efficient (at least in 2.12.5 &+), but it is not obvious how to extend this to a 3-arity function.
Here is my try.

``````  def maplistX[A1,A2,A3,R](f:(List[A1],List[A2],List[A3])=>R,data1:List[A1],data2:List[A2],data3:List[A3]):List[R] = {
(data1.tails, data2.tails, data3.tails).zipped.collect {
case (a: List[A1], b: List[A2], c: List[A3]) if a.nonEmpty && b.nonEmpty && c.nonEmpty => f(a, b, c)
}.toList
}
``````

When I compile this, i get the error:

``````Error:(62, 45) No implicit view available from Iterator[List[A1]] => scala.collection.TraversableLike[El1,Repr1].
(data1.tails, data2.tails, data3.tails).zipped.collect {
Error:(62, 45) not enough arguments for method zipped: (implicit w1: Iterator[List[A1]] => scala.collection.TraversableLike[El1,Repr1], implicit w2: Iterator[List[A2]] => scala.collection.IterableLike[El2,Repr2], implicit w3: Iterator[List[A3]] => scala.collection.IterableLike[El3,Repr3])scala.runtime.Tuple3Zipped[El1,Repr1,El2,Repr2,El3,Repr3].
Unspecified value parameters w1, w2, w3.
(data1.tails, data2.tails, data3.tails).zipped.collect {
``````

#10

Er yeah, that’s a particularly ugly one
The problem is that `zipped` expects to be able to convert the things in the tuple to a `TraversableLike` or `IterableLike` collection. A property of those collection types is (at least I think so) that they can be traversed multiple times. While an `Iterator` can generally only be traversed once.
I would suggest the following change:

``````def maplistX[A1,A2,A3,R](f:(List[A1],List[A2],List[A3])=>R,data1:List[A1],data2:List[A2],data3:List[A3]):List[R] = {
(data1.tails zip data2.tails zip data3.tails).collect {
case ((a, b), c) if a.nonEmpty && b.nonEmpty && c.nonEmpty => f(a, b, c)
}.toList
}
``````

#11

hmm, so that zipping two tails creates an iterator which iterates the zipped result? i.e., lazy-zip?

#12

Yes, everything that comes before `.toList` creates simple `Iterator` objects without computing any sublists or tuples yet.

#13

I think you’re looking for `coflatMap`, which is not in the standard library but is provided by Cats.

``````@ import cats.implicits._
import cats.implicits._

@ List(1,2,3).coflatMap(identity)
res1: List[List[Int]] = List(List(1, 2, 3), List(2, 3), List(3))

@ List(1,2,3).coflatMap(_.sum)
res2: List[Int] = List(6, 5, 3)
``````

#14

Thanks for the information about coflatMap. It is not immediately obvious to me why this is a flatMap–it doesn’t seem to flatten anything, although that doesn’t make it any less interesting.

#15

It’s not a flatMap, more like (though not literally) the opposite. “co-” in this context means something like “reverse the direction of an operation”.

``````def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
def coflatMap[B, A](fa: F[B])(f: F[B] => A): F[A]
``````

(I flipped the generic parameter names for coflatMap to highlight the reverse symmetry.)