Successor syntax for for comprehensions

#1

I’d like to suggest an enhancement for the for comprehension syntax. This is motivated by a feature of the Common Lisp loop macro. I’m completely open to the particular syntax, but I’d like to hear what people think about the semantics. Here is an example.

for{
  x <- xs
  y = 1 then f(y)
  z <- zs
}

The semantics are that the first time through the x map* loop, y is bound to 1, thereafter after x is bound to its next value, y is bound to f(y) where y is the value from the previous iteration. E.g.,

for{
  x <- xs
  y = true then !y
  z <- zs
}

In this example y is bound to true, then false, then true, etc… Another example:

for{
  x <- xs
  y = 0 then (y+1) % 3
  z <- zs
}

In this case y iterates through the sequence 0, 1, 2, 0, 1, 2, etc…

Note that in each of these examples, there is only an x loop and a z loop. The y=... syntax does not evoke another call to map/flatMap, but rather a binding within the map/flatMap of x

The same behavior can be achieved in an awkward way using foldLeft, and I suggest more difficult to read:

    xs.foldLeft((zero,0)){ ((acc,y), x) => {
      (acc ++ zs.map(f(x,y,z)),f(y)) // ++ to emulate flatMap of x
    }}

The conversation started here.

I welcome anyone’s comments.

#2

This makes some sense when for is used as a loop or possibly as a comprehension from an iterative perspective over collections, but I don’t see how this abstracts.

What would this desugar to, in either the comprehension or the loop case? And is this useful for anything other than collections?

2 Likes
#3

I believe how it should desugar is just to make the previous value of y available in scope when evaluating the then part. Although the then part could also simply be a call by name parameter used as the next value of y.

As to whether it would be useful for the non-looping case, I can’t see any such use. Is there some abstraction of fold which works for non-collection monoids? After all my suggested syntax is a marriage between fold and map.

#4

I like the idea, but indeed it only makes sense for collections, and not necessarily for other things on which for comprehension can be used.

There is no notion of “the previous value” in the desugaring of for comprehensions – they are expressed in terms of map, flatMap, and withFilter.

However, if we had a syntax for zipping in for comprehensions, this could be emulated elegantly using Iterator.iterate, as in:

for {
  x <- xs | y <- Iterator.iterate(0)(y => (y+1) % 3)
  z <- zs
} yield (x,y,z)

with the same semantics as:

for {
  (x, y) <- xs.zip(Iterator.iterate(0)(y => (y+1) % 3))
  z <- zs
} yield (x,y,z)
4 Likes
#5

Sorry, @LPTK, are you suggesting the | syntax, or does that already exist for creating parallel rather than concentric loops?

#6

Yes, I am suggesting it. It does not exist in Scala yet, but it does exists in Haskell already, via the parallel list comprehensions extension, which is compatible with the monad comprehension extension, so you can write things like:

Prelude> :set -XParallelListComp
Prelude> :set -XMonadComprehensions
Prelude> [(x,y) | x <- Just 1 | y <- Just 2]
Just (1,2)
1 Like
#7

It seems to me that the “English” is better if you use & instead of |. This syntax says that x goes through xs and y goes through the iterator. I like the general idea though, especially if it would try to default to a lazy zip that doesn’t have the overhead of making a full collection of tuples. I haven’t stayed completely on top of the details of 2.13, but I believe that the changes to collections were going to make lazy behavior more standard.

I assume that if there were more than two, the pattern would just be ((x, y), z) <- xs.zip(ys).zip(zs) or something like that? It seems like a logical extension that might not even require additional logic if done correctly.

#8

I would personally prefer the currently working zip variant over the syntax sugar variant.

4 Likes
#9

I’d argue that (x,y,z,...).zipped should be used for more than 2 zipped collections (also, it should be generalized to tuples of more than 3 elements, which is currently the limit). Unfortunately, tuple .zipped it does not seem to work with iterators (neither in 2.12 nor in 2.13).

So in fact, along with the new parallel comprehension syntax, I’d also introduce a lazyZipped family of methods for tuples of arbitrary sizes.

#10

In that case, it should zip lazily, just like withFilter (withZipper?)

There is also overlap with the old apfor proposal, which gathered some limited amount of steam, but was generally seen as not significantly improving over typing zip instead of |

#11

I’m trying to type this into the worksheet, and can’t get it to work. Is that excerpt supposed to work? What did I miss?

val xs = List("a","b","c","d")
val zs = List(5,7,13,19)
for {
  (x, y) <- xs.zip(Iterator.iterate(0)(y => (y+1) % 3))
  z <- zs
} yield (x,y,z)
#12

It works in Scala 2.13 with the collections redesign, which makes Iterator more like other collections. To make it work in 2.12, you can use Stream.iterate(0)(y => (y+1) % 3).

(Also, prefer val to var when possible.)

#13

yes val was a typo (fixed), not a philosophical point :sunglasses:

#14

Yes. Stream.iterate works. Although in my opinion, this zip/iterate trick doesn’t express the intent. Admittedly it is not as ugly as trying to express the comprehension in terms of foldLeft.

#15

Apparently, you cannot zip an Iterable with an Iterator. You have to either zip two Iterables, or two Iterators.

1 Like
#16

@jimka2001
There were proposals for applicatives in for comprehensions already:


1 Like
#17

@tarsa, I must admit that I don’t understand the consequences of how applicative desugaring effects my vague proposal. Are you suggesting they are similar and it is worth investigating whether one subsumes the other, or are you suggesting that indeed my successor suggestion is really a special case of applicatives ?

My motivation, in retrospect, was that the situation has occurred several times already for me, that I want to do a certain type of iteration which is almost a for comprehension and almost a foldLeft, but is neither. When I try, as a user, to combine the two, I fail, and when I implement it with fold* it works, but is ugly and does not express the simple intent.

#18

I can implement what I need for my particular case using a small stateful object. It is not as beautiful as what I prefer, but perhaps it is less ugly than an unhappy marriage between fold and for.

case class successor[A](init:A){
  var current:A = init

  def apply(f:A=>A):A = {
    current = f(current)
    current
  }
}


val primes = List(11,13,17,19)
val odds = Array(3,5,7)


val s1 = successor(0)
for {
  w <- primes
  x = s1(_+3)
  s2 = successor(false)
  y <- odds
  z = s2(!_)
} yield (w,x,y,z)

output the following

res0: List[(Int, Int, Int, Boolean)] = List((11,3,3,true), (11,3,5,false), (11,3,7,true), (13,6,3,true), (13,6,5,false), (13,6,7,true), (17,9,3,true), (17,9,5,false), (17,9,7,true), (19,12,3,true), (19,12,5,false), (19,12,7,true))```
#19

For comprehensions are syntactical sugar for something else. When proposing any changes to it, it is essential that you describe the rules that will be applied to de-sugar it. Or, in other words, write the Scala code that will be generated to replace the for-comprehensions.

3 Likes