Just reviewed a gem from Programming Scala. Of all the Fibonacci implementations I’ve seen, my new favorite is below. Its 1 statement long, and there’s not a recursive function in sight:
lazy val fib: Stream[Int] = Stream.cons(0, Stream.cons(1, fib.zip(fib.tail).map(p => p._1 + p._2)))
If you have not seen that zip trick before, follow me on a little explanation. The code defines a Stream — a non-strict iterable — that begins with two literal values “0″ and “1″. The stream then continues the Fibonacci sequence by zipping the sequence to itself. More specifically, to its own tail sequence.
This figure illustrates what the zipper is creating.
The tail value of the initial sequence is just the sequence starting with the literal value “1″. The zipper creates Pairs out of the each member of the sequence pairwise joined with the next member of the sequence.
The first pair is (0, 1).
The second pair is then (1, 0 + 1) = (1, 1).
The third pair is then (1, 1 + 1) = (1, 2).
The forth pair is then (2, 1 + 2) = (2, 3). And so on.
The coolest part is of course the complete lack of apparent recursion. The whole sequence is lazily evaluated, so the Stream takes up little space — one new Stream object per element in the sequence.
We can generalize this stream-zipping technique. When the value of a Stream element n can be calculated from the previous k sequence members, we can use a k-ary version of this technique. That is, if the stream theStream member n can be defined by some function s:
def theSeq(n) = s(theSeq(n-1), theSeq(n-2), …, theSeq(n-k))
We can define the stream in a single statement thus:
Here, for example, is a rolling average of the last 4 members of a Stream[Double]:
val data: Stream[Double] = ... val padded_data = Stream.fill(4)(0.0) ++ data ++ Stream.fill(4)(0.0) // Note: tail padding not a problem even if data is infinite. /* Here's where the stream is joined to itself. Also, mapping the (((Int,Int),Int),Int) to (Int,Int,Int,Int) for readability. Can't be recursively defined */ def zip4[A](str: Stream[A]): (A,A,A,A) = (str zip str.tail zip str.tail.tail zip str.tail.tail.tail) map { p=> (p._1._1._1, p._1._1._2, p._1._2, p._2)} /* Could be recursively defined in terms of base type Product */ def avg4(p: (Double,Double,Double,Double)): Double = (p._1, p._2, p._3, p._4) / 4 /* Finally, generating the rolling-average stream */ lazy val avg_rolling: Stream[Double] = zip4(padded_data) map (avg4)
You can use Iterator.sliding(n) to get a similar effect. And that does work on infinite, non-strict streams. Personally, I just though this technique was so cool, and it does have the benefit of strongly-typed tuples. (Iterator.sliding() simple provides more Streams. Try it out if you’re curious.)
I’m laboring under an extremely waterfall project right now. A client asked for a set of REST-style services, but the client’s making me write approx. 200 pages of documentation before writing the code.
(Most of the documentation could be replaced by a far smaller, and more logically accurate, Operation State Modeling description. But that’s not what I’m here to talk about…)
Writing the REST-style interface, something pretty interesting occurred to me. I’ll need the casual reader to put on his thinking cap before moving on here, so please do that if you haven’t already. I’ll wait…
Let’s start with what a future is: To review, as the linked document says, a future is “…a place-holder for the undetermined result of a (concurrent) computation…”. Let’s say there’s a value your program needs, but the computation or retrieval of that value takes a significant amount of time or resources. Instead of synchronizing (waiting) for the value to be computed, you could spin off an asynchronous process to compute/retrieve the value; alternatively, you could leave a placeholder object that only starts the complex computation/retrieval on demand. Either way, your program leaves in place a placeholder object know as a future.
When your program eventually comes back to the future object asking for the value, the the future either a) hands it back immediately if it has a cached copy; or b) the main program synchronizes (blocks) until the background process completes its computation/retrieval.
The object graph produced by Hibernate when you make an object query uses futures to represent unretrieved values. The query result Hibernate produces is an object graph with placeholder Collections representing lazy relationships. The lazy collections initially don’t have any data in them, but instead have just enough data in them to generate a secondary Hibernate query. When the program tries to access a lazy collection’s contents, only then does the Collection query a Hibernate entity manager for the collection of related objects it represents. The placeholder Collection objects are thus futures.
When a REST-style service response contains a link URL/URI reference to another entity, you can think of that link as a kind of future in the same way as a Hibernate lazily populated Collection. One could easily populate a graph of objects from JSON source, replacing URL/URI references with lazy future objects.
In Scala, a Future[X] extends Function1[X], meaning that Future is Function subtype, so you can use a Function1[_] type to represent URL/URI-based references:
/** * Invoice can be deserialized from JSON such as: * { * id: "XYZ", * lineItems: "http://somewhere.com/inv/XYZ/lineItems" * // ^^^ URL; serialized representation of * // a List[LineItem] future. * } **/ class Invoice(val id: String, val lineItems: () => List[LineItem], ...) { ... }
You think you know how to define a for loop, do you? Scala has 4 different kinds.
Unit
for(mbr <- collection) { println(mbr) }
Not surprisingly, this loop prints out the members of the collection, in order that they are returned by the collection’s iterator. In fact, this loop construct is translated exactly to
collection.foreach(mbr => println(mbr))
val transformed = for(mbr <- collection) { yield transform(mbr) }
Each time through this example loop, the result of the loop is yielded out. All the yielded results are collected in to a single iterator. This type of for loop is syntactic sugar for the following statement
val transformed = collection.map(mbr => transform(mbr))
That’s right, a simple for…yield loop is just syntactic sugar for Iteratable.map().
Iteratable.map()
Infinite (or extremely large) iterables, usually implemented as Streams or Ranges, are a bit tricky. For example, it probably wouldn’t surprise you to learn that the following traditional for loop will not terminate (at least not in your lifetime):
Stream
Range
for(i <- 0 to 100000000000) println(i)
But executing this next for…yield loop does not cause an indefinite wait — it works fine! (Go ahead, try it out!)
val numberStrings = for(i <- 0 to 100000000000) yield ("" + i)
How can this be so? You need to know that o to 10000000000 results in a Range object, which is a non-strict iterator. That is, it is an iterator that calculates the “next” value as you iterate through it, rather than pre-computing all members up front and storing them in memory when the Range is created.
o to 10000000000
Iteratable functions that yield a scalar result, like foldLeft() or length() or any catamorphic function, are not safe to use with non-strict iterators, because these methods must iterate over the entire iteratable’s contents to produce a result. The foreach() method falls in to this unsafe category — foreach()’s return type is Unit, which is considered scalar.
foldLeft()
length()
foreach()
Remember the traditional for loop is just syntactic sugar for a foreach() call, and this explains why looping over the range with a traditional loop causes an indefinite wait.
Iteratable functions that yield results of similar size to the input, such as map() and flatMap(), are perfectly safe to use with non-strict iterators. These methods themselves yield non-strict iterators, and don’t need to iterate over the source iterator’s contents to yield a result.
map()
flatMap()
The for…yield loop is just syntactic sugar for a map() call, and this explains why looping over the Range with a for…yield loop doesn’t cause an indefinite wait.
End of Interlude
// Using the guarded for...yield loop syntactic sugar val oddSquares = for(i <- 0 to 10000000000 if i % 2 == 1) yield (i*i) // Exactly the same thing as val oddSquares = (0 to 10000000000).filter(i=>i % 2 == 1).map(i=>i*i)
And as the example implies, this for loop style is non-strict collection safe (because both filter() and map() are non-strict safe).
filter()
// Long-winded nested for loop val pairsThatSumTo100 = for(i <- 0 to 100; j <- i to 100 if i + j == 100) yield Pair(i, j) // Slightly shorter but harder to read raw form that gets compiled val pairsThatSumTo100 = (0 to 100).flatMap(i=>(i to 100).filter(j=>i+j==100).map(j=>Pair(i,j)))
Note that nested for loops are also non-strict safe, because filter(), map() and flatMap() are all non-strict safe. Only the traditional for loop is not safe for non-strict use.
My first not-completely-trivial task in Scala is to implement the equivalent of the F# pipe operator.
The pipe operator is syntactic sugar that makes certain patterns of code easier to read. When generating a final result by a sequence of value calculations its easier to read the sequence from left -to-right, but Scala only supports passing values to functions in function(value) form, which basically forces the eyes to read the sequence in right-to-left order — rather unnatural.
Here is one way of expressing a sequence of calculations, relying on local vals to hold intermediate sequence values:
def shuffle(str: String): String = . . . def randomize(str: String): String = . . . def camelCase(str: String): String = . . . def futzWith(str: String): String = . . . def applySeveralStringTransforms(str: String): String = { val shuffled = shuffle(str) val randomized = randomize(shuffled) val camelCased = camelCase(randomized) futzWith(camelCased) }
Which reads easy enough — the result of the function is the result of shuffling, randomizing, camel-casing and finally futzing with the original String. And here’s the equivalent calculation as a single expression, without local vals. Note how the sequence of calculations is performed from right to left — first shuffle, then randomize, etc.
def applySeveralStringTransforms(str: String): String = { futzWith(camelCase(randomize(shuffle(str))) }
A pipe operator allows you to pass the result of an expression to the right, preserving left-to-right visual order while still being semantically equivalent to either form above:
def applySeveralStringTransforms(str: String): String = { str |> shuffle |> randomize |> camelCase |> futzWith }
My first attempt has me defining a right-associative operator, using Odersky’s pimp-my-library technique, to generate a temporary PipeFunc object which has a “|>:” operator. That is, I’m using a couple tricks to get the compiler to automatically rewrite this
x |>: func
like this
(new PipeFunc(func)).|>:(x)
Since my operator “|>:” ends with a colon, Scala treats it as a “right-associative” function — a function of the right-operand “func”, rather than a function of the left-operand “x”. A very short-lived PipeFunc object gets created by an implicit conversion, and this object has a method named “|>:” that gets applied.
Here’s the definition of my operator:
object Pipeline { implicit def toPipeFunc[X, Y](func: X => Y) = new PipeFunc(func) class PipeFunc[X, Y](func: X => Y) { def |>:(value: X): Y = func(value) } }
There are immediate problems with this approach. Because of how Scala 2.7.5 (the version I am using) parses this code, it is apparently unable to recognize that the right-hand side of |>: is a function reference. So the following actually causes a compiler error:
// complains "|>:" is not a function of type Unit "Hello, World!" |>: println
I’m not sure why this is, but using parens fixes the problem, but makes the expression too surprising and ugly for my taste. I’m going to have to go back to the drawing board…
Instead of augmenting the function argument on the right, I’ll try augmenting the value argument on the left with a “|>” operator. I’ll use the same pimp-my-library technique to use an implicit conversion of the left-hand object to a temporary object that has a “|>” operator, which takes a function as its right-hand argument. That is, I’m using a couple tricks to get the compiler to automatically convert this
x |> func
to this
(new PipeLink(x)).|>(func)
Here’s my code for the operator definition:
object Pipeline { implicit def toPipeLink[X](v: X): PipeLink[X] = new PipeLink[X](v) class PipeLink[X](value: X) { def |>[Y](func: X => Y): Y = func(value) } }
OK, works correctly, and doesn’t have any of the problems that the right-associative operator had.
I do have a hidden performance issue: creation of an very-short-lived temporary object. Consider how the the following single expression gets rewritten by the Scala compiler:
str |> shuffle |> randomize |> camelCase |> futzWith
to this:
(new PipeLink((new PipeLink((new PipeLink((new PipeLink(str)). |>(shuffle)).|>(randomize)).|>(camelCase)).|>(futzWith)
Ugly – obviously; wastefully creates too many objects – also true. 4 temporary PipeLinks created and thrown away. The JVM GC is pretty good at handling short-lived objects, but this is terribly wasteful. I can’t think of a way of getting rid of temporary objects — any suggestions greatly appreciated!
Only after implementing did I find that Steve Gilham had already posted his implementation of the pipe operator. He immediately went with a left-associative operator implementation. Must be a clever guy! Both his solution and mine suffer from creating a temp object with each invocation of the pipe operator.
