Updating Functions

In computer science often updates to bindings / environments are described by updating substitution functions at specific points. This blog post shows a way to express such updates in Scala.

Yesterday dinesh asked in #scala on IRC whether Scala supported updateable functions

(11:46:16) dinesh_: well for example, if you have f(x) = x, and then apply the function update f[5 := 10]
(11:46:50) dinesh_: then f[5 := 10](x) = x, except f[5 := 10](5) = 10

In the following discussion assume f to be defined as

def f(x: Int) = x

The obvious built in way to express the function update in Scala would be to use PartialFunction.orElse. One would like to write

{ case 5 => 10 } orElse f

Unfortunately the type inferencer will not derive the function argument type in the partial function literal and PartialFunction.orElse requires its argument to be a PartialFunction, not a "normal" Function1. So you had to write instead

({ case 5 => 10 }: PartialFunction[Int,Int]) orElse ({ case x => f(x) }: PartialFunction[Int,Int])

which is not that elegant.

Implicits and the pimp-my-library pattern comes to the rescue. Define

object FunctionUpdate {
  implicit def function2RichFunction[A,B](f: Function1[A,B]) = new RichFunction(f)
  class RichFunction[A, B](f: Function1[A,B]) {
    def updated(pf: PartialFunction[A, B]): Function1[A, B] =
      pf orElse { case x => f(x) }
  }
}

And now you can write

import FunctionUpdate.function2RichFunction

def f(x: Int) = x
assert(f(1) == 1)
assert(f(5) == 5)

val g = f _ updated { case 5 => 10 }
assert(g(1) == 1)
assert(g(5) == 10)

If you have many updates to a function the above implementation will suffer from the linear search implied by chaining partial functions. You will have to find a more sophisticated way of representing the updated functions such that you could optimize implementation when the chain of updates becomes larger. While this is certainly possible I have no use case for such code and leave that topic to the interested reader :) .

The above code is also available on bitbucket.

_____
tags: Programming Languages|  Scala