Does Scala have an equivalent to C# yield?

Question

I'm new to Scala, and from what I understand yield in Scala is not like yield in C#, it is more like select.

Does Scala have something similar to C#'s yield? C#'s yield is great because it makes writing iterators very easy.

Update: here's a pseudo code example from C# I'd like to be able to implement in Scala:

public class Graph<T> {
   public IEnumerable<T> BreadthFirstIterator() {
      List<T> currentLevel = new List<T>();
      currentLevel.add(_root);

      while ( currentLevel.count > 0 ) {
         List<T> nextLevel = new List<T>();
         foreach( var node in currentLevel ) {
            yield return node;
            nextLevel.addRange( node.Children );
         }
         currentLevel = nextLevel;
      }
   }
}

This code implements an iterative breadth first traversal of a graph, using yield, it returns an iterator, so that callers can traverse the graph using a regular for loop, e.g.:

graph.BreadthFirstIterator().foreach( n => Console.WriteLine( n ) );

In C#, yield is just syntactic sugar to make it easy to write an iterator (IEnumerable<T> in .Net, similar to Iterable in Java). As an iterator, its evaluated lazily.

Update II: I could be wrong here, but I think the whole point of yield in C# is so that you don't have to write a higher order function. E.g. you can write a regular for loop or use a method like select/map/filter/where instead of passing in a function which will then traverse the sequence.

E.g. graph.iterator().foreach(n => println(n)) instead of graph.iterator( n => println(n)).

This way you can chain them easily, e.g graph.iterator().map(x => x.foo).filter(y => y.bar >= 2).foreach(z => println(z)).

Holzer

This question is also answered in two other places: #2202382 #2138119 There's also an answer to the issue of how to make it compatible with for statements: #8934726 – Warehouseman

Answer 1

I think the answer (barring changes in 2.8) is that the answer is no, Scala does not have syntactic sugar similar to C#'s yield to write iterators (implementations of IEumerable or Iterable).

However, in Scala you could instead achieve a similar result by passing in a function to the traversal which it would invoke on each item in the traversal. This approach could also be implemented in the same fashion in C#.

Here is how I'd write Traverse in C# without the use of yield:

public class Graph<T> {
   public void BreadthFirstTraversal( Action<T> f) {
      List<T> currentLevel = new List<T>();
      currentLevel.add(_root);

      while ( currentLevel.count > 0 ) {
         List<T> nextLevel = new List<T>();
         foreach( var node in currentLevel ) {
            f(node);
            nextLevel.addRange( node.Children );
         }
         currentLevel = nextLevel;
      }
   }
}

You could then use it like this:

graph.BreadthFirstTraversal( n => Console.WriteLine( n ) );

Or like this:

graph.BreadthFirstTraversal( n =>
{
   Console.WriteLine(n);
   DoSomeOtherStuff(n);
});

Holzer

It's more intuitive with C#'s yield, for sure, though. – Amphictyony

And also you couldn't chain calls this way, as in: graph.BreadthFirstTraversal().Where(...). – Gulfweed

Answer 2

The hijacking of the word yield here distracts from its usual intent: as an entry/exit marker in a coroutine. The C# BreadthFirstIterator in the example above appears to use yield in its coroutine sense; after a value is returned by yield, the next call to active BreadthFirstIterator's IEnumerable will continue with the next statement after yield.

In C#, yield is coupled to the idea of iteration rather than being a more general control flow statement, but within that limited domain its behavior is that of a coroutine. Scala's delimited continuations may allow one to define coroutines. Until then, Scala lacks such a capability, especially given its alternate meaning for yield.

Johnette

I think you've hit the nail on the head Seh. It sounds like Java is getting native coroutines which might make this available in Scala too: weblogs.java.net/blog/forax/archive/2009/11/19/… – Holzer

Answer 3

Yes it does, you may want to look at this question for the answer: What is Scala's yield?

Here is the docs from Scala for this type of construct: http://www.scala-lang.org/node/111

UPDATE:

This blog talks about C# yield and Scala: http://hestia.typepad.com/flatlander/2009/01/scala-for-c-programmers-part-1-mixins-and-traits.html

