Filter with FlatMap (or collect)

I picked up this tip from one of Daniel Spiewak’s tweets. He tweeted a pro tip that uses flatMap to create a filtered list:

  1. list flatMap {
  2.   case st: String => Some(st)
  3.   case _ => None
  4. }


At a glance one might wonder why not simply use list.filter{_.isInstanceOf[String]}. The difference is that the flatMap will return a List[String].

However Scala 2.8 offers the collect method for doing a similar thing.

  1. def strings(list: List[Any]) = list flatMap {
  2.   case st: String => Some(st)
  3.   case _ => None
  4. }
  5. // returned list is a List[String]
  6. scala> strings("hi" :: 1 :: "world" :: 4 :: Nil)
  7. res11: List[String] = List(hi, world)
  8. // returned list is a List[Any] (not as useful)
  9. scala> "hi" :: 1 :: "world" :: 4 :: Nil filter {_.isInstanceOf[String]}
  10. res12: List[Any] = List(hi, world)
  11. // collect returns List[String]
  12. scala> "hi" :: 1 :: "world" :: 4 :: Nil collect {case s:String => s}           
  13. res13: List[String] = List(hi, world)

Continua a leggere

Pubblicato in Senza categoria

Implicit Parameter Resolution

This topic is a continuation of the previous implicit parameter topics:

This topic provides some explanation about how implicit parameters are resulted. There are very strict rules for which implicit value is to be applied to a implicit parameter. A simple way to think about it is that the “closest” definition will be used. Local scope, enclosing class, parent class, companion object of the desired type.

  1. class X(val i:Int)
  2. class Y(val i:Int)
  3. object X {
  4.   implicit def xx = new X(1)
  5. }
  6. class Method {
  7.   def x(implicit x:X)=println(x.i)
  8.   def y(implicit y:Y)=println(y.i)
  9. }
  10. trait M { 
  11.   self : Method =>
  12.   implicit def x1 = new X(10)
  13.   implicit def y1 = new Y(100)
  14.   def testy = y
  15.   def testx = x
  16. }
  17. trait SM extends M {
  18.   self : Method =>
  19.   implicit def x2 = new X(20)
  20.   implicit def y2 = new Y(200)
  21.   
  22.   def testy2 = y  
  23. }
  24. // implicit resolved from companion object of X
  25. new Method().x
  26. // explicit applied so that value is used
  27. new Method().x(new X(3))
  28. // implicit resolved from companion object of X
  29. // NOT from M.  This is because the call site of x 
  30. // is not within M therefore does not use the implicits in M
  31. // for resolution.
  32. (new Method with M).x
  33. implicit def x = new X(30)
  34. // local scope overrides companion object implicit
  35. new Method().x
  36. // explicit applied so that value is used
  37. new Method().x(new X(3))
  38. // local scope overrides companion object implicit
  39. (new Method with M).x
  40. // testy is defined within M so the implicits within M
  41. (new Method with M).testy
  42. // testx is defined within M so the implicit within M
  43. // overrides the companion object implicit
  44. (new Method with M).testx
  45. // testy is within M (not SM) so the implicit within M
  46. // is used
  47. (new Method with SM).testy
  48. // testy2 is within SM so the implicit within SM 
  49. // overrides the implicit in M and the companion object
  50. (new Method with SM).testy2


Output:

1
3
1
30
3
30
100
10
100
200
Continua a leggere

Pubblicato in Senza categoria

Conjugating verbs in Haskell


