Partial Application of Type Constructor with Scala’s Type Lambdas

Type Lambda, a must-have when utilizing higher-kind types with Scala programming language, is the topic of this post. I want to outline my findings regarding it in the current post. Please note that most of the examples listed next are inspired from different blog posts and books that I have come across. I will try to reference them as much as I can.

Without further ado, let’s begin!

Background: Type Members

We know that Scala allows definition of type members in a trait or class. For instance,

trait HList{
  type Hd
  ....
}

We can define an abstract type member Hd and we can also give a concrete meaning to Hd depending on the contexts, as shown next.

class IntList extends HList {
  type Hd = Int
  ....
}

As noted in #1, the above definition of Hd can also be considered as an alias for type Int. Similarly, we can define a IntMap as follows.

type IntMap[V] = Map[Int, V]

Note that, in the above code, V can vary deepening on the application of IntMap.

Type Projection

We can access the type members of a class or trait with the # operator (similar to . operator in case of value members), e.g., IntList#Hd. For instance, the following line asserts that IntList#Hd is indeed an Int type.

implicitly[Int =:= IntList#Hd]

Type members of a class or trait can be reused into different context and the relevant type checks are performed statically —

val x: IntList#Hd = 10

Design Principle

From design perspective, type members are particularly interesting when they are evolved along with their enclosing type to match the behavior accordingly. As noted in #2, it is regarded as family polymorphism or covariant specialization.

Application of Type Lambda

Now, lets get back to the topic of type lambda.

What is Type Lambda?

It is often regarded as Type-Level Lambda. As its name suggests, it is similar to anonymous functions, but for types. In fact, type lambdas are used to define an anonymous/inner types for given contexts. It is particularly useful when a type constructor has fewer type parameters compared to the parameterized type that we want to apply in that context. Next, we explain the concept of type lambda with an example.

Problem Description

Consider the following excellent example of a Functor from #2:

trait Functor[A, +M[_]]{
  def map[B] (f: A => B): M[B]
}

Notice that M[_] type constructor only accepts one type parameter. So, it is quite straightforward, if we want extend the Functor it for a Seq types.

case class SeqFunctor[A](seq: Seq[A])
  extends Functor[A, Seq]{

  override def map[B](f: (A) => B): Seq[B] =
    seq.map(f)
  }
}

And we can use SeqFunctor as follows:

> val lst = List(1,2,3)
> ListFunctor(lst).map(_ * 10)
// prints List(10, 20, 30)

However, in case of Map[K, V], it would be tricky to extend, since Map[K,V] has two type parameters while M[_] type constructor only accepts one.

Solution

To solve this, we apply type lambda, which handles the additional type parameter as shown below.

case class MapFunctor[K,V](mapKV: Map[K,V])
  extends Functor[V, ({type L[a] = Map[K,a]})#L]{

  override def map[V2](f: V => V2): Map[K, V2] =
    mapKV map{
      case (k,v) => (k, f(v))
    }
}

> MapFunctor(Map(1->1, 2->2, 3->3)).map(_ * 10)
// Result: Map(1 -> 10, 2 -> 20, 3 -> 30)

Here, we simply apply f on the values of mapKV. Thus, type variable are indeedV and V2.

Informally, we extend Functor for Map with a type lambda as follows–

Functor[A, +M[_]] ==>
Functor[V,
  (
    {type L[a] = Map[K, a]} // structural type definition
  )
  #L // type projection
]

Here {type L[a] = Map[K, a]} denotes a structural type. It essentially specifies an inner/annonymous type alias L[a], which is then matched against the (outer) #L. Type parameter K is partially applied and has been resolved from the context in this case. By applying type projection, #L, we get the type member out of the structural type, and thus define an alias for Map[K,_] in effect.

As noted in #3, an empty block in the type position (as in M[_]) essentially creates an anonymous structural type and the type projection allows us to get the type member from it.

Additional Tricks

Type lambda seems a bit intimidating; and handling multiple of them leads to somewhat difficult-to-comprehend code. To avoid that, Dan Rosen proposed a trick.

To demonstrate that, lets consider the previous example. Revisiting the type lambda from MapFunctor, we note that the only varying type is V and V2. We can define a Functor for Map by avoiding type lambda and use type member Map[K] as shown below.

