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

Question
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
      case head::tail => f(data)::maplist(f,tail)
    }
  }
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)
1 Like
4

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

1 Like
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 :dizzy_face:
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
}
1 Like
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.

1 Like
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)
1 Like
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.)