Fun with function composition in Scala

This is my first post with content, and is what motivated me to start this blog — a simple little code bite that I thought might be useful for others. And, since it is about composing functions, it helped  me come up with the name Bcomposes.

So, the goal of this post is to show how a list of functions can be composed to create a single function, in the context of mapping a set of values using those functions. It’s a cute example that shows off some of the goodness that comes with functional programming in Scala. And, while this isn’t a tutorial, it might still be useful for people who are just getting into functional programming.

We’ll start with the list of numbers 1 to 5 and some simple functions — one for adding 1, another for squaring, and third for adding 100.

scala> val foo = 1 to 5 toList
foo: List[Int] = List(1, 2, 3, 4, 5)

scala> val add1 = (x: Int) => x + 1
add1: (Int) => Int = <function1>

scala> val add100 = (x: Int) => x + 100
add100: (Int) => Int = <function1>

scala> val sq = (x: Int) => x * x
sq: (Int) => Int = <function1>

We can then apply any of these functions to each element in the list foo by using the map function.

scala> foo map add1
res0: List[Int] = List(2, 3, 4, 5, 6)

scala> foo map add100
res1: List[Int] = List(101, 102, 103, 104, 105)

scala> foo map sq
res2: List[Int] = List(1, 4, 9, 16, 25)

We can save the results of mapping all the values through add1, and then map the resulting list through sq.

scala> val bar = foo map add1
bar: List[Int] = List(2, 3, 4, 5, 6)

scala> bar map sq
res3: List[Int] = List(4, 9, 16, 25, 36)

Or, if we don’t care about the intermediate result, we can just keep on mapping, through both functions.

scala> foo map add1 map sq
res4: List[Int] = List(4, 9, 16, 25, 36)

What we just did, above, was sq(add1(x)) for every x in the list foo. We could have instead composed the two functions, since sq(add1(x)) = sqοadd1(x). Here’s what it looks like in Scala:

scala> val sqComposeAdd1 = sq compose add1
sqComposeAdd1: (Int) => Int = <function1>

scala> foo map sqComposeAdd1
res5: List[Int] = List(4, 9, 16, 25, 36)

Of course, we can do this with more than two functions.

scala> foo map add1 map sq map add100
res6: List[Int] = List(104, 109, 116, 125, 136)

scala> foo map (add100 compose sq compose add1)
res7: List[Int] = List(104, 109, 116, 125, 136)

And so on. Now, imagine that you want the user of a program you’ve written to be able to select the functions they want to apply to a list of items, perhaps from a set of predefined functions you’ve provided plus perhaps ones they are themselves defining. So, here’s the really useful part: we can compose that arbitrary bunch of functions on the fly to turn them into a single function, without having to write out “compose … compose … compose…” or “map … map … map …” We do this by building up a list of the functions (in the order we want to apply them to the values) and then reducing them using the compose function. Equivalent to what we had above:

scala> val fncs = List(add1, sq, add100)
fncs: List[(Int) => Int] = List(<function1>, <function1>, <function1>)

scala> foo map ( fncs.reverse reduce (_ compose _) )
res8: List[Int] = List(104, 109, 116, 125, 136)

Notice the that it was necessary to reverse the list in order for the composition to be ordered correctly. If you don’t feel like doing that, you can use andThen in Scala.

scala> foo map (add1 andThen sq andThen add100)
res9: List[Int] = List(104, 109, 116, 125, 136)

Which we can of course use with reduce as well.

scala> foo map ( fncs reduce (_ andThen _) )
res10: List[Int] = List(104, 109, 116, 125, 136)

Since functions are first class citizens (something we used several times above), we can assign the composed or andThened result to a val and use it directly.

scala> val superFunction = fncs reduce (_ andThen _)
superFunction: (Int) => Int = <function1>

scala> foo map superFunction
res11: List[Int] = List(104, 109, 116, 125, 136)

This example is of course artificial, but the general pattern works nicely with much more complex/interesting functions and can provide a nice way of configuring a bunch of alternative functions for different use cases.

