I was going through Chapter 14 of the Real World Haskell book, that discusses and explains monads. Here is an example straight from the book itself ..
import qualified Data.Map as M
type PersonName = String
type PhoneNumber = String
type BillingAddress = String
data MobileCarrier = Honest_Bobs_Phone_Network
| Morrisas_Marvelous_Mobiles
| Petes_Plutocratic_Phones
deriving (Eq, Ord)
findCarrierBillingAddress :: PersonName
-> M.Map PersonName PhoneNumber
-> M.Map PhoneNumber MobileCarrier
-> M.Map MobileCarrier BillingAddress
-> Maybe BillingAddress
and one of it's implementations, the most concise one (name changed) ..
findCarrierBillingAddress person phoneMap carrierMap addressMap =
lookup phoneMap person >>= lookup carrierMap >>= lookup addressMap
where lookup = flip M.lookup
The problem is to find the address of mobile carriers used by a person, hopping through a few cascaded lookups in mapped information.
The method uses the chaining function (
>>=) of monads, "bind", in Haskell, that binds the result of the computation on the left to the parameter of the one on the right. More specifically, the result of the computation on the left gets applied as a parameter to the already partially applied function on the right. Cool stuff .. bread and butter to an experienced Haskeller. But I do not fall into that category, and succumbed immediately to the urge of comparing it with how it will be implemented in Scala ..
Here is the meat of the monadic code in Scala ..
def find_carrier_billing_address(name: String,
phone_map: Map[String, String],
carrier_map: Map[String, MobileCarrier],
address_map: Map[MobileCarrier, String]) = {
phone_map.get(name).flatMap(carrier_map.get(_)).flatMap(address_map.get(_))
}
Pretty much similar in conciseness ..
flatMap is Scala's bind and we have the same chaining effect through partial application. In both of the above applications, we use the MayBe monad (Option[T] in Scala).However, there are a few subtle points to be noted in the Haskell and Scala variants that bring out some of the differences in the language implementations. And which became much clearer to me once I implemented the above Haskell example in Scala.
Partial Application in Haskell
Haskell is a purely functional language, where partially applied functions are the normal idioms in programming. Have a look at the type signature of
map in Haskell ..ghci> :type map
map :: (a -> b) -> [a] -> [b]
The above definition is, by definition curried. For a more common view of the type for
map, as in other not-so-pure languages, we need to do an explicit uncurry in Haskell ..ghci> :type uncurry map
uncurry map :: (a -> b, [a]) -> [b]
map is a function that takes as arguments a function and a collection and generates another collection by applying the function on every element of the input collection. Now, in Haskell, the function type operator (->) is right associative - hence the above signature looks like (a -> b) -> ([a] -> [b]). We can invoke map with only one argument, the mapping function, and the result will be another function that takes as input a list and returns another list.ghci> :type map (+2)
map (+2) :: (Num a) => [a] -> [a]
In the above snippet,
map (+2) is a valid invocation of the map function, that generates another function, that takes a list of integers and generates another list whose every element will be incremented by 2.Note that every application of the function binds to the parameter list from the left - hence in Haskell, function application is left-associative. In the above example, we did a partial application to
map and the parameter we supplied (+2) binds to the leftmost argument of the type signature. Without resorting to the tricks of anonymous lambdas, normally idiomatic Haskell does not allow you to bind to middle parameters in a function application.In the function
findCarrierBillingAddress above, lookup carrierMap is a partial application to lookup, that produces another function, to which the result of the previous lookup in chain (phoneNumber) gets bound. And this continues for every element of the chain in bind.But notice the
where part, where we need to redefine lookup and flip the positions of arguments for Data.Map.lookup. This needs to be done since partial application in Haskell, by default (without resorting to some lambda tricks), associates to the left and all API designs that plan to be partial application friendly need to honor this constraint. The argument that flows from the previous element in the monadic bind can only associate to the rightmost parameters in the list. Hence the added verbosity in the implementation ..And now for Scala
Unlike Haskell, Scala forces that a method has to be applied to all its arguments. The arguments can be explicitly specified or they can be partially applied using the placeholder
_.scala> val l = List(1, 2, 3, 4)
l: List[Int] = List(1, 2, 3, 4)
scala> l map (_ + 2)
res7: List[Int] = List(3, 4, 5, 6)
Since Scala offers placeholder arguments that need to be supplied, it becomes easy to bind any parameter through partial application. Let us change the above program fragment, where instead of a map lookup, the final fetch of the address is done through a function that takes some additional parameters ..
def get_address(carrier: MobileCarrier,
out_of_state: Boolean, address_map: Map[MobileCarrier, String]) = {
if (out_of_state == true) address_map.get(carrier)
else None
}
Scala handles it nicely, since it can explicitly bind parameters through placeholders in partial application ..
def find_carrier_billing_address(name: String,
phone_map: Map[String, String],
carrier_map: Map[String, MobileCarrier],
address_map: Map[MobileCarrier, String]) = {
phone_map.get(name)
.flatMap(carrier_map.get(_))
.flatMap(get_address(_, true, address_map))
}
We get the same conciseness as the first implementation.
How do we implement the same in Haskell ? Here is the
getAddress function like the one in Scala ..getAddress :: MobileCarrier
-> Bool
-> M.Map MobileCarrier BillingAddress
-> Maybe BillingAddress
getAddress carrier outOfStation addressMap =
case outOfStation of
False -> Nothing
_ -> M.lookup carrier addressMap
We cannot have the same concise chaining as above, without changing the position of the parameters, since Haskell partial application is left-associative and the parameter
carrier that comes in from the previous element of the chain in the monadic bind needs to be applied to the leftmost position ..This creates problems when dealing with third party APIs when switching argument positions is not in your control. The alternative is to apply the ubiquitous indirection that uses anonymous lambdas ..
findCarrierBillingAddress person phoneMap carrierMap addressMap =
lookup phoneMap person >>= lookup carrierMap >>= \c -> getAddress c True addressMap
where lookup = flip M.lookup
Workable, but not as concise as the Scala one or the earlier Haskell variant. The Scala idiom of using placeholders for parameter binding is quite powerful as well as intuitive. Scala, being a hybrid OO-FP language has to take care of issues like subtyping (which Haskell does not have) - I guess it is for this reason Scala cannot support pure function currying as the default like Haskell. But the placeholders work out very well in offering the flexibility of partial application and any-position parameter binding.
9 comments:
def curriedFun(a: Int)(b: Int) = ...
val partial = curriedFun(3)
How 'bout that? :-)
FP/OO hybridization doesn't really have much to do with whether or not a language can support currying. The big reason that Scala defaults to the uncurried form is for reasons of interop with Java (and company). No Java method is curried, which means that Scala either has to transparently curry everything (inefficient and confusing) or support both forms on equal footing.
I may be mistaken, but I thought I read somewhere that implementing subtype polymorphism and function currying as a default together is difficult.
I did a quick google and found this comment from Martin Oderskey in a reddit thread ..
"I think the question to curry or not is deep in a language design. Scala chooses not to curry as a default. If it would curry by default it would be a very different language."
The problem is the use of the word "pure". The ML family of languages aren't pure functional languages but they curry by default as well.
A pure functional language is one that enforces a separation between between computation and side effects. The ML family is not pure. Haskell 98 is. GHC Haskell mostly is ( you have to ignore the unsafe* family). So currying has nothing to do with purity.
As Daniel says, an OO language could be fully curried with no problems. The rules for co-and-contra variance hold just fine whether you're overriding a tupled method (e.g. Java and Scala's default) or a curried method (e.g. the example that Daniel posted in Scala).
Is there any OO language that implements currying by default ?
In the post, by "pure" I meant to differentiate between *pure* functional and *hybrid* OO-functional. I was thinking that implementing currying as default may be a problem with object subtyping. The example that Daniel has posted implements currying on a plain function. Will this same semantics hold for member functions in a class hierarchy ? Somehow the *this* pointer handling looks a bit problematic in subtypes. Or they will be handled by the regular co- and contra variance rules ? Here we are dealing with a single rooted hierarchy, hence we need to manage currying of *this* argument in the normal flow to make the implementation seamless.
Do you all see any issues with that ?
I'm not aware of any, but that doesn't mean it hasn't been done.
To show that it's perfectly feasible here's a bit of curried Scala code with no _ place holders.
class Base {
def doSomething(x:Int)(y:Int) = x + y
}
class Sub extends Base {
override def doSomething(x:Int)(y:Int) = x - y
}
val it : Base = new Sub
val f : Int => Int = class Base {
def doSomething(x:Int)(y:Int) = x + y
}
class Sub extends Base {
override def doSomething(x:Int)(y:Int) = x - y
}
val it : Base = new Sub
val f : Int => Int = it doSomething 17
println(f(12))
Martin's point about full currying making a different language is quite true, but that's a language design esthetic and usability question rather than a fundamental problem.
Sorry, I screwed up the paste
class Base {
def doSomething(x:Int)(y:Int) = x + y
}
class Sub extends Base {
override def doSomething(x:Int)(y:Int) = x - y
}
val it : Base = new Sub
val f : Int => Int = it doSomething 17
println(f(12))
James -
Here is an interesting one ..
class Base {
def foo = 10
def foo(i: Int) = i + 19
}
class Sub extends Base {
override def foo = 20
}
val b = new Sub
b foo // will it be curried ?
Yup. There are two features of Scala that a fully curried language would have to either ditch or seriously rethink. One is ad-hoc overloading. The other is variadic arguments (aka var args). But neither one is necessary. Varargs, in particular, can be easily replaced with a lightweight syntax for creating lists or arrays.
Now I realize why Martin said that Scala would be a different language if we decided to implement curry-by-default. And possibly, Java compatibility has been one of the driving factors towards this decision.
Post a Comment