I’ve been playing around with a few ideas on how to apply a lens-like construct on arbitrary Scala collections that also combines the power of predicate composition as opposed to the more standard notion of functional composition. To ask a silly question, what if we could do something similar to a Scalaz Lens with a “get,” “set,” and “mod” but applied to a collection? What if the actions we’d taking using this data structure were based upon some predicate condition? What if we wanted to be able to solve Fizz Buzz by updating only the portions of a list without writing a function that was wholly specific to Fizz Buzz. Something like…
val fizz = Choose({x: Int => x % 3 == 0})
val buzz = Choose({x: Int => x % 5 == 0})
val fizzbuzz = fizz and buzz
val myList = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
val result = fizz set("Fizz", buzz set("Buzz", fizzbuzz set("FizzBuzz", myList)))Granted, the output type of the List would differ from the input type of the List but in a perfect world, magic.
This isn’t a terribly new idea. In fact, something very similar has already been done before. Where? Haskell of course! Take a look at Haskage: lens. In it you’ll see a number of “odd” structures of which one stands out in particular, Traversal. I have to admit, Traversal is pretty nifty, pretty powerful, and most assuredly beautiful. I’m about to bastardize it but like any neophyte with a gun, ready-shoot-aim.
Making Choices
In my Predicates library I laid out 22 predicate traits with the following operators:
- and
- or
- xor
- nand
- nor
- nxor
with the addition of a Not operator being defined for each one. It worked great with TraversableLike‘s filter method (and still does if I’d ever publish it.) However, I think I half wrote fifteen different versions of the following, each with their own “doStuff” method, throughout the code I worked on:
case class MyClass(pred: SomeType){
def apply(myCollection: SomeCollectionType) = myCollection map{
if(pred(x)) doStuff(x) else x
}
def and(that: MyClass) = copy(x => pred(x) && that.pred(x))
}Clearly, I wanted something that also had those operators but itself was not a predicate. Something that combined action with filtration like this:
class PredicatedMod[A](pred: A => Boolean, f: A => A){
def apply[Repr <: TraversableLike[A, Repr]](that: Repr) = that map{
if(pred(x)) f(x) else x
}
def and(that: ChooseFunction[A]) = new ChooseFunction(pred and that.pred, f)
def or(that: ChooseFunction[A]) = new ChooseFunction(pred or that.pred, f)
//def xor, def nand, etc.Simple concept and indeed is expressible in a few lines of code. In fact, PartialFunction can do much of the same albeit without the predicate composition:
myList map{
case x if pred(x) => f(x)
case x => x
}However, this only handles the case of “mod” of a Lens-like construct (and “set” for constant functions, f(x) = b.) It does not handle the case of “set” wherein we have some contained concept of iteration or mutation within the function we’d like to apply (assuming it is referentially transparent.)
Choosing Wisely
So when is a function referentially transparent but contains some idea of iteration or mutation? When it forms a locally trapped closure around mutating state like this:
class Set[A](myList: List[A]) extends (List[A] => List[A]){
def apply(that: List[A]) ={
val iter = myList.toIterator
that map{ x =>
if(iter hasNext ()) iter next () else x
}
}
}That’s a PITA to have to write repeatedly which is why the Scala collections library has a patch method defined on SeqLike. What is more is that the patch method is a little more powerful than the above function would indicate as it also allows the caller to specify a start index and length of substitution. Unfortunately it is an all or nothing type of action, with a defined start and finish that runs over the entire segment.
The important thing to take away is not that patch is not amenable to application based upon a predicate condition (it isn’t) but rather that it works on an entire collection at once. To put it simply, we could get away with the PartialFunction as nearly enough in the last section because it worked piece-wise on a point by point basis wherein each item of the collection was independent from the other. Here, the substitution depends on how many previous values were substituted. To say this another way, each subsequent action in a collection is dependent upon the accumulated set of actions which had happened prior to that point.
class PredicatedSet[A](pred: A => Boolean, myList: List[A]) extends (List[A] => List[A]){
def apply(that: List[A]) ={
val iter = myList.toIterator
that map{ x =>
if((iter hasNext ()) && pred(x)) iter next () else x
}
}
}Like I said before, it’s a PITA to write again and again not because it takes up a lot of code but rather because it uses so little code we’re tempted not to package it up. Generalizing this to more than one collection type or family of collections is where the “fun” starts to happen and where it’s easy to make a small mistake.
Creating Choices
That “fun” part, I did it for you. I created what I’m calling a Choice in a new package of my Predicates library. As an embodiment of a “portable filter” which works on the non-parallel versions of the Scala collections library it is also contravariant. I’ve also made two variants of these: Choose and Ignore. The later works by taking the inverse of the contained predicate condition for application in the “get,” “set,” and “mod” member functions. Finally, a Choice composes, producing another Choice which is the union (and-ing) of the underlying predicates.
The example in the introductory paragraphs? It works, sorta. It works if you cast the List to a List[Any]. The “mod” and “set” functions don’t allow for the changing of the return type. They can’t. What if the predicate condition were never to be satisfied as in the case of Never1? No change, no modification and thus purely an expensive pass-through.
I’m still having some fun with the library and so I haven’t released it (ok, I have two left thumbs when it comes to getting anything on Maven or Sonatype.) I’m potentially planning on adding in a “switch” function which you could think of as “modOrElse” that looks like:
val choice = Choose({x: Int => x %2 == 0})
val processed = choice switch(myCollection, f, g)and could conceivably add in “partition,” “fold,” and “scan” member functions.
In the Predicates section, I’m still working on a few more ideas around PartialFunctions (like actually having 22 of them) and a simple way of lifting a FunctionN into a PartialFunctionN using an implicit class. It’s a work in progress when I’m not spending time with loved ones or catching up on reading that I’ve missed these past few years.
Anways, if you’ve got ideas or if there’s something you’d like to see in it, fork and contribute ’cause my own pace is quite slow.