About these ads
12 comments
  1. Excellent article, i’m just starting in scala, and found this new concept (for me) very useful.

  2. Nice, really good for those who are learning functional programming. Thanks.

  3. Chris said:

    I am also starting my journey into Scala and found this article very interesting and helpful

  4. Nice article. Scala standard library provides you a convenience function “Function.chain” that reduces a sequence of A => A under andThen combinator.

    scala> val square = (x: Int) => x * x
    square: (Int) => Int =

    scala> val double = (x: Int) => 2 * x
    double: (Int) => Int =

    scala> val add1 = (x: Int) => x + 1
    add1: (Int) => Int =

    scala> val fs = List(square, double, add1)
    fs: List[(Int) => Int] = List(, , )

    scala> val f = Function.chain(fs)
    f: (Int) => Int =

    scala> f(2)
    res44: Int = 9

    • Function.chain is rather more convenient — thanks for pointing it out! Hopefully, this post will help folks understand what it is doing.

  5. Also, A => A type functions are endofunctors, and endofunctors are monoids under composition. So this works too:

    scala> val g = fs.map(_.endo).reverse.asMA.sum
    g: scalaz.Endo[Int] =

    scala> g(2)
    res45: Int = 9

  6. kuchumovn said:

    Good

  7. 小明 said:

    Very nice article!

  8. Paul said:

    Thanks – this was crystal clear for me. Really helped my understanding!

  9. Sven H said:

    I have to learn scala, for it is java based, and that is kinda hip for some use-cases. But the Scala syntax makes me cry, because I do not come from Java, I also know a little haskell in which you example looks like this:
    (“Prelude> ” is the prompt of the interactive haskell interpreter)

    Prelude> let foo = [1..5]
    Prelude> let add1 = (1+)
    Prelude> let add100 = (100+)
    Prelude> let sq x = x * x

    Okay to play around with this:

    Prelude> add1 `map` foo
    [2,3,4,5,6]

    which is the infix variant of:

    Prelude> map add1 foo
    [2,3,4,5,6]

    (Wich I prefer)

    (in haskell the function comes always first, and putting a binary function into back ticks (`f`) makes it possible to use the function in infix position)

    To combine add100 and sq:

    Prelude> map sq (map add100 foo)
    [10201,10404,10609,10816,11025]

    OR:

    Prelude> map (sq . add100) foo
    [10201,10404,10609,10816,11025]

    OKay now lets put all the functions into a list:

    Prelude> let fncs = [add1, add100, sq]

    Then lets hammer that list of functions onto foo, to get
    a list of results from each function application:

    Prelude> map (sequence fncs) foo
    [[2,101,1],[3,102,4],[4,103,9],[5,104,16],[6,105,25]]

    Oh well this is nice, but not what the blog author intended, I shall keep to the script;

    In haskell there there are the classic fold-style functions (foldr, foldl, …)
    because they are somewhat un-intuive to many let me define a ‘reduce’ functions that looks more familiar:

    let reduce = foldl1

    now a combine function, that reduces a list via functions composition (operator “.”):

    let combine = reduce (.)

    Prelude> map (combine fncs) foo
    [102,105,110,117,126]

    we can do without the combine and the foo
    Prelude> let map_fncs = map (reduce (.) fncs)

    and then lets define some other lists:

    Prelude> let bar = [0..9]

    And we can do:

    Prelude> map_fncs foo
    [102,105,110,117,126]

    and:

    Prelude> map_fncs bar
    [101,102,105,110,117,126,137,150,165,182]

    BTW a stable, recursive quicksort might look like this:

    quicksort (pivot:xs) = quicksort smaller ++ [pivot] ++ quicksort bigger
    where smaller = filter ( pivot) xs
    quicksort [] = []

    as one-liner:
    Prelude> let quicksort xs = case xs of x:xs -> quicksort (filter ( x) xs); [] -> []

    lets test:

    Prelude> quicksort (reverse bar)
    [0,1,2,3,4,5,6,7,8,9]

    Anyway… Scala also has some *cough* *cough* nice syntax, and “I gotta do what I gotta do” and learn it anyway…

    Thanks for your great post, helps me as absolute scala beginner alot

    • Sven H said:

      Hmm text input somehow failed to keep the quicksort intact

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,661 other followers

%d bloggers like this: