Successor syntax for for comprehensions

[jimka2001]

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.

[martijnhoekstra]

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?

[jimka2001]

@martijnhoekstra

What would this desugar to, in either the comprehension or the loop case?

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.

[LPTK]

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.

@jimka2001

how it should desugar is just to make the previous value of y available in scope

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)

[jimka2001]

@LPTK

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

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

[LPTK]

@jimka2001

are you suggesting the | syntax

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)

[MarkCLewis]

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.

[Jasper-M]

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

[LPTK]

@MarkCLewis

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.

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.

[martijnhoekstra]

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 |

[jimka2001]

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)

[LPTK]

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.)

[jimka2001]

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

[jimka2001]

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.

[curoli]

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

[tarsa]

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

New syntax: applicative desugaring in for comprehensions (with PR)

Hello everyone, Just to make things clear: this is not April fools Inspired by comonadic comprehensions proposal and the recent success of Comma McTraily I was thinking about how we could express applicative comprehensions in Scala. This could be useful not only for people using typelevel style (I suppose, I’m not one of them) but also for mere mortals like me and people to which the word “applicative” says absolutely nothing. And I think I may have found a simple and totally co…

Sequencing in for-comprehensions

Sequencing in for-comprehensions It is often possible and desirable to make multiple extractions without doing flatMap steps. This can be achieved by making Cartesian products repeatedly or sequencing lists of objects. Alternative way for avoiding flatMaps is to devise special auto-generated syntax like for Validation in scalaz. In general, however sequencing can work as a general abstraction for such purposes. Sequencing objects instead of flatMapping them can solve performance or usabili…

[jimka2001]

@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.

[jimka2001]

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))

[dcsobral]

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.