Entendendo Scala Sequence Comprehensions

Neste post explicarei a “mágica” por trás da sintaxe de sequence comprehensions em Scala..

Scala Sequence Comprehensions

val sixInts = List(1, 2, 3, 4, 5, 6)
for {
  x <- sixInts
  y <- sixInts
  if x % 2 == 0 && y % 2 == 0
} yield (x, y)

A sintaxe lembra um SELECT...JOIN em SQL onde a cláusula WHERE requer que x e y sejam pares. O resultado da avaliação da expressão for acima é a lista de todos os pares de números pares entre 1 e 6.

Resultado

List((2,2), (2,4), (2,6), (4,2), (4,4), (4,6), (6,2), (6,4), (6,6))

A mesma lista poderia ser definida de outra forma.

Scala Sequence Comprehensions

for {
  x <- sixInts if x % 2 == 0
  y <- sixInts
  if y % 2 == 0 // o if também pode ser colocado em outra linha
} yield (x, y)

Sequence comprehensions são traduzidas para expressões equivalentes em termos de flatMap, map, e withFilter que são métodos definidos em todas as Collections da linguagem Scala. Como exemplo, nesse post, estou usando apenas a List, mas qualquer classe que defina flatMap, map e withFilter pode ser usada dentro de expressões for como essas.

filter(), withFilter(), map() e flatMap()

/**
 * Selects all elements of this list which satisfy a predicate.
 *
 * @param p the predicate used to test elements.
 * @returns a new list consisting of all elements of this
 * list that satisfy the given predicate p.
 * The order of the elements is preserved.
 */
def filter(p: (A) => Boolean): List[A]

/**
 * Creates a non-strict filter of this list.
 *
 * Note: the difference between c filter p and c withFilter p
 * is that the former creates a new collection, whereas the
 * latter only restricts the domain of subsequent
 * map, flatMap, foreach, and withFilter operations.
 *
 * @param p the predicate used to test elements.
 * @returns an object of class WithFilter, which supports
 * map, flatMap, foreach, and withFilter operations.
 * All these operations apply to those elements of this
 * list which satisfy the predicate p.
 */
def withFilter(p: (A) => Boolean): FilterMonadic[A, List[A]]

/**
 * Builds a new collection by applying a function to all elements
 * of this list.
 *
 * @param B the element type of the returned collection.
 * @param f the function to apply to each element.
 * @returns a new list resulting from applying the given
 * function f to each element of this list and
 * collecting the results.
 */
def map[B](f: (A) => B): List[B]

/**
 * Builds a new collection by applying a function to all elements
 * of this list and using the elements of the resulting collections.
 *
 * @param f the function to apply to each element.
 * @returns a new list resulting from applying the given
 * collection-valued function f to each element of
 * this list and concatenating the results.
 */
def flatMap[B](f: (A) =>  GenTraversableOnce[B]): List[B]

Para entendimento desse post, pode-se entender withFilter como sendo indêntico ao método filter. A diferença é que em vez de alocar uma nova lista, withFilter passa a lista e o predicado para a criação de uma instância de WithFilter. WithFilter define map, flatMap, filter, withFilter… mas restringe a aplicação dessas funções apenas aos valores que satisfazem ao predicado da chamada a withFilter, comportando-se exatamente como uma List resultante da aplicação de filter.

Eexemplo de uso de flatMap

val lines = List(
  "Lorem ipsum dolor sit amet, consectetur",
  "adipisicing elit, sed do eiusmod tempor",
  "incididunt ut labore et dolore magna aliqua."
)
lines flatMap (line => line split "\\W+")  // List[String] = List(Lorem, ipsum, dolor, sit, amet,
                                           //|      consectetur, adipisicing, elit, sed, do,
                                           //|      eiusmod, tempor, incididunt, ut, labore, et,
                                           //|      dolore, magna, aliqua)

Nesse exemplo, flatMap transforma uma lista de linhas de um texto em uma lista de palavras de um texto. Para isso, basta prover a flatMap uma função que transforma uma linha em uma lista de palavras. flatMap aplicará essa função a cada linha e concatenará as listas resultantes para produzir o resultado final.

Após entender as definições de withFilter, flatMap e map, vamos às regras de tradução de sequence comprehensions.

1 for simples

Forma mais simple de sequence comprehension

for (x <- e1) yield e2
// onde `e1` e `e2` são expressões

// equivale a
e1.map(x => e2)