He goes into some detail about how extensions are being used to make IENumerable work compared to using Traits in Scala.

So, you are correct that yield won't function the same way in Scala as C#, but that is because they are very different, and so if you want to do this BreadthFirst as a Trait then you can call the map() and filter and foreach methods, just as you would in C#, but the trait will help solve the problem of how to traverse the collection.

Doze

Thanks James, I'll check those out. – Holzer

No, they are not the same. Scala 2.7.x does not have an equivalent construct as C#'s "yield". In Scala 2.8.x though, thanks to the Delimited Continuation compiler plugin, it is possible to code a construct using continuation to mimic C# "yield" fairly easily. – Stome

Any thoughts on how I reconcile James and Walter's apparently contradictory answers? – Holzer

James, I tried out scala's comprehensions, so far it looks to me like they are always in the form "for enums yield item", and you can't do much else. In C# its a different mechanism, allowing you to call yield at any point in your method, multiple times, allowing you to create an iterator for any data, whereas it looks like comprehensions in Scala are a nice way to write sequences. – Holzer

@Alex Black - Hopefully tonight I will have time to look at them closely and compare better. – Doze

Answer 4

Even though Scala has a keyword yield, it's quite different from the C# yield, and Ruby's yield is different from both. It seems to be a wildly overused keyword. The use of yield in C# appears very limited at first glance.

To do the same in Scala, you could define your own high-order function. In English, that means a function that takes a function as a parameter.

To take Microsoft's example, here's a Scala method:

object Powers {
  def apply(number:Int, exponent:Int) (f:(Double) => Any) = {
    (new Range(1,exponent+1,1)).map{exponent => f(Math.pow(number, exponent))}
  }
}

Now you have your "iterator":

scala> Powers(2,8){ println(_) }
2.0
4.0
8.0
16.0
32.0
64.0
128.0
256.0

Notes:

• Powers(2,8) is the same as Powers.apply(2,8). That's just a compiler trick.
• This method is defined with two parameter lists, which might be confusing. It just allows you to do: Powers(2, 8){ println(_) } instead of Powers(2, 8, {println(_)})

Scala: 1, C#: 0

---

Update:

For your just-added example, write traverse that does the traversal you want without thinking about how you are going to use it. Then add an extra parameter by adding (f(Node) => Any) after the traverse parameter list, e.g.

def traverse(node:Node, maxDepth:Int)(f(Node) => Any)) { ... }

At the point in traverse where you have a value you would yield with in C#, call f(yieldValue).

When you want to use this "iterator," call traverse and pass a function to it that does whatever it is you want to do for each element in the iterator.

traverse(node, maxDepth) { (yieldValue) =>
  // this is f(yieldValue) and will be called for each value that you call f with
  println(yieldValue)
}

This is a basic case for "functional programming" and you should make sure you understand it to be successful with Scala.

Overmantel

Thanks Alex, thats a great example. Question 1: how does Powers(2,8) work? Question 2: in C#, with yield, I can easily write an iterator for any data structure, just by 'yielding' out each item.. E.g. I can easily make an iterator that goes depth-first through a DAG. how would I do that in Scala? – Holzer

Alex, reading it over again, I think your example is a bit off base. 1. Its not lazy (I don't think) like the C# example from Microsoft is. 2. You could implement it it that way in C# too: (e) => Enumerable.Range(e, e+1).Select( n => f( Math.Power(e,n) ) ) – Holzer

a) How does Powers(2,8) work? I'm not sure what you are asking. The map call loops through each element of the Range (which is essentially List(1,2,3,4,5,6,7,8)) and calls the method that is passed with f(number,exponent) where exponent is the current element of the range. b) Sure, I think you can make this do anything C#'s yield can do and a lot more c) It is lazy, if by that you mean it calls println for each result as it is calculated. d) Sure you could do that in C#, but it doesn't demonstrate a custom iteration. – Overmantel

When I asked how does Powers(2,8) worked, I meant what is it that enables you to write Powers(2,8) instead of Powers.apply(2,8). I tried this with an Object of mine and it didn't work. – Holzer

I read your update. I think the gist of my question is not how to use such a Traverse function, but how to write one. I showed how to write one in C#, and I'm curious how to write one in Scala. – Holzer

