Idea Transcript
More Next Blog»
Create Blog Sign In
Ruminations of a Programmer A programmer's blog - will deal with everything that relates to a programmer. Occasionally, it will contain some humour, some politics and some sport news.
SUNDAY, JANUARY 04, 2009
ABOUT ME
Higher Order abstractions in Scala with Type Constructor Polymorphism Abstractions at a higher level through type constructor polymorphism. Good type systems are expressive enough to conceal the implementation complexity, and expose *only* what it matters to the developer. People often cringe about the complexity of Scala's type system and how it serves as a barrier to the entry point in mainstream programming. As Michael Feathers recently noted on Tweeter, the unfortunate fact is that people often jump at the esoteric parts of a language before looking at the simpler subset, which he will be using 90% of the time. And, I think Scala has that sweet spot, where you need not mess around too much with variances, implicits and existentials and yet come up with a nice, concise and functional codebase. In this post, I discuss the already introduced intimidating phrase "Type Constructor Polymorphism" through a series of code snippets ranging from toys to some real-world stuff. The idea is, once again, not to evangelize type theory intricacies, but share some of the experiences of how this feature in Scala's type system can help write idiomatic code, while staying away from the complexities of its underlying implementation.
Debasish Ghosh Follow
1.7k
Programming nerd with interest in functional programming, domain-specific languages, and NoSQL databases. Debasish is a senior member of ACM and has authored DSLs In Action, published by Manning in December 2010. Debasish is also authoring another book Functional and Reactive Domain Modeling also to be published by Manning. View my complete profile
Jump on .. We have a list of Option[String] that we need to abstract over and compute some value. Say, for the sake of keeping the example simple, we will calculate the sum of lengths of all the strings present ..
POPULAR POSTS
Does category theory make you a better programmer ? How much of category theory knowledge should a working programmer have ? I guess this depends on what kind of language the programmer uses i...
val employees: List[Option[String]] = List(Some("dave"), None, Some("john"), Some("sam")) val n: List[Int] = employees.map { x => x match { case Some(name) => name.length case None => 0 } }.elements.reduceLeft[Int](_ + _) println(n)
Let us take another problem that needs to abstract over a different List structure, a List of List of Strings, and compute the same result as before, i.e. the sum of lengths of all the strings encountered in the collection .. val brs: List[List[String]] = List(List("dave", "john", "sam"), List("peter", "robin", "david"), List("pr as", "srim")) val m: List[Int] = brs.flatMap {x => x.map {_.length}} .elements.reduceLeft[Int](_ + _) println(m)
Do you see any commonality in the solution structure in the above snippets ? After all, the problem space has a common generic structure ..
Scala Implicits : Type Classes Here I Come I was having some discussion on type classes in Scala with Daniel on Twitter the other day when I suddenly discovered one of my unfinished ... Monads - Another way to abstract computations in Scala You can view monads as containers or as computations . Isn't this confusing enough ? To a programmer, the biggest scare with the name ... CQRS with Akka actors and functional domain models Fighting with impedance mismatch has been quite a losing battle so far in the development of software systems. We fight mismatch to handle s... External DSLs made easy with Scala Parser Combinators External DSLs are hard since implementing them involves reinventing most of the mechanisms found in a general purpose language. Designing in...
1. we have a List with some String values abstracted in different forms 2. need to iterate over the list 3. do some stuff with elements in the list and compute an Int value
Unfortunately the actual solution structures look quite different and have to deal a lot digging into the abstractions of the underlying representations within the collection itself. And this is because, we cannot abstract over the type constructor (the List in this case) that takes another type constructor as an argument (Option[String] in the first case and List[String] in the second case). Enter type constructor polymorphism. Sounds intimidating ? Maybe, but ask the Haskellers .. they have been using typeclasses ever since so successfully in comprehensions, parser combinators and embedded DSLs and programming at a different level of abstraction. Scala supports type constructor polymorphism since 2.5, and the details have been discussed in a recent paper by Adriaan Moors et al in OOPSLA 2008. Here is a snippet of the Scala code that works seamlessly for both of the above cases .. val l: List[Int] = employees.flatMapTo[Int, List]{_.map{_.length}} val sum: Int = l.elements.reduceLeft[Int](_ + _) println(sum)
The above code abstracts over List through higher order parametric polymorphism, i.e. independent of whether the List parameter is an Option[] or another List[]. Incidentally both of them (List and Option) are monads and flatMapTo abstracts a monadic computation, hiding all details of type constructor polymorphism from the developer. Now here is some real life example (elided for simplicity) .. Here are the simple domain models for Customer, Instrument and Trade, used for modeling a use case where a Customer can order for the Trade of an Instrument in an exchange. case class Customer(id: Int, name: String) case object nomura extends Customer(1, "NOMURA") case object meryll extends Customer(2, "MERYLL") case object lehman extends Customer(3, "LEHMAN")
Functional Patterns in Domain Modeling - Anemic Models and Compositional Domain Behaviors I was looking at the presentation that Dean Wampler made recently regarding domain driven design, anemic domain models and how using functi... Count-Min Sketch - A Data Structure for Stream Mining Applications In today's age of Big Data, streaming is one of the techniques for low latency computing. Besides the batch processing infrastructure of... Functional Patterns in Domain Modeling - The Specification Pattern When you model a domain, you model its entities and behaviors. As Eric Evans mentions in his book Domain Driven Design , the focus is on the... Domain Driven Design - Inject Repositories, not DAOs in Domain Entities There are some discussions in Spring forum , of late, regarding injection of repositories in the domain objects. And in the context of the d... Domain Models - Thinking differently in Scala & Clojure A language that doesn't affect the way you think about programming, is not worth knowing. - Alan J Perlis When you model a domain you...
Subscribe in a reader
case class Instrument(id: Int) case object ibm extends Instrument(1) case object sun extends Instrument(2) case object google extends Instrument(3)
Buy your copy of DSLs in Action here
case class Trade(ref: Int, ins: Instrument, qty: Int, price: Int)
NOW AVAILABLE IN PRINT
And we fetch the following list through a query from the database. It is a List of tuples where each tuple consists of a Customer and a trade that has been executed based on the Order he placed at the exchange. And here is the snippet of the code that computes the sum total of the values of all trades executed in the day for all customers. val trades: List[(Customer, Option[Trade])] = List((nomura, Some(Trade(100, ibm, 20, 12))), (meryll, None), (lehman, Some(Trade(200, google, 10, 10))))
val ts: List[Option[Trade]] = trades.map(_._2) val t: List[Int] = ts.flatMapTo[Int, List]{_.map{x => x.qty * x.price}} val value = t.elements.reduceLeft[Int](_ + _) println(value)
RUMINATIONS SOUL SEARCH
Search
Really not much different from the above simple cases where we were dealing with toy examples - isn't it ? The structure of the solution is the same irrespective of the complexity of data being stored within the collections. The iteration is being done at a much higher level of abstraction, independent of the types stored within the container. And as I mentioned above, flatMapTo is the secret sauce in the above solution structure that abstracts the building of the new container hiding the inner details. To get more into the innards of flatMapTo and similar higher order abstractions, including the new form of Iterable[+T], have a look at the OOPSLA paper referenced above. Postscript: In all the snippets above, I have been explicit about all type signatures, just for the sake of easier understanding of my passionate reader. In reality, almost all of these will be inferred by Scala.
Posted by Debasish Ghosh at 1/04/2009 09:10:00 PM
FOLLOWERS
Labels: functional, haskell, scala, type
12 comments: Fanf said... I believe I never let a comment here before, so this is a global "thank you" for all your posts, they are always really pleasant to read. Monday, January 5, 2009 at 8:48:00 PM GMT+5:30
BLOG ARCHIVE
2017 (3) 2015 (4) 2014 (6)
Arrgh said...
2013 (8)
Note that the map/match in the first example could be done more concisely like this:
2012 (11) 2011 (11)
val lengths = for (Some(name) x match { case Some(name) => name.length case None => 0 } }.iterator val n: Int = a.reduceLeft[Int](_ + _) ///(a:Int,b:Int) => a + b println(n) val brs: List[List[String]] = List(List("dave", "john", "sam"), List("peter", "robin", "david"), List("pras", "srim")) val m: Int = brs.flatMap { x => x.map { _.length } } .iterator.reduceLeft[Int](_ + _) println(m) The reduceLeft's don't return List[Int], they return Int. Perhaps I'm missing something. Tuesday, July 17, 2012 at 2:02:00 AM GMT+5:30 Post a Comment Newer Post
Home
Older Post
Subscribe to: Post Comments (Atom)
Powered by Blogger.