Em sua forma mais simples, um for é simplesmente um map.

// sixInts => e1
// 2 * x => e2
for (x <- sixInts) yield 2 * x //> List[Int] = List(2, 4, 6, 8, 10, 12)

// equivale a
sixInts.map(x => 2 * x) //> List[Int] = List(2, 4, 6, 8, 10, 12)

2 for com filtro

for com um filtro (ou condição do loop)

for (x <- e1 if p; s) yield e2
// onde `p` é um expressão booleana
// `s` é uma sequência (possivelmente vazia) de geradores e filtros

// equivale a
for (x <- e1.withFilter(x => p); s) yield e2
// e a tradução continua a partir dessa nova expressão.

// Particulamente para `s` vazio
for (x <- e1 if p) yield e2
// equivale a
for (x <- e1.withFilter(x => p)) yield e2
// que equivale a (pela regra 1)
e1.withFilter(x => p).map(x => e2)

// Para o caso em que `s` é não-vazio, a tradução segue
// aplicando-se a regra 3.

ifs são traduzidos para chamadas a withFilter.

3 for com sequência de geradores

for com seqûencia de geradores

for (x <- e1; y <- e2; s) yield e3
// onde `s` é uma sequência (possivelmente vazia) de geradores e filtros

// equivale a
e1.flatMap(x => for (y <- e2; s) yield e3)
// e a tradução continua a partir dessa nova expressão.

Quando há mais de um gerador, flatMap é usado. Você pode entender a sequência de geradores como várias chamadas aninhadas a flatMap (regra 3) e filtros quando necessário, que produzem uma única sequência que servirá para a aplicação de map ao final. A função passada para map é construída a partir da expressão após a palavra-chave yield.

Juntando tudo

Vamos traduzir as expressões for apresentadas no início do post.

Passo a passo da tradução

val sixInts = List(1, 2, 3, 4, 5, 6)

for {
  x <- sixInts
  y <- sixInts
  if x % 2 == 0 && y % 2 == 0
} yield (x, y)     // List((2,2), (2,4), (2,6), (4,2), (4,4), (4,6), (6,2), (6,4), (6,6))

// Aplicando a regra 3, equivale a 
sixInts.flatMap(x =>
  for (
    y <- sixInts
    if x % 2 == 0 && y % 2 == 0
  ) yield (x, y)
)

// Aplicando a regra 2, equivale a
sixInts.flatMap(x =>
  for (
    y <- sixInts.withFilter(y => x % 2 == 0 && y % 2 == 0)
  ) yield (x, y)
)

// Aplicando a regra 1, equivale a
sixInts.flatMap(x =>
  sixInts.withFilter(y => x % 2 == 0 && y % 2 == 0).map(y =>
    (x, y)
  )
)      // List((2,2), (2,4), (2,6), (4,2), (4,4), (4,6), (6,2), (6,4), (6,6))

A primeira forma tem apenas um filtro (equivalente ao if x % 2 == 0 && y % 2 == 0).

Passo a passo da tradução

val sixInts = List(1, 2, 3, 4, 5, 6)

for {
  x <- sixInts
  if x % 2 == 0
  y <- sixInts
  if y % 2 == 0
} yield (x, y)    // List((2,2), (2,4), (2,6), (4,2), (4,4), (4,6), (6,2), (6,4), (6,6))

// Aplicando a regra 2, equivale a
for {
  x <- sixInts.withFilter(x => x % 2 == 0)
  y <- sixInts
  if y % 2 == 0
} yield (x, y)

// Aplicando a regra 3, equivale a
sixInts.withFilter(x => x % 2 == 0).flatMap(x =>
  for(
    y <- sixInts
    if y % 2 == 0
  ) yield (x, y)
)

// Aplicando a regra 2, equivale a
sixInts.withFilter(x => x % 2 == 0).flatMap(x =>
  for (
    y <- sixInts.withFilter(y => y % 2 == 0)
  ) yield (x, y)
)

// Aplicando a regra 1, equivale a
sixInts.withFilter(x => x % 2 == 0).flatMap(x =>
  sixInts.withFilter(y => y % 2 == 0).map(y =>
    (x, y)
  )
)         // List((2,2), (2,4), (2,6), (4,2), (4,4), (4,6), (6,2), (6,4), (6,6))

A segunda forma tem dois filtros (um para testar a paridade de x e outro para testar a paridade de y).