Flatten a list of tuples in Scala?

Question

I would have thought that a list of tuples could easily be flattened:

scala> val p = "abcde".toList
p: List[Char] = List(a, b, c, d, e)

scala> val q = "pqrst".toList
q: List[Char] = List(p, q, r, s, t)

scala> val pq = p zip q
pq: List[(Char, Char)] = List((a,p), (b,q), (c,r), (d,s), (e,t))

scala> pq.flatten

But instead, this happens:

<console>:15: error: No implicit view available from (Char, Char) => scala.collection.GenTraversableOnce[B].
       pq.flatten
          ^

I can get the job done with:

scala> (for (x <- pq) yield List(x._1, x._2)).flatten
res1: List[Char] = List(a, p, b, q, c, r, d, s, e, t)

But I'm not understanding the error message. And my alternative solution seems convoluted and inefficient.

What does that error message mean and why can't I simply flatten a List of tuples?

Tusker

Answer 1

If the implicit conversion can't be found you can supply it explicitly.

pq.flatten {case (a,b) => List(a,b)}

If this is done multiple times throughout the code then you can save some boilerplate by making it implicit.

scala> import scala.language.implicitConversions
import scala.language.implicitConversions

scala> implicit def flatTup[T](t:(T,T)): List[T]= t match {case (a,b)=>List(a,b)}
flatTup: [T](t: (T, T))List[T]

scala> pq.flatten
res179: List[Char] = List(a, p, b, q, c, r, d, s, e, t)

Buonaparte

Please don't use implicit conversions when both the source and target type are this common. Mix this with e.g. auto-tupling and you get all kinds of wacky stuff. Got a method that takes a list of strings? Suddenly foo("a", "b") works but foo("a", "b", "c") doesn't. And on and on… – Endymion

Point taken. Implicits are, by their nature, a little too "spooky" and probably should be avoided in casual situations like this. – Buonaparte

Answer 2

jwvh's answer covers the "coding" solution to your problem perfectly well, so I am not going to go into any more detail about that. The only thing I wanted to add was clarifying why the solution that both you and jwvh found is needed.

As stated in the Scala library, Tuple2 (which (,) translates to) is:

A tuple of 2 elements; the canonical representation of a Product2.

And following up on that:

Product2 is a cartesian product of 2 components.

...which means that Tuple2[T1,T2] represents:

The set of all possible pairs of elements whose components are members of two sets (all elements in T1 and T2 respectively).

A List[T], on the other hand, represents an ordered collections of T elements.

What all this means practically is that there is no absolute way to translate any possible Tuple2[T1,T2] to a List[T], simply because T1 and T2 could be different. For example, take the following tuple:

val tuple = ("hi", 5)

How could such tuple be flattened? Should the 5 be made a String? Or maybe just flatten to a List[Any]? While both of these solutions could be used, they are working around the type system, so they are not encoded in the Tuple API by design.

All this comes down to the fact that there is no default implicit view for this case and you have to supply one yourself, as both jwvh and you already figured out.

Champollion

So basically the conversion that @Buonaparte supplied ensures that the tuples members both have the same type (T, T). That would allow them to be flattened (a,b) => List(a,b). Nice explanation (: – Afterimage

@mdm: The conversion from Tuple2[T1,T2] to List[T] is indeed not obvious, but Tuple2[T,T] -> List[T] is on the other hand fairly straightforward. I don't think there is a good reason scala does not provide it. If I can flatten a List[Option[T]], I should be able to do the same with List[(T,T)], List[(T,T,T)] etc. – Nantucket

@Dima, why, when perfectly good Seq (et al) already exist? I think the use-cases are limited (and, in some cases, it would be quite wrong). Take a typical use of (x, y) to store coordinates. x and y are still not the same thing and flatten would be a very unappropriate operation. Tuples are more than a sequence of possibly different types, the index within them is also very important, and implicitly providing operations that somewhat ignore that is't a good idea (all very "mostly opinions" of course, but that's OK in comments). – Aventurine

@dima, Option[T] is a Monad, and flatten in that case is effectively exercising that. Every Option[T] is a Monad, and the behaviour is consistent within the type: flatten on any T will have the same behaviour. Tuple[T1,T2] on the other hand is not a Monad, and it has no consistent behaviour to offer. The fact that, specifically for the interaction between Tuple[T,T] and List[T], you can flatten it, hardly justifies a language-level special case, IMHO. – Champollion

@dima, Also, you could make Tuple[T,T] a specific monad instance, but why would the language designer choose that List((5,7),(6,8)) should flatten to List(5,7,6,8) rather than, for example, List(5,6)? Or maybe List(7,8)? The behaviour you describe is "obvious" only if you are using a Tuple as a List, which you cannot expect the type system to give for granted. – Champollion

@mdm: the language designer would choose that List((5,7), (6,8)) should flatten to List(5,7,6,8) for the same reason he chose that List(Some(1), Some(2)) to flatten to List(1,2), not List(12) or List(148) - because it makes sense. You are correct: the behavior I describe is obvious if you are using a tuple as a list. In all other cases, you would not need .flatten. And the fact that Option[T] is a monad, and Tuple2[T,T] does not explain anything, it just makes things worse: why the hell not??? – Nantucket

@TheArchetypalPaul "tuples are more than a sequence ..." - that is true. Options are also more than sequences of at most one element, yet I can flatten the list of the latter. – Nantucket

@dima: "because it makes sense" is a highly subjective view, but in any case, you can always add a PR to add such implicit to the language. If it is going to be approved and added to the language, then maybe you can make it an objective one. – Champollion

@Dima, but options are still "containers" to me in a way that Tuples arent. Basically, I think I'm ending up at mdm's point that they're monads. Tuples to me are more like a case class with an empty name and strange parameter names :) and I don't think most people would think case class Foo(a:Int, b:Int); val x = Foo(1,2).flatten should work. Anyway, interesting discussion. – Aventurine

@Champollion Any view can be said to be "subjective", that is not a very good argument. Consider that none of the people who reacted to this question (including yourself) appear to have any doubt about what kind of behavior would be expected of flatten had it been implemented. And thanks, I know I can add a PR, just don't care enough to do it ... – Nantucket

@TheArchetypalPaul I don't see what monads have to do with it: one can easily and trivially add .flatMap to a Tuple2[T,T]. That would make it a monad, but how would it affect the question at hand? – Nantucket

@Dima, but you couldn't add it to Tuple2[T, U]. I think all of this revolves around whether one thinks a two-type-parameter "thing" should be considered differently (and support different operations) if the two type parameters supplied happen to be the same type. I don't think it should, you're of the opposite opinion. – Aventurine

@TheArchetypalPaul there are many instances in scala where different operations are supported, depending on the kind and structure of type parameters, there is nothing exceptional about it. For example, you can .toMap a List[Tuple2[K,V]], but not List[T] in general. You cannot sort a List[T], unless an Ordering is available. Obviously, you can also .flatten List[T] only for some values of T, and not others. I don't see what makes those cases different. – Nantucket

None of those are two different types that happen to be the same. They're all about constraints on one type. I do see those as different. – Aventurine

@TheArchetypalPaul in the case in hand, it is a constraint on one type too: in Tuple2[T1, T2], only T2 is constrained to be the same as T1. T1 in turn can be anything – Nantucket

We'll have to agree to disagree on that. – Aventurine

Answer 3

We needed to do this recently. Allow me to explain the use case briefly before noting our solution.

Use case

Given a pool of items (which I'll call type T), we want to do an evaluation of each one against all others in the pool. The result of these comparisons is a Set of failed evaluations, which we represent as a tuple of the left item and the right item in said evaluation: (T, T).

Once these evaluations are complete, it becomes useful for us to flatten the Set[(T, T)] into another Set[T] that highlights all the items that have failed any comparisons.

Solution

Our solution for this was a fold:

val flattenedSet =
    set.foldLeft(Set[T]())
                { case (acc, (x, y)) => acc + x + y }

This starts with an empty set (the initial parameter to foldLeft) as the accumulator.

Then, for each element in the consumed Set[(T, T)] (named set) here, the fold function is passed:

1. the last value of the accumulator (acc), and
2. the (T, T) tuple for that element, which the case deconstructs into x and y.

Our fold function then returns acc + x + y, which returns a set containing all the elements in the accumulator in addition to x and y. That result is passed to the next iteration as the accumulator—thus, it accumulates all the values inside each of the tuples.

Why not Lists?

I appreciated this solution in particular since it avoided creating intermediate Lists while doing the flattening—instead, it directly deconstructs each tuple while building the new Set[T].

We could also have changed our evaluation code to return List[T]s containing the left and right items in each failed evaluation—then flatten would Just Work™. But we thought the tuple more accurately represented what we were going for with the evaluation—specifically one item against another, rather than an open-ended type which could conceivably represent any number of items.

Bohlen

Can you explain how this works? How does it solve the problem? – Simpleton

@RichardWеrеzaк I added explanation to the answer. – Bohlen