|
Re: Getting Dynamic Productivity in a Static Language
|
Posted: Mar 30, 2009 9:03 AM
|
|
> All you say is correct. However, I see the > advantage of static typing in other situations. > Suppose for instance you have a list of objects, > where the objects are of different types and can > be lists themselves (typical case a hyerarchical > data structure, say coming from a XML file). > A typical problem is to flatten such a nested list. > This is a solution in Python <=2.5: > > def flatten(x): > res = [] > for el in x: > if hasattr(el, '__iter__'): > res.extend(flatten(el)) > else: > res.append(el) > return res > > print(flatten([1, 2.0, ["abc", [3, ""]]])) > > How would you solve a problem like this in Scala? > The idiomatic way would be to use a recursive pattern match like this:
scala> val michele = List(1, "hi", List(1, 2, 3), new java.util.Date, List("fee", "fie", "foe", List('f', 'u', 'm')), 99, "Luftballons") michele: List[Any] = List(1, hi, List(1, 2, 3), Mon Mar 30 23:42:37 MYT 2009, List(fee, fie, foe, List(f, u, m)), 99, Luftballons)
scala> def flatten(list: List[Any]): List[Any] = | list match { | case (x: List[Any]) :: xs => flatten(x) ::: flatten(xs) | case x :: xs => x :: flatten(xs) | case Nil => Nil | } warning: there were unchecked warnings; re-run with -unchecked for details flatten: (List[Any])List[Any]
scala> flatten(michele) res0: List[Any] = List(1, hi, 1, 2, 3, Mon Mar 30 23:42:37 MYT 2009, fee, fie, foe, f, u, m, 99, Luftballons)
It may look a bit obscure if you aren't familiar with Scala, so I'll walk you through the method:
def flatten(list: List[Any]): List[Any] =
This is the method signature basically. def means method declaration as in Python. flatten is the name of the method, as in Python. In parens is the argument, which I called list , and in Scala you have to give its type, so I put List[Any] . The type goes after the variable name, separated by a colon. Then because this is a recursive method you're required to specify a result type, so that's the second List[Any] . That's the result type of the method. Then there's an equals sign, which starts the body of the function. The rest is the body of the function. Since it is one expression, I don't need curly braces for the body.
list match {
This means do a pattern match on the incoming list. It is like a switch statement on steroids. There's three cases it will look at, and the first one to match will win. The pattern is between case and the => (the "rocket"). That's the thing that will be matched against. The expression to the right of the rocket symbol is the result value if that case matches. So here's the first one:
case (x: List[Any]) :: xs => flatten(x) ::: flatten(xs)
The pattern here is (x: List[Any]) :: xs . This matches any list whose first element is also a list. When this matches, the first element (the nested list) is assigned to the variable x , and the remainder of the list is assigned to the variable name xs . Then the result is the right hand side of the rocket: flatten(x) ::: flatten(xs) . This means call flatten recursively, passing in the first element (the nested list), then concatenate that result with the result of calling flatten on the rest of the list. (The ::: operator means list concatenation.) Here's the next case:
case x :: xs => x :: flatten(xs)
This one just matches any list that has at least one element. If this case matches, the first element will be assigned to the variable x and the rest of the list will be assigned to xs . Now one thing we know about x here is that it isn't a list, because if it were a list, the previous case would have matched. So the result, the expression to the right of the rocket, in this case is the element x prepended to the result of calling flatten on the rest of the list. (The :: operator prepends an element to the beginning of a list.) Here's the last case:
case Nil => Nil
This one matches the empty list. In this case, the result is just the empty list. This is the one that finishes the recursion. As the unrolling recursion starts popping frames, the result list gets built from back to front.
|
|