Sunday, July 31, 2011

Partially unexpected effects of chaining partial functions in Scala

People who learn Scala usually agree that pattern matching is a great feature which helps make your code more expressive. Some time later they also discover that partial functions used in the match statement can also be used separately. And since partial functions are full-blown functions, you can combine them in a couple useful ways:



f1 orElse f2

Combines two partial function in a new one; if f1 is not defined in its argument, tries f2.

f1 andThen f2

Applies the result of f1 to f2. This means that the output of f1 must be a type compatible with the input of f2



orElse


As others have discovered, you can combine a list (TraversableOnce really) of partial functions into one with reduce. What's not so obvious though is that the way you combine them can lead to unexpected perfomance consequences.


In order to easily create a lot of partial functions to test, we will create a higher-order function to generate them (if you're used to Java, you can call it a factory). The produced partial function will print a short message when its isDefinedAt method is called (not when it's applied):



def genPF(defined: Int): PF = { case i if {println(defined); defined == i} => i }
val f123 = 1 to 3 map genPF reduceLeft(_ orElse _)


Let's try it:



> f123(1)
1
1
1
> f123(2)
1
2
1
2
1
2
> f123(3)
1
2
3

Wait, what? The isDefinedAt method is called up to 6 times. It gets even worse with a bigger number of composed functions.



val f1to5 = 1 to 5 map genPF reduceLeft(_ orElse _)



> f1to5(2)
1
2
1
2
1
2
1
2
> f1to5(3)
1
2
3
1
2
3
1
2
3
> f1to5(4)
1
2
3
4
1
2
3
4

Let's take a closer look at the definition of isDefinedAt and apply of the function created with orElse:



def orElse[A1 <: A, B1 >: B](that: PartialFunction[A1, B1]) : PartialFunction[A1, B1] =
new PartialFunction[A1, B1] {
def isDefinedAt(x: A1): Boolean =
PartialFunction.this.isDefinedAt(x) || that.isDefinedAt(x)
def apply(x: A1): B1 =
if (PartialFunction.this.isDefinedAt(x)) PartialFunction.this.apply(x)
else that.apply(x)
}


When you apply a composed partial function, we first check if it's defined in either f1 or f2, and then we check f1 again, so that we know which one to call. This means that in the worst case, isDefinedAt for f1 is called twice.


Given this, we can explain what happens here. The isDefinedAt delegates to the composed functions' methods, and when it's called twice... you know what happens when we do this again and again. We can fairly easily find out that isDefinedAt is called k * (n - k + 1) times, where n: number of composed functions, k: the first function that matches.


