The Artima Developer Community
Sponsored Link

Weblogs Forum
Percolating Nones in Scala

4 replies on 1 page. Most recent reply: Sep 19, 2009 1:13 AM by Bill Venners

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 4 replies on 1 page
Bill Venners

Posts: 2249
Nickname: bv
Registered: Jan, 2002

Percolating Nones in Scala (View in Weblogs)
Posted: Sep 12, 2009 2:06 AM
Reply to this message Reply
Summary
Scala has an Option type that provides a type-safe alternative to using null to represent optional values. In this blog post, I show how to replace nested conditionals involving Option with a for-expression.
Advertisement

Scala's Option type has only two possible subtypes, Some[T] and None. If an Option is a Some, the optional value does indeed exist. If it is a None, however, the value does not exist. In other words, None indicates in Scala what null often indicates in Java.

Idiomatic Scala APIs use Option to represent optional values. For example, here's a find method that looks for a specified character, c, in a specified string, s:

def find(c: Char, s: String): Option[Int] =
    s.indexOf(c) match {
        case -1 => None
        case c => Some(c)
    }

If the string contains the character, find returns the index of the first occurence of the character wrapped in a Some. Otherwise, it returns None to indicate the character does not exist in the string.

Here's another example. The superChar method returns the character at the specified index, i, of the string, "supercalifragilisticexpialidotious", wrapped in a Some, or None if i is greater than or equal to the length of "supercalifragilisticexpialidotious":

def superChar(i: Int): Option[Char] = {
    val song = "supercalifragilisticexpialidotious"
    if (i < song.length) Some(song(i)) else None
}

In the unlikely event that you want to determine the character in supercalifragilisticexpialidotious at the same index as the first occurrence of a particular character in a particular string, you could first call find. If it's result is a Some, you have the index of that character in the string. You can then pass that index to superChar. If it returns a Some, then you have the character in supercalifragilisticexpialidotious that sits at the same index as your chosen character in your chosen string. Now imagine further you want to find the index of the first occurrence of this result character in your original string. You could invoke find again, this time passing in the result character and the original string.

Now three things could go wrong here:

  1. Character c might not be in string s.
  2. Character c is in string s, but at an index greater than or equal to the number of characters in supercalifragilisticexpialidotious.
  3. If the previous two problems didn't materialize, the result character still might not be in string s.

The traditional Java-style approach to deal with this situation with a nested if-else construct, as is done in the following percolate1 method. If all goes well, it returns the desired index, wrapped in a Some. But if any of the three potential problems happen, it returns a None:

def percolate1(c: Char, s: String) = { // (Not idiomatic Scala)
    val index = find(c, s)
    if (index.isDefined) { // isDefined is true for Some, false for None
        val resultChar = superChar(index.get) // get grabs the value out of the Some
        if (resultChar.isDefined) {
            find(resultChar.get, s)
        }
        else {
            None
        }
    }
    else {
        None
    }
}

A more idiomatic way to accomplish this in Scala is with a nested pattern match. That would look like this:

def percolate2(c: Char, s: String) = {
    find(c, s) match {
        case Some(index) =>
            superChar(index) match {
                case Some(resultChar) => find(resultChar, s)
                case None => None
            }
        case None => None
    }
}

While this is a bit more concise and leaves less room for error than the nested if-else construct, Scala has an even better way to accomplish this. You can use a for-expression, like this:

def percolate3(c: Char, s: String) =
    for {
        index <- find(c, s)
        resultChar <- superChar(index)
        result <- find(resultChar, s)
    } yield result

Using any of these approaches, a None will percolate out no matter where the failure occurs.

Here are some examples in the Scala interpreter. Given c and "cats", percolate3 will return Some(3) because c is at index 0 in cats, index 0 in supercalifragilisticexpialidotious contains s, and s in "cats" appears at index 3:

scala> percolate3('c', "cats")
res0: Option[Int] = Some(3)

