What is the inverse of intercalate, and how to implement it?

Question

This question discusses how to interleave two lists in an alternating fashion, i.e. intercalate them.

• What is the inverse of "intercalate" called?
• Is there an idiomatic way to implement this in Scala?

Answer 1

The topic is discussed on this Haskell IRC session.

Possibilities include "deintercalate", "extracalate", "ubercalate", "outercalate", and "chocolate" ;-)

Assuming we go for "extracalate", it can be implemented as a fold:

def extracalate[A](a: List[A]) = 
    a.foldRight((List[A](), List[A]())){ case (b, (a1,a2)) => (b :: a2, a1) }

For example:

val mary = List("Mary", "had", "a", "little", "lamb")
extracalate(mary)                              
//>  (List(Mary, a, lamb),List(had, little)

Note that the original lists can only be reconstructed if either:

• the input lists were the same length, or
• the first list was 1 longer than the second list

The second case actually turns out to be useful for the geohashing algorithm, where the latitude bits and longitude bits are intercalated, but there may be an odd number of bits.

Note also that the definition of intercalate in the linked question is different from the definition in the Haskell libraries, which intersperses a list in between a list of lists!

Update: As for any fold, we supply a starting value and a function to apply to each value of the input list. This function modifies the starting value and passes it to the next step of the fold. Here, we start with a pair of empty output lists: (List[A](), List[A]()) Then for each element in the input list, we add it onto the front of one of the output lists using cons ::. However, we also swap the order of the two output lists , each time the function is invoked; (a1, a2) becomes (b :: a2, a1). This divides the input list between the two output lists in alternating fashion. Because it's a right fold, we start at the end of the input list, which is necessary to get each output list in the correct order. Proceeding from the starting value to the final value, we would get:

([], [])
([lamb], [])
([little],[lamb])
([a, lamb],[little])
([had, little],[a, lamb])
([Mary, a, lamb],[had, little])

Answer 2

Also, using standard methods

val mary = List("Mary", "had", "a", "little", "lamb")
       //> mary  : List[String] = List(Mary, had, a, little, lamb)
val (f, s) = mary.zipWithIndex.partition(_._2 % 2 == 0)
       //> f  : List[(String, Int)] = List((Mary,0), (a,2), (lamb,4))
       //| s  : List[(String, Int)] = List((had,1), (little,3))
(f.unzip._1, s.unzip._1) 
       //> res0: (List[String], List[String]) = (List(Mary, a, lamb),List(had, little))

Not really recommending it, though, the fold will beat it hands down on performance

Skinning the cat another way

val g = mary.zipWithIndex.groupBy(_._2 % 2) 
        //> g  : scala.collection.immutable.Map[Int,List[(String, Int)]] = Map(1 -> List
        //| ((had,1), (little,3)), 0 -> List((Mary,0), (a,2), (lamb,4)))
 (g(0).unzip._1, g(1).unzip._1)
       //> res1: (List[String], List[String]) = (List(Mary, a, lamb),List(had, little))

Also going to be slow

Answer 3

I think it's inferior to @DNA's answer as it's more code and it requires passing through the list twice.

scala> list
res27: List[Int] = List(1, 2, 3, 4, 5)

scala> val first = list.zipWithIndex.filter( x => x._1 % 2 == 1).map(x => x._2)
first: List[Int] = List(0, 2, 4)

scala> val second = list.zipWithIndex.filter( x => x._1 % 2 == 0).map(x => x._2)
second: List[Int] = List(1, 3)

scala> (first, second)
res28: (List[Int], List[Int]) = (List(0, 2, 4),List(1, 3))