What is a "custom iteration", and what is it about the C# in my comment that makes it not a "custom iteration"? – Holzer

(e) => Enumerable.Range(e, e+1).Select( n => f( Math.Power(e,n) ) ) uses the built in iterative method Select. In your tree example, there is no built in iterator for depth-first traversal so you need to write one. My example shows how to do that using a trivial case where there are simpler options that do not require writing an iterator. – Overmantel

How to write a traverse function is a completely different question.... You would use a pretty simple recursive method, but it has nothing to do with the question "Does scala have an equivalent to C# yield." You should ask a new question: "How do I implement a depth first traversal properly in Scala?" – Overmantel

Regarding how Powers(2,8) works, I don't know why it wouldn't work for you. Example? If you do it on a class instead of an object, you need to use an instance of the class instead of just the object name, e.g. (new Power())(2,8). – Overmantel

Alex, thanks the comments. I guess my main point was that if Scala has an equivalent to Yield, then I could just port the traversal above. But, I can post a new question. – Holzer

Regarding how Powers(2,8) works, it does work, my mistake. How does it work? Does Powers(2,8) just invoke the first method on the Object? – Holzer

Alex, your traverse example is interesting but not what I'm asking about. Your traverse method takes a function as an argument which is then invoked on each node in the graph. Its quite similar, and achieves the same result I think, but not what I'm asking about. See my second update in the question. – Holzer

Well, there is no C# yield equivalent in Scala. C#'s yield is of limited. You can basically port the algorithm by following my instructions in the update. Write the traversal, then add the function. You've already written the traversal... – Overmantel

Your update is partially correct. However the reason C# provides that capability is likely because C# did not start out with first class functions. The functional way is far more flexible and you don't lose anything. You can chain methods if you have the method return List[T] instead, the same way map works. graph.traverse{}.filter{.value > 1} would select all nodes and then filter by the value. – Overmantel

I'd recommend getting comfortable with higher order functions instead of trying to avoid them. In your example, port it to Scala and change the name for BreadthFirstIterator() to traverse(), add a function parameter, and call f(Node) instead of yield. Done. – Overmantel

This has been an interesting discussion, thanks. A couple comments: iterators (such as java's Iterable) are useful, and using List[T] instead of that loses their advantages. The use of higher order functions here is the same as the visitor pattern but applied to functions. It is also easily implemented in C#, e.g. IEnumerable Traverse( Func<T> f ) { do traversal here, call f(node) }. Then graph.Traverse( n => { println(n); dostuffToNode(n) } ). – Holzer

Can you comment a bit more on what are the advantages of having the Traverse function take a function as an argument instead of returning an iterator? – Holzer

I'm not sure I can give you a complete answer because I am only a recent convert to the functional style. If you look at the difference in code there are some apparent differences. For one, you don't need to write a for loop in the functional version. Iterators are useful, but they are error prone and unnecessary. Iterators are inherently stateful, which introduces a whole class of potential bugs that don't exist in the functional style. I'm not sure which advantages you mean are lost without iterators. – Overmantel

1. I was hoping you'd elaborate on what you wrote before: "The functional way is far more flexible". 2. The iterator versions don't need a for loop, e.g. breadthFirstIterator.map( n => n.name ) 3. See Chapter 12 of Scala by Example "Computing Streams" for some info on advantages of iterators vs lists. bit.ly/XDkzK – Holzer

My point is that the general structure of passing a function as a parameter is more flexible than C#'s yield, which is point solution for iterators. C#'s approach is not dis-similar functionally, it's just less useful generally. C#'s technique introduces the possibility of partially consumed Iterators being passed around. Regarding 2) yes, there is no for loop in the "client". I'm not sure how I can elaborate. I prefer tree.traverse{_} to val arr = Nil; for(node <- tree.traverse){arr.append(node)} or similar. – Overmantel

1. Your statements of "generally less useful" are "generally not useful" :) I'd love to here some solid advantages of function as argument vs iterator (scala, C# or otherwise). Here are advantages of the iterator approach: only what is needed of the sequence need be generated; only what is needed at a given moment need be stored in memory; regular scala methods like map, filter etc can easily be chained on. 2. There are no for-loops added by implementing traverse as a function-returns-iterator instead of implementing it as a function-takes-function. – Holzer

