Forward iteration on lists

Question
1

There is certain type of iteration that I ofent do in lisp and find myself wishing to do in Scala. Perhaps it is not very idiomatic in Scala.

(let ((my-list '(a b c d e f)))
  (mapcon (lambda (is) 
            (when (cdr is)
              (let ((i1 (car is)))
                (mapcar (lambda (i2)
                          (list i1 i2))
                        (cdr is)))))
          my-list))

Which evaluates to the following:

((A B) (A C) (A D) (A E) (A F) 
 (B C) (B D) (B E) (B F) 
 (C D) (C E) (C F) 
 (D E) (D F) 
 (E F))

I.e. it iterates i1 and i2 over the given list but only for i2 strictly to the right of i1. Thus by construction we have (c d) in the return list, but not (d c).

I can’t see how this could be implemented in Scala for general collections. To be implemented efficiently the collection needs to be (1) ordered, (2) list-like in the sense that head and tail are easy to compute [not an array or set], and (3) at multiply iterable [not iterable only once].

Perhaps this works ONLY for List, not sure if there is a larger set of types for which it makes sense.

Here is my implementation this lisp idiom in Scala.

I wonder whether someone can comment on this implementation. Is it the correct
way to perform this iteration? I believe, (and it’s hidden from the programmer by the for abstrction), that the lists are converted to iterators, and I have to convert the final iterator back to a List at the end.

It seems like there should be a better way without resorting to this conversion, i.e. by manipulating the cons cells directly. On the other hand, the Scala code is indeed very concise and readable.

val data = List("a","b","c","d","e")
val tmp = for {
                is <- data.tails
                if is.nonEmpty
                i1 = is.head
                i2 <- is.tail
              } yield (i1,i2)
tmp.toList

Which evaluates to the following:

List((a,b), (a,c), (a,d), (a,e), (b,c), (b,d), (b,e), (c,d), (c,e), (d,e))
2

How about:
data.zip(data.tails.drop(1)).flatMap { case (x, xs) => xs.map(x -> _) }

3

@odd, Not sure which scala version you are using, but for me, I get compilation errors:

Error:(10, 25) type mismatch;
found   : Iterator[List[String]]
required: scala.collection.GenIterable[?]
data.zip(data.tails.drop(1)).flatMap { case (x, xs) => xs.map(x -> _) }
Error:(10, 59) value map is not a member of Any
data.zip(data.tails.drop(1)).flatMap { case (x, xs) => xs.map(x -> _) }
4

@jimka I’m on Scala 2.13.2.

5

A solution for List like datastructures.

def zipWithTails[A](list: List[A]): List[(A, A)] = {
  @annotation.tailrec
  def loop(remaining: List[A], acc: List[Iterator[(A, A)]]): List[Iterator[(A, A)]] =
    remaining match {
      case a :: as =>
        val iter = as.iterator.map(a2 => a -> a2)
        loop(remaining = as, iter :: acc)
      
      case Nil =>
        acc
    }
  
  loop(
    remaining = list,
    acc = List.empty
  ).reverseIterator.flatten.toList
}

Another one for Array like datastructures.

def zipWithTails[A](arr: ArraySeq[A]): ArraySeq[(A, A)] = {
  val indices = for {
    i <- 0 until len
    j <- (i + 1) until len
  } yield (i, j)
  
  ArraySeq.tabulate(indices.length) { x =>
    val (i, j) = indices(x)
    arr(i) -> arr(j)
  }
}
6

This is a nice use case coflatMap, but you need Cats to do it. I’m also using tupleLeft from Functor which is shorthand for .map(a => (<constant>, a)).

@ val cs = "abcdef".toList 
cs: List[Char] = List('a', 'b', 'c', 'd', 'e', 'f')

@ cs.coflatMap { case h :: t => t.tupleLeft(h) } 
cmd1.sc:1: match may not be exhaustive.
It would fail on the following input: Nil
val res1 = cs.coflatMap { case h :: t => t.tupleLeft(h) }
                        ^
res1: List[List[(Char, Char)]] = List(
  List(('a', 'b'), ('a', 'c'), ('a', 'd'), ('a', 'e'), ('a', 'f')),
  List(('b', 'c'), ('b', 'd'), ('b', 'e'), ('b', 'f')),
  List(('c', 'd'), ('c', 'e'), ('c', 'f')),
  List(('d', 'e'), ('d', 'f')),
  List(('e', 'f')),
  List()
)

The warning can be disregarded because coflatMap only visits non-empty substructures. You can get rid of this warning by using NonEmptyList rather than list.

You can do .dropRight(1) if you don’t want the trailing Nil, and .flatten if you want a list of pairs rather than a list of lists of pairs.

It will work for List and Vector and Chain and other common immutable sequence types.

2 Likes
7

There should be a flatCoflatMap.

2 Likes