case class ReadableMapFunctor[K,V](mapKV: Map[K,V]){
  def mapFunctor[V2] = {
    type `Map[K]`[V2] = Map[K, V2]
    new Functor[V, `Map[K]`] {
      override def map[V2](f: (V) => V2): `Map[K]`[V2] = mapKV map{
        case (k,v) => (k, f(v))
      }
    }
  }
}

> ReadableMapFunctor(Map(1->1, 2->2, 3->3)).mapFunctor.map(_*10)
//Map(1 -> 10, 2 -> 20, 3 -> 30)

This trick handles the extra type parameter of Map[K, V]. Also note the backticks; they permit the use of [] in the name of an identifier #4.

Following 5 outlines code examples used in this post.

Outlook

Overall, it seems to be an excellent feature with specific use-case, yet quite verbose. Sometimes, it is quite difficult to head around it. But surely, it has its applications and is a nice-to-have tool for Scala developers.

Let me know if you have any question. Thanks for visiting this post and going through this rambling.

References

  1. Programming in Scala by Odersky et al.
  2. Programming Scala by Dean Wampler and Alex Payne.
  3. Stackoverflow answer by Kris Nuttycombe regaring the benefits of Type Lambda in Scala.
  4. A More Readable Type Lambda Trick by Dan Rosen

Building ODataURI Parser with Scala Parser Combinators

Objective

Open Data Protocol (ODATA) facilitates end-users to access the data-model via REST-based data services by utilizing Uniform Resource Identifiers (URIs). In this post, we present the result of our recent experiment to build an abstraction on ODATA URIs to generate AST (Abstract Syntax Tree).

Note that this experiment is in its initial stage; hence, the implementation does not support complete feature-set of ODATA URI specification outlined at odata.org. It states a set of recommendations to construct these URIs to effectively identify data and metadata exposed by ODATA services.

To give an example of ODATA URI, consider following URI:

http://odata.org/service.svc/Products?$filter=Price ge 10

It in essence refers to a service request to return all the Product entities that satisfies the following predicate: Price greater than or equal to 10.

Motivation

Primary motivation of building such abstraction is to promote separation-of-concern and consequently, to allow the underlying layers of ODATA service implementation to process query expression tree and yield the result-set in a more efficient manner.

Approach

To implement this parser, we use Parser Combinators, which is in essence a higher-order function that accepts a set of parsers as input and composes them, applies transformations and generates more complex parser. By employing theoretical foundations of function composition, it allows constructing complex parser in an incremental manner.

Scala facilitates such libraries in its standard distribution (see scala.util.parsing). In this implementation, we in particular, use JavaTokenParsers along with PackratParser.

class ODataUriParser extends JavaTokenParsers with PackratParsers {
//...
}

Implementation

ODATA URI contains three fundamental parts, namely Service Root URI, Resource Path and Query Options as below and as per the documentations at [1].

If we consider the ODATA URI mentioned previously, following illustrates the stated three parts of ODATA request:

odata-uri-parts

Hence, we can construct this parser by building combinators for the three sub-parts in a bottom-up manner and then compose them to construct the complete parser as listed below.

To gets started with an example, lets consider following URI:

http://odata.io/odata.svc/Schema(231)/Customer?$top=2&$filter=concat(City, Country) eq 'Berlin, Germany'

and we are expecting an expression tree based on a pre-defined model as follows:

Building a parser combinator for Service Root and Resource Path are considerably simpler compared to that of Query Options (the third part). Let’s build them first.

We are using this convention (see ODATA specification) that a ODATA service root should always be ended by .svc. The following snippet can parse for instance http://odata.io/odata.svc to URL("http://odata.io/odata.svc").

Next we are defining a resource path which can parse for instance Schema(231) to ResourcePath("Schema",Number("231"),ResourcePath("Customer",EmptyExp(),EmptyExp())) expressions. A compound resource path can be augmented with multiple resources.

After that we have reached to the crux of the problem: to build a parser that can handle the query operators defined in the OData specification. To solve it, we apply bottom up approach in conjunction with top-down realization.

First we define a basic parser that can parse arithmetic expressions as follows.