The previous example made it all the way through. If any of the three potential problems occurs, a None will occur at that step and percolate out all the way to the result. Here the first call to find results in None, so None percolates out as the result of percolate3:

scala> percolate3('d', "cats")
res1: Option[Int] = None

Here the initial call to find returns Some(68), but because 68 is greater than the length of supercalifragilisticexpialidotious, the subsequent call to superChar results in a None, which percolates out:

scala> percolate3('c', "--------------------------------------------------------------------cats") 
res2: Option[Int] = None

And here the first call to find results in Some(2), and superChar results in Some(u), but because "cats" doesn't contain a u, the second call to find results in a None, which is returned:

scala> percolate3('a', "cats")
res2: Option[Int] = None

Using a for expression for this can seem non-intuitive because we're used to doing this kind of thing to iterate over collections. One way to think of an Option is as a collection that can contain either zero or one value--like a special kind of List that can either be an empty List or a List with only one value in it. The nice thing is you can compose up to as many operations like this as you need and be confident Nones that happen at any step along the way will simply percolate through to the end.


Kevin Wright

Posts: 38
Nickname: kevwright
Registered: Jul, 2009

Re: Percolating Nones in Scala Posted: Sep 13, 2009 4:02 AM
Reply to this message Reply
I love this approach, but for the example given I think it's cleaner still to use .map directly instead of the for comprehension

Kevin Wright

Posts: 38
Nickname: kevwright
Registered: Jul, 2009

Re: Percolating Nones in Scala Posted: Sep 14, 2009 2:03 PM
Reply to this message Reply

def percolate4(c: Char, s: String) =
find(c,s).flatMap(superChar(_)).flatMap(find(_, s))

Daniel Jimenez

Posts: 40
Nickname: djimenez
Registered: Dec, 2004

Re: Percolating Nones in Scala Posted: Sep 17, 2009 12:11 PM
Reply to this message Reply
>
> def percolate4(c: Char, s: String) =
> find(c,s).flatMap(superChar(_)).flatMap(find(_, s))
>


I believe this is the same as the for-comprehension. Isn't flatMap the bind method in Scala?

At least that's what I thought I understood from http://james-iry.blogspot.com/2007/09/monads-are-elephants-part-1.html - see the last paragraph of "Monads are Combinable"

Bill Venners

Posts: 2249
Nickname: bv
Registered: Jan, 2002

Re: Percolating Nones in Scala Posted: Sep 19, 2009 1:13 AM
Reply to this message Reply
> >
> > def percolate4(c: Char, s: String) =
> > find(c,s).flatMap(superChar(_)).flatMap(find(_, s))
> >

>
> I believe this is the same as the for-comprehension. Isn't
> flatMap the bind method in Scala?
>
> At least that's what I thought I understood from
> http://james-iry.blogspot.com/2007/09/monads-are-elephants-
> part-1.html - see the last paragraph of "Monads are
> Combinable"
>
I had the phrase "Option's monadic nature" in an early draft but dropped it. I think a lot of people are not very certain what monads are, and I didn't want to get into explaining it. In part, because I'm sure I don't fully grok the monad concept yet myself, though I have had a few glimpses of insight here and there. Scala's Option is a monad, just like "Maybe" in Haskell.

You're right that the for expression (or for comprehension) in Scala gets transformed into calls to map, flatMap, filter, and foreach. But I think what Kevin is really saying is he prefers the straightfoward method call style over the more "sugared" for expression style. I've heard some people say that as they got more comfortable with the functional aspects of Scala, they started using for expressions less and instead just making direct calls with map, flatMap, filter, etc. I myself use map, filter, and foreach occasionally, but I often use for expressions simply because I find the resulting code a bit easier to read.

Flat View: This topic has 4 replies on 1 page
Topic: Converting .jpeg images in .cbz format Previous Topic   Next Topic Topic: Google Chrome Changes the Game


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us