Luckily, there is an easy solution to combine partial functions in a more efficient way. We can use reduceRight, where isDefinedAt for each composed function is invoked at most twice. Verifying this and finding out why is left as an exercise for the curious reader (as you undoubtedly are, since you're reading this).




andThen


You would think that f1 andThen f2 should be defined only in the cases when the results of f1 are defined in f2



val doubler: PartialFunction[Int,Int] = { case i if Set(1,2) contains i => i * 2 }
val f = doubler andThen doubler


Of course, that's not how it works. In order to find out if the output of f1 is a valid input for f2, we would need to execute the function, and it's better not to do this in case it has side effects. This means that we cannot rely on calling isDefined for the combined function to avoid MatchErrors:



> f isDefinedAt 2
res3: Boolean = true
> f(2)
scala.MatchError: 4
...

Conclusion: when you're looking for performance, it always help to understand how the abstractions you're using decompose into simpler building blocks.


24 comments:

lester said...

Vassil,

Thanks for the interesting article and important details about PartialFuction's composition!

Btw, I ran f123 fuction just to clear some details for myself and results of f123(2) PF application were a little bit different:


scala> f123(2)
1
2
1
2
res1: Int = 2

jhon apps said...

some of the binery functions are very hard to understand and for work as well as.

make a facebook application

jojopig.com said...

Agreed to Jhon. Nice Post By the way. Thanks.

Term Papers said...

Very Good Article About "Partially unexpected effects of chaining partial functions in Scala"

Post by
Term Papers

jojopig.com said...

thanks for the posts. good stuff.

Unknown said...


ROCKET SPANISH
is designed to be the easiest to follow system for learning how to speak Spanish available. Rocket Spanish is an interactive course that makes you want to study. Also, it's practical. You'll discover exactly what to say in virtually all situations.
With Rocket Spanish, you are going to learn Spanish rapidly, effectively, and easily. You are going to be able to speak at a restaurant, at an airport, with new friends… in basically every situation you can think of!

Shoofi said...

Good ideas delivered..
Way of coding is great..
شوفي

Unknown said...


This information really worth saying, i think you are master of the content and thank you so much sharing that valuable information and get new skills after refer that post.

Android Training in Chennai

Sri akshaya said...


Really very nice blog information for this one and more technical skills are improve,i like that kind of post.

Content marketing services in chennai

Suseela said...



What an awesome post, I just read it from start to end. Learned something new after a long time.


SAP SD training in Chennai

Shalini said...

I just see the post i am so happy to the communication science post of information's.So I have really enjoyed and reading your blogs for these posts.Any way I’ll be replay for your great thinks and I hope you post again soon.

Digital Marketing Company in India

Mahalya sree said...

Great and really helpful article! Adding to the conversation, providing more information, or expressing a new point of view...Nice information and updates. Really i like it and everyday am visiting your site..
Office Interior Designers in Coimbatore
Office Interior Designers in Bangalore
Office Interior Designers in Hyderabad

Unknown said...

Thanks for sharing this kind of information.
Interior Designers in Chennai
Interiors in Chennai
Good Interior Designers in Chennai

Nicole Bolton said...

What you have written in this post is exactly what I have experience when I first started my blog.I’m happy that I came across with your site this article is on point,thanks again and have a great day.Keep update more information.
Fleet Management Software
Manufacturing ERP
Logistic ERP
Logistics Software
Human resources management software

Unknown said...

Fertility is the natural capability to produce offspring. As a measure, fertility rate is the number of offspring born per mating pair, individual or population.Human fertility depends on factors of nutrition, sexual behavior, consanguinity, culture, instinct, endocrinology, timing, economics, way of life, and emotions.Greate thinks of a fertility center for humans.

Fertility Center in OMR

liza said...


Very enjoyable to visit this blog and find something exciting and amazing.
Deer Hunting Tips Camping Trips Guide DEER HUNTING TIPS travel touring tips

liza said...


Thank you for such a sweet tutorial - all this time later, I've found it and love the end result. I appreciate the time you spent sharing your skills.
travel trekking tips
see the link Tent Camping 101 Exploring Smithriver

Chiến SEOCAM said...

Anjeun gaduh artikel hébat

lưới chống chuột

cửa lưới dạng xếp

cửa lưới tự cuốn

cửa lưới chống muỗi

afibiz said...

This is most informative and also this post most user friendly and super navigation to all posts... Thank you so much for giving this information to me.. 
interior designers in chennai
best interior designers in chennai

afibiz said...

This is such a great post, and was thinking much the same myself. Another great update.
interior decorators in chennai
Modular kitchen in chennai

afiaa said...

Nice tutorial. Thanks for sharing the valuable information. it’s really helpful. Who want to learn this blog most helpful. Keep sharing on updated tutorials…
Best Interior Designers
home interiors in chennai
Commercial interior designers in chennai

afibiz said...

This is most informative and also this post most user friendly and super navigation to all posts... Thank you so much for giving this information to me.. 
Office interior designers in chennai
living room interior designers in chennai
False ceiling interiors designers in chennai

Magnaa Interiors said...

Great post with very useful information to all thanks for sharing with all of us
Office furniture manufacturer in chennai
office interior designerss

afiaa said...

Really great post, Thank you for sharing This knowledge.Excellently written article, if only all bloggers offered the same level of content as you, the internet would be a much better place. Please keep it up!
interior designers in chennai