Then we incrementally augment support for handling relational operators, and thus can handle logical and, or and similar operation.

The above two code listings form the basis to provide support for the query operations such as $filter and $select. See below.

Thus, it allows to parse the URI to expression tree as shown below.

Or, as follows:

Conclusion

The complete source of this project is available at github repository. Please feel free to browse and if there is any question, please post.

See More:

  1. OData URI Specification
  2. External DSLs made easy with Scala Parser Combinators
  3. DSLs in Action

Coalesce data functionally

In a recent project I had to coalesce quite significant amount of data in the following way. To simplify it for this post, consider that we have the following two lists.

val x = List(“a”, “b”, “c”, “a”)

val y = List(1, 2, 6, 9)

We are about to write a function which would return the following list as the result.

val result = List((a,10), (b,2), (c,6))

Basically it would coalesce value with the same category. See for instance “b” in the above example.

Language that came up with repl inherently provides very nice way to try out different expression and to get to the expected outcome. In this context, as we are using scala, we can use repl-driven development quite conveniently as illustrated below.

  • Define the Lists:
scala> val x = List("a", "b" , "c", "a")
x: List[String] = List(a, b, c, a)

scala> val y = List(1,2,6,9)
y: List[Int] = List(1, 2, 6, 9)
  • Zip them.
scala> val z = x zip y
z: List[(String, Int)] = List((a,1), (b,2), (c,6), (a,9))
scala>
  • Group them based on the values of x.
scala> val grps = z groupBy (_._1)
grps: scala.collection.immutable.Map[String,List[(String, Int)]] = Map(b -> List((b,2)), a -> List((a,1), (a,9)), c -> List((c,6)))

scala>
  • Map the values of res8 and reduce them to compute the sum.
scala> val res = grps.values.map {_.reduce((i,j) => (i._1, (i._2+j._2)))}

res: Iterable[(String, Int)] = List((b,2), (a,10), (c,6))
scala>
  • Sort res based on the 1st value of the tuple.
scala> res.toList.sorted
res23: List[(String, Int)] = List((a,10), (b,2), (c,6))

scala>

Thus, the function can be simply written as follows:

Thus we get the expected result.

Akka: Links, News And Resources (7)

Akka: Links, News And Resources (6)

Originally posted on Angel \"Java\" Lopez on Blog:

Previous Post
Next Post

You know: I’m interested in actor models in general, and Akka implementation in particular, having distributed applications. I started two projects implementing Akka ideas, in Node.js and in C#:

https://github.com/ajlopez/SimpleActors
https://github.com/ajlopez/Aktores

Now, more links of my collection of links:

mrb: Distributed Systems Archaeology: Ricon West, 2013.10.30
http://michaelrbernste.in/2013/11/22/distributed-systems-archaeology.html

Using Akka in Scala IDE – Stack Overflow
http://stackoverflow.com/questions/13585927/using-akka-in-scala-ide

Pacific Northwest Scala 2013 Akka in Production: Our Story by Evan Chan – YouTube
http://www.youtube.com/watch?v=c1heorOM2LE

Akka vs Storm | Blog of Adam Warski | Planet JBoss Community
http://planet.jboss.org/post/akka_vs_storm

Akka in Production: Our Story
http://www.slideshare.net/EvanChan2/akka-inproductionpnw-scala2013

typesafe.com
http://typesafe.com/blog/typesafe-gets-sprayed

Typesafe Reactive Platform Acquires New High-Performance HTTP Foundation
http://www.marketwired.com/press-release/Typesafe-Reactive-Platform-Acquires-New-High-Performance-HTTP-Foundation-1841738.htm

Dev Time: Cope with Failure – Actor Supervision in Akka
http://blog.florian-hopf.de/2013/10/cope-with-failure-actor-supervision-in.html

Akka Work Pulling Pattern to prevent mailbox overflow, throttle and distribute work » Michael on development
http://www.michaelpollmeier.com/akka-work-pulling-pattern/

Going Reactive: Event-Driven, Scalable, Resilient & Responsive Systems
http://www.slideshare.net/jboner/going-reactive-eventdriven-scalable-resilient-systems

Let it crash • Where Akka Came From

View original 18 more words