This has been an interesting topic to stew on. The ability to terminate mid-iteration is good point. Either the function would have to be written to allow it or you would have to use an exception (which is probably not appropriate). I can't think of another way. Memory is not an issue for functions (look again.) The regular Scala methods map/filter/etc ARE functions, not iterators although some may be implemented using iterators. – Overmantel

Although C# iterators can be stateful, they don't have to be. What they allow is writing in a procedural style. There's no reason why functional languages shouldn't support syntax sugar to emulate procedural style. Even the "daddy", Haskell, supports this through its syntactic sugar over the core set of operations on a monad, allowing (for example) IO operations to be written in a way that looks like procedural coding (which is important when the order of the IO side-effects is bound to be crucial). In other words, even the purest language has to find an acceptable way to be impure. – Dachau

Looks like this type of functionality is coming to Java, perhaps Scala too then... weblogs.java.net/blog/forax/archive/2009/11/19/… – Holzer

Answer 5

You can do this in Scala >= 2.8 using an implementation of generators in terms of delimited continuations. You'll need the continuations plugin and then something along these lines,

import scala.continuations._
import scala.continuations.ControlContext._

object Test {

  def loopWhile(cond: =>Boolean)(body: =>(Unit @suspendable)): Unit @suspendable = {
    if (cond) {
      body
      loopWhile(cond)(body)
    } else ()
  }

  abstract class Generator[T] {
    var producerCont : (Unit => Unit) = null
    var consumerCont : (T => Unit) = null

    protected def body : Unit @suspendable

    reset {
      body
    }

    def generate(t : T) : Unit @suspendable =
      shift {
        (k : Unit => Unit) => {
          producerCont = k
          if (consumerCont != null)
            consumerCont(t)
        }
      }

    def next : T @suspendable =
      shift {
        (k : T => Unit) => {
          consumerCont = k
          if (producerCont != null)
            producerCont()
        }
      }
  }

  def main(args: Array[String]) {
    val g = new Generator[Int] {
      def body = {
        var i = 0
        loopWhile(i < 10) {
          generate(i)
          i += 1
        }
      }
    }

    reset {
      loopWhile(true) {
        println("Generated: "+g.next)
      }
    }
  }
}

Piranesi

Answer 6

As already mentioned you could create a Generator using the continuations-plugin to create a yield which is exactly behaving like C#:

import scala.util.continuations._

object GenTest {

    val gen = new Generator[Int] { def produce = {
        yieldValue(1)
        yieldValue(2)
        yieldValue(3)
        Thread.sleep(1000)
        yieldValue(42)
  }}


    def main(args: Array[String]): Unit = {
        for (v <- gen) {
            println(v)
        }
    }
}

abstract class Generator[E] {

    var loopFn: (E => Unit) = null

    def produce(): Unit @cps[Unit]

  def foreach(f: => (E => Unit)): Unit = {
        loopFn = f
        reset[Unit,Unit]( produce )
  }

  def yieldValue(value: E): Unit @cps[Unit] =
    shift { genK: (Unit => Unit) =>
      loopFn( value )
      genK( () )
      ()
    }

}

Hoagland

Yes it does, it uses the new CPS-Compiler-Plugin with "scalac -P:continuations:enable". I have no idea whether the plugin will be integrated by default. – Hoagland

first class support for generators would be nice, maybe one day. – Holzer

Using Scala 2.9.1 I receive an error: java.lang.NoSuchMethodError: scala.util.continuations.package$.shift(Lscala/Function1;)Ljava/lang/Object. Any idea what I'm doing wrong here? – Shushan

Answer 7

Coming from a C# background and having debugged the Scala code from hotzen(adapted to Scala 2.11.6), I must say this continuations usage comes close to the C#-yield equivalent. I do not know if continuations still would function similarly if multiple Generators were needed, running all in the same methods or possibly spread over different methods, but I am happy continuations do exist, so that I am not forced to work with multiple threads to achieve similar, or pass along call-backs.

Hitchcock