> {-# LANGUAGE RecordWildCards #-}
> import Data.Maybe
> import Data.Default
> import Control.Monad.Writer hiding (First)

I’ll show you an English verb conjugator. Although handling inflections is complex, the structure of the language can be expressed idiomatically, using a monad. You’ll see that things like “perfect continuous” are really “perfect” on top of “continuous”, in code.

First, some boring code and auxiliary functions.


> data Tense = Past | Present | Future
> type Infinitive = String
> data Person = First | Second | Third
> -- plural in English is the same form as second person

> pastForms inf = fromMaybe (inf++"ed", inf++"ed") $
> lookup inf [("do", ("did", "done")),
> ("have", ("had", "had")),
> ("be", ("was", "been")),
> ("drive", ("drove", "driven")),
> ("build", ("built", "built"))]

> presentParticiple inf | last inf == 'e' && inf /= "be" = init inf ++ "ing"
> | otherwise = inf ++ "ing"

> pastParticiple inf = snd $ pastForms inf

> conjugate1 :: Tense -> Person -> Infinitive -> String
> conjugate1 Future p inf = "will " ++ inf
> conjugate1 t p "be" = case (t, p) of
> (Present, First) -> "am"
> (Present, Second) -> "are"
> (Present, Third) -> "is"
> (Past, Second) -> "were"
> (Past, _) -> "was"

> conjugate1 Past p inf = fst $ pastForms inf
> conjugate1 Present Third "have" = "has"
> conjugate1 Present Third "do" = "does"
> conjugate1 Present Third inf = inf ++ "s"
> conjugate1 Present _ inf = inf

We can conjugate verbs in three tenses, and form participles. For example:


> test1 = conjugate1 Future First "drive"
> test2 = conjugate1 Present Third "phone"
> test3 = presentParticiple "have"

Adding “perfect”
Now the fun begins.

Exercise: Allow forming perfect tenses:


> conjugate2 :: Bool -> Tense -> Person -> Infinitive -> String

(For example, conjugate2 True Present Third “drive” should be “has driven”)

Solution:

Perfect is “have” + past participle. You can express this directly:


> conjugate2 False tense person inf = conjugate1 tense person inf
> conjugate2 True tense person inf = conjugate1 tense person "have" ++ " " ++ pastParticiple inf

Adding “continuous”
It will be downhill now.

Exercise: Allow forming continuous tenses:


> conjugate3 :: Bool -> Bool -> Tense -> Person -> Infinitive -> String

where the first parameter will be continuous or not. For example, conjugate3 True False Present Third “drive” should be “is driving”.

Solution:

It’s be + present participle.


> conjugate3 False perf tense person inf = conjugate2 perf tense person inf
> conjugate3 True perf tense person inf = conjugate2 perf tense person "be" ++ " " ++ presentParticiple inf

This composes nicely:


> test4 = "he " ++ conjugate3 True True Present Third "drive"

Adding passive voice
Exercise: Allow forming passive voice:


> conjugate4 :: Bool -> Bool -> Bool -> Tense -> Person -> Infinitive -> String

> test5 = "the house " ++ conjugate4 True True False Present Third "build"

Solution:


> conjugate4 False cont perf tense person inf = conjugate3 cont perf tense person inf
> conjugate4 True cont perf tense person inf = conjugate3 cont perf tense person "be" ++ " " ++ pastParticiple inf

Merging
conjugate2, conjugate3 and conjugate4 can be joined into a single function.
Remembering all arguments in order and specifying them every time is problematic. This is described in Brent Yorgey’s Haskell anti-pattern – incremental ad-hoc parameter abstraction. Also there’s a lot of repetition.


> conjugate5 :: Bool -> Bool -> Bool -> Tense -> Person -> Infinitive -> String
> conjugate5 True continuous perfect tense person inf =
> conjugate5 False continuous perfect tense person "be" ++ " " ++ pastParticiple inf
> conjugate5 _ True perfect tense person inf =
> conjugate5 False False perfect tense person "be" ++ " " ++ presentParticiple inf
> conjugate5 _ _ True tense person inf =
> conjugate5 False False False tense person "have" ++ " " ++ pastParticiple inf
> conjugate5 _ _ _ tense person inf = conjugate1 tense person inf

Using records


> data ConjugateOptions = ConjugateOptions { passive :: Bool,
> perfect :: Bool,
> continuous :: Bool,
> person :: Person,
> tense :: Tense }

> instance Default ConjugateOptions where
> def = ConjugateOptions False False False First Present

> conjugate6 :: ConjugateOptions -> Infinitive -> String
> conjugate6 ([email protected]{ .. }) inf
> | passive = conjugate6 o { passive = False } "be" ++ " " ++ pastParticiple inf
> | continuous = conjugate6 o { continuous = False } "be" ++ " " ++ presentParticiple inf
> | perfect = conjugate6 o { perfect = False } "have" ++ " " ++ pastParticiple inf
> | otherwise = conjugate1 tense person inf

Much better – we can use it like


> test6 = conjugate6 def { perfect=True } "paint"

Using the Writer monad
conjugate6 is doing recursion on some infinitive and adds “remaining part” to the end. The Writer monad can express this.


> plumb :: Infinitive -> (Infinitive -> String) -> Infinitive -> Writer [String] Infinitive
> plumb aux participle inf = Writer (aux, [participle inf])

> passive' = plumb "be" pastParticiple
> continuous' = plumb "be" presentParticiple
> perfect' = plumb "have" pastParticiple

> conjugate7 :: Tense -> Person -> (Infinitive -> Writer [String] Infinitive) -> Infinitive -> String

> conjugate7 tense person tr inf =
> let (a,b) = runWriter (tr inf)
> in unwords $ (conjugate1 tense person a):(reverse b)

You can join those different “higher order verbs” using >=>.


> test7 = "he " ++ conjugate7 Past Third (continuous' >=> perfect') "paint"

and add new new ones instantly:


> learn = plumb "learn" ("to "++)

> test8 = "I " ++ conjugate7 Present First (learn >=> perfect') "love" ++ " Haskell"

Obviously there is a lot missing – inflections (“he goes”, “he panicks”), irregular verbs, modal verbs, negation, “used to”, “have something done”, interrogative mood… It gets dirty then.

You can write such conjugator in similar languages, like German.

Haskell is a great language – imagine how would you write conjugate1 without pattern matching, or writing the plumbing in conjugate5 again, when Writer can do that for you. Continua a leggere

Pubblicato in Senza categoria

Implicit Parameters

Evidently the topic of implicit parameters has not yet been correctly addressed. There have been several topic that refer to implicit parameters but none that directly discuss them. So before I continue with the topic of implicit parameter resolution I will discuss implicit parameters.

First, implicit parameters are not the same as implicit object conversions. Implicit parameters provide a way to allow parameters of a method to be “found”. This is similar to default parameters at a glance but in fact is a different mechanism for finding the “default” value. It differs from implicit object conversion in that it is only a way for parameters for a method to be resolved. Implicit object conversion allows methods to appear to be called on one object when in fact that object is being converted behind the scenes to another type. (more or less)

An implicit parameter is a parameter to method or constructor that is marked as implicit. This means that if a parameter value is not supplied then the compiler will search for an “implicit” value defined within scope (according to resolution rules.) Implicit parameter resolution rules will be discussed soon.

Example:

  1. scala> def p(implicit i:Int) = print(i)
  2. p: (implicit i: Int)Unit
  3. // defining a val/var/def as implicit 
  4. // means that it will be considered during implicit resolution
  5. scala> implicit val v=2
  6. v: Int = 2
  7. // scope is searched for a implicit value to sue
  8. // v is found as marked implicit
  9. scala> p               
  10. 2
  11. // explicit declarations always overrides implicit values
  12. scala> p(1)
  13. 1


Implicit parameters are very nice for simplifying APIs. For example the collections use implicit parameters to supply CanBuildFrom objects for many of the collection methods. This is because normally the user does not need to be concerned with those parameters. Another example is supplying an encoding to an IO library so the encoding is defined once (perhaps in a package object) and all methods can use the same encoding without having to define it for every method call.

One important restriction is that there can only be a single implicit keyword per method. It must be at the start of a parameter list (which also makes all values of that parameter list be implicit). I further understand that only the last parameter list may be implicit.

Here are several illegal examples:

  1. // implicit is not in last parameter list
  2. scala> def pp(implicit i:Int, a:Int)(b:Int) = println(a,i)                 
  3. < console>:1: error: '=' expected but '(' found.
  4.        def pp(implicit i:Int, a:Int)(b:Int) = println(a,i)
  5. // there are 2 implicit parameters
  6. scala> def pp(implicit j:Int, a:Int)(implicit i:Int,b:Int) = println(a,i)
  7. < console>:1: error: '=' expected but '(' found.
  8.       def pp(implicit j:Int, a:Int)(implicit i:Int,b:Int) = println(a,i)
  9. // implicit is not the first parameter of the parameter list
  10. scala> def pp(a:Int, implicit i:Int) = println(i,j)         
  11. < console>:1: error: identifier expected but 'implicit' found.
  12.        def pp(a:Int, implicit i:Int) = println(i,j)
  13.                      ^


Here are several legal examples (Updated with useage examples):

  1. scala> implicit def v = 7
  2. v: Int
  3. scala> implicit var x = 10L
  4. x: Long
  5. // i is implicit
  6. scala> def pp(a:Int)(implicit i:Int) = println(a,i)
  7. pp: (a: Int)(implicit i: Int)Unit
  8. scala> pp(3)
  9. (3,7)
  10. // both i and b are implicit
  11. scala> def pp(a:Int)(implicit i:Int, b:Long) = println(a,i,b) 
  12. pp: (a: Int)(implicit i: Int,implicit b: Long)Unit
  13. scala> pp(4)               
  14. (4,7,10)
  15. // both i and b are implicit
  16. scala> def pp(implicit i:Int, b:Long) = println(i,b)  
  17. pp: (implicit i: Int,implicit b: Long)Unit
  18. scala> pp
  19. (7,10)
  20. // all or none of the parameters must be supplied
  21. scala> pp(2)
  22. < console>:13: error: not enough arguments for method pp: (implicit i: Int,implicit b: Long)Unit.
  23. Unspecified value parameter b.
  24.        pp(2)
  25. // This is syntactically legal but I cannot seem to implicitly invoke this
  26. // I would recommend: def pp(b:Long*)(implicit i:Int) = println(i,b)
  27. scala> def pp(implicit i:Int, b:Long*) = println(i,b)
  28. pp: (implicit i: Int,implicit b: Long*)Unit
  29. scala> pp(3,1,2,3)
  30. (3,WrappedArray(1, 2, 3))
  31. scala> def pp(b:Long*)(implicit i:Int) = println(i,b)
  32. pp: (b: Long*)(implicit i: Int)Unit
  33. scala> pp(1,2,3)
  34. (7,WrappedArray(1, 2, 3))


A related topic is Companion Object implicits. Continua a leggere

Pubblicato in Senza categoria

sacto, northern cal!

hanging out in the old hometown of stockton… yesterday we went to one of the greatest mexican restaurants in the world… el novillero in sacramento. many a meal was consumed here in the early pavement days! we’re off to dublin in a few days to start… Continua a leggere

Pubblicato in Senza categoria

Break Performance

In the Breaks comments there were several questions about the performance of the Scala break command vs the Java break command. So I decided to take a look.

The code for the tests is available on GitHub at: Scala Benchmarks. Feel free to play around with it.

I personally don’t think these tests say anything of particular import because they only test how fast the Java break is vs the Scala break without doing any work in the loop. So I don’t expect these number would ever been seen in the real world. However that said if you have a tight loop with minimal processing then a Scala break may not be the correct construct to use.

Here is the Java test (labelled JavaSimpleBreak)

  1. int i = 0;
  2. while (i < 10) {
  3.   if(i==1) break;
  4.   i += 1;
  5. }


Here is the Scala test (labelled ScalaSimpleBreak)

  1. var i = 0;
  2. breakable {
  3.   while (i < 10) {
  4.     if(i==1) break;
  5.     i += 1;
  6.   }
  7. }


Out of curiosity I also added a test that created a new Exception each iteration (labelled ScalaException):

  1. var i = 0;
  2.   while (i < 10) {
  3.     if(i==1) throw new Exception();
  4.     i += 1;
  5.   }


And also a test that just throws the same ScalaBreak exception each time. This one is weird since Scala Simple Break also throws the same exception but is much much faster so I think there is something about popping the stack in the example compared to the ScalaSimpleBreak test.

  1. var i = 0;
  2. breakable {
  3. while (i < 10) {
  4. if(i==1) break;
  5. i += 1;
  6. }
  7. }


The results of the tests:

First, don’t compare the break tests to the Exception tests. They are sufficiently different to not be worth comparing.
Second, remember that this is a micro benchmark and has very little relationship to reality.

90000000 iterations. Swapping every 90000000 tests
JavaSimpleBreak = 254 (0.0016279129387033098)
ScalaSimpleBreak = 2475 (0.015862537493270438)
ScalaBreakException = 18806 (0.12052964852462379)
ScalaException = 156028 (1.0)

90000000 iterations. Swapping every 500000 tests
JavaSimpleBreak = 772 (0.005138547761203965)
ScalaSimpleBreak = 2351 (0.015648608531853004)
ScalaBreakException = 19346 (0.12876987692778744)
ScalaException = 150237 (1.0)

90000000 iterations. Swapping every 500 tests
JavaSimpleBreak = 790 (0.005242446563543097)
ScalaSimpleBreak = 2247 (0.014911110668710557)
ScalaBreakException = 19213 (0.1274976276270298)
ScalaException = 150693 (1.0)
Continua a leggere

Pubblicato in Senza categoria

Companion Object Implicits

When a method requires an implicit there are several ways that the implicit is resolved. One way is to search for an implicit definition in the companion object of the required type. For example: def x(implicit m:MyClass) parameter m will search local scope, class hierarchy and the MyClass companion object for an implicit val or def. (More on implicit resolution later).

To demonstrate the method put the following code block into a file and run the script:

  1. class X(val i:Int) {
  2.   def add(implicit x:X)=println(x.i+i)
  3. }
  4. object X {
  5.   implicit def xx = new X(3)
  6. }
  7. // implicit is obtained from companion object of X
  8. new X(3).add
  9. val other = new {
  10.   def print(implicit x:X)=println(x.i)
  11. }
  12. // implicit is obtained from companion object of X
  13. other.print
  14. implicit def x = new X(32)
  15. // implicit is obtained local scope
  16. other.print


Running: scala impl.scala should produce:
6
3
32 Continua a leggere

Pubblicato in Senza categoria

thanks southland!

ok. we conquered coachella. now the anxiety can cease. hope all who saw us enjoyed. we know we did. all in all, it was a fun show. we were a little nervous when we went on, but after a few songs we hit our stride. the response from the crowd was very g… Continua a leggere

Pubblicato in Senza categoria

food, coffee, cocktails, party!

this is my breakfast on our united airlines flight from tokyo to los angeles… inedible! and you wonder why this airline goes bankrupt.and this is jeremy lemos travel/tour blog for the chicago reader. jeremy does killa monitors for us and is a slick d… Continua a leggere

Pubblicato in Senza categoria

Breaks

Scala 2.8 added the break control flow option. It is not implemented as a special language feature. Rather it is simply implemented as an object/trait using standard Scala mechanisms. If you are interested in creating a control flow object similar to this look at the Defining Custom Control Structures post.

The Break functionality is works basically how you would expect:

  1. // Import the control flow methodsmethods
  2. scala> import util.control.Breaks._
  3. import util.control.Breaks._
  4. // pass a function to the breakable method
  5. scala> breakable {
  6.      | for (i <- 1 to 10 ) {
  7.      | if(i > 5) break  // call break when done
  8.      | println(i)
  9.      | }
  10.      | }
  11. 1
  12. 2
  13. 3
  14. 4
  15. 5


Pretty intuitive but beware, break only breaks out to the first enclosing breakable. Here is an example of the issue:

  1. scala> def loop(f : Int => Boolean) = breakable {
  2.      | for (i <- 1 to 300) if (f(i)) break else println(i)
  3.      | }
  4. loop: (f: (Int) => Boolean)Unit
  5. // This never ends because break is caught by breakable in the loop method
  6. scala> breakable {
  7.      | while(true) {
  8.      | loop{ i => break; true }
  9.      | }
  10.      | }


Fortunately the implementers provide an elegant way to handle these sorts of cases. The Breaks object extends the Breaks class. By instantiating other instances of Breaks it is possible to control which breaks capture

  1. scala> import scala.util.control._
  2. import scala.util.control._
  3. scala> 
  4. scala> def loop(f : Int => Boolean) = {
  5.      |   val Inner = new Breaks
  6.      |   Inner.breakable {
  7.      |     for (i <- 1 to 4) if (f(i)) Inner.break else println(i)
  8.      |   }
  9.      | }
  10. loop: (f: (Int) => Boolean)Unit
  11. scala> 
  12. scala> val Outer = new Breaks
  13. Outer: scala.util.control.Breaks = scala.util.control.Breaks@1ba4806
  14. scala> Outer.breakable {
  15.      |   while(true) {
  16.      |     loop{ i => if(i==4) Outer.break; false}
  17.      |   }
  18.      | }
  19. 1
  20. 2
  21. 3

Continua a leggere

Pubblicato in Senza categoria