Simple Problem, Simple Solution(s)

Borrowed from :
http://learnyouahaskell.com/starting-out#im-a-list-comprehension
Which right triangle that has integers for all sides and all sides equal to or smaller than 10 has a perimeter of 24? 


Haskell
[ (a,b,c) | c <- [1..10], b <- [1..c], a <- [1..b], a^2 + b^2 == c^2, a+b+c == 24]


Scala

for {c <- 1 to 10; b <- 1 to c; a <- 1 to b; if(a+b+c == 24 && (a*a) +(b*b) ==(c*c))} yield (a,b,c)

C#

var result= from c in Enumerable.Range(1, 10)
from b in Enumerable.Range(1, c)
from a in Enumerable.Range(1, b)
where a+b+c == 24 && (a*a) + (b*b) == (c*c)
select a+" "+b+" "+c;


More on comprehensions:
http://patternsinfp.wordpress.com/2012/01/19/comprehensions/
Haskell
[2 * a + b | a <-[1,2,3], b <- [4,5,6],  b `mod` a == 0]


Scala
for{a <- 1 to 3; b <- 4 to 6; if (b % a == 0)} yield(2 * a + b)

99 Problems in Scala

99 Problems originated from Prolog [1] but I came across it here [2] where SCala is used to solve the problems.


==03==
def findMe(l:List[Int], i:Int):Int = { if(i==0) l.head else findMe(l drop 1,i-1) }


==04==
l.foldLeft(0) {(a,b) => a+1 }


==05==
def myRev[A](l:List[A]):List[A] = l.foldLeft([List[A]()) { (a,c) => c :: a}


==14==
l.foldLeft(Nil.asInstanceOf[List[Int]]) {(c,a) => (a :: a :: c) }


==15==
def consmore (l:List[Int], count:Int, element:Int):List[Int] = if(count==0) l else consmore(element::l,count-1, element)


==28==
ll=List[List[Int]] = List(List(1, 2), List(1, 2, 3), List(4, 5), List(5), List(3, 4, 5), List(7), List(1, 2, 3, 4, 5), List(1, 2, 3, 4))
val r1=ll.foldLeft(List[(Int,Int)]()) { (a,b) => (b.length,ll indexOf b) :: a}
val r2= r1 sortWith ((t1,t2)=> t1._1 > t2._1)
val finalResult=r2.foldLeft(List[List[Int]]()) { (a,b) => ll(b._2) :: a }


The level of difficulty rises along. So while beeing lazy because I didn't want to solve all 99. I pick P50 as an quick exercise to solving a more complex task with scala.
==50==

class Node(val h:Int, val char:Char){

def this(h:Int) = this(h,'1');

private var left:Node = null

private var right:Node = null

def getLeft() = left

def getRight() = right

def setLeft(k:Node) = {left = k}

def setRight(k:Node) = {right = k}

def setLeftRight(l:Node, r:Node)= {left = l; right = r}

def hasEdge() = left != null || right != null

def isLeaf() = !char.isDigit

override def toString() = h+" L:"+left+" R:"+right

}

import scala.collection.mutable.HashMap

def findFreq(s:String):HashMap[Char,Int] = {
val r=new HashMap[Char,Int];
s.distinct.foreach(x=> r+= (x -> (s count(y => y==x)) ) );
r
}

def sortNodes(a:Node,b:Node) = a.h < b.h

val fr=findFreq(”MISSISSIPPI”)

val t2=(for {b <- fr; fre =b._2; element=b._1 } yield new Node(fre,element)).toList

val r2=t2 sortWith(sortNodes)

def transform(var l:List[Node]) = {

val r=l take 2
if(r.size > 1)
l=new Node(r(1).haeuf+r(2).haeuf)::l

}

Neu gefunden:


[1]http://sites.google.com/site/prologsite/prolog-problems/
[2]http://aperiodic.net/phil/scala/s-99/
[3]https://github.com/etorreborre/s99

Evaluation Strategy and Laziness

Coming from Java I guess I'm used to "simple" strict evaluation

Scala allows for three kinds of evaluation

1. List.range(a, b) - strict evaluation
2. Stream.range(a, b) - lazy evaluation, evaluated once and cached
3. (a to b) - lazy evaluation, evaluated each time it is used

Call by name parameter

def someMethod(test:Boolean, findMe:String,  expensiveSearch:String ) = {

if(test)

  true

else

 expensiveSearch contains findMe

}

Instead of the type String for expensiveSearch use => String or () => String

You can choose which is most appropriate for your situation.

[2] Refers to a Haskell example which demonstrated that you have to turn your program quite a bit upside down to get real benefit from laziness. Is it worth?

[1]http://dcsobral.blogspot.com/2009/05/scalas-projections.html
[2]http://debasishg.blogspot.com/2009/03/learning-haskell-laziness-makes-you.html

Practically Functional

A very nice read up by Daniel Spiewak[1].
Scala combines OOP and FP. But how to use FP in practice? Practically Functional gives a fine introduction starting with the following "functional trademarks":

• referential transparency
• higher order functions
• closures
• immutability

Which then are described as "functional idioms" using a classification that looks like this:
Recursion -> HOF -> Combinators -> Monads
where each Level raises the level of abstraction.

Recursion
If functional programming does not allow loops then how do you do something repeatedly? The answer  is via recursion. To assist the programmer with that Scala offers nested methods.


Higher Order Functions
HOF are functions which take functions as their arguments. Some examples are:

• foldLeft, foldRight ( catamorphism)
• map ( "mapping" over a collection)
• flatMap ( "map" and afterwards "flatten")

Combinators
There are three kinds of Combinators:

• Sequential ( first a, then b)
• Disjoint (either a or b)
• Literal(exactly foo)

Monads

Properties:

• Typ constructor
• Single argument constructor
• flatMap / >>= (bind)

It is really nice to see such eye opening examples which really help you to understand code better and still do the job:

def readPeople(files: List[String]): List[Person] = {
  for {
    file <-files
    props <-readFile(file)
    firstName <-props get"name.first"
    lastName <- props get "name.last"
    ageString <- props get "age"
    age <- toInt(ageString)
  } yield new Person(firstName, lastName, age)
}


[1] pdf file

functional vs. imperative

Today I came across this post[1]. It discusses about readability, comparing functional and imperative code snippets. I think its quite hard to tell which reads better because it depends on you think it should work. I guess this shows how important code style guides are when it comes to big scala code basis, involving possibly many different team members.


[1]http://www.drmaciver.com/2008/08/functional-code-not-equal-good-code/

more on Scala

What is interesting about Scala that it offers a lot of powerful features.

Context Operations
Since Methods can be used in infix notation and you can use symbols as method names (like *,/,+,-) , it is important to view them always in context or to be specific in scope of the current code.

Many of those features derive from functional programming. Which seems a vast space to explore. But for now I may start with closures.


No Statics
Scala is in fact more OO than Java, it removes statics completely and introduces another construct the 'Object'. By defining an object in scala you define an single instance module or singleton, which can be referred to without using an constructor.


Closures and Functional Programming
So I stumbled about this blog post[1].  While it only started with the title Closures, it offers quite more than just that. The post discusses concepts which define algebraic structures, e.g.: associativity. The MyClass example seems simple and compelling. In quite a different manner (than so far for me) the author describes functional programming and how it can be useful. I really like that. Functional programming is a broad topic and this particular spot on helped me to get started.

Some more advanced topics from functional programming would include topics like: Monads, Applicative, Arrows and Zipper. Some useful links:

[1]http://aabs.wordpress.com/2008/05/29/functional-programming-lessons-from-high-school-arithmetic/
[2]http://debasishg.blogspot.com/2008/03/monads-another-way-to-abstract.html
[3]http://james-iry.blogspot.com/2007/09/monads-are-elephants-part-1.html

A closer look at Scala

So I have been reading more about Scala recently and it has been interesting reads so far.  As I consider myself a "Java-Refugee" I  was surprised to find this [1]. Scala surely has some different concepts some of them I want to write down here.

Methods
A few examples of method declarations:

//this method does nothingdef firstName() = {
 var back:String ="empty"
}

//this method doesn't do eitherdef firstName() = {
 var back:String ="empty"
 back = "still nothing"
}

//finally return the back variable
def firstName() = {
 var back:String ="empty"
 back
}

//declare the return type explicitly 
def firstName():String = {
 var back:String ="empty"
 back 
}

Note here in the last example that the last statement in the method is returned. It is also possible to use "return back" instead of just "back". The second example fails to return a value because the last line contains an assignment.
If you wanted to override a method in a subclass you have to declare it explicit via the override modifier.


Closures

Lastly a short example of Closures (=>), which offer a very nice alternative to anonymous inner classes in java:

val arr = Array(1, 2, 3, 4, 5)
val sum = arr.reduceRight((a:Int, b:Int) => a + b)


println(sum)

So reduceRight is a method which takes two values as parametes from the array(arr) and awaits a result originating from an operation involving these two parameters. So simply in this case, our result value sum will contain a sum over all elements of the value arr. 


Statics in Scala
There is no static keyword in Scala. Instead the concept of a Singleton is applied through the object keyword. If a class and an object have the same name the latter is described as companion object. 
Pattern matching
Pattern matching seems at a very first glance related to the switch statement in java, but there are so many differences and it turn out to be much more useful.   
Java:

int number= ..
String res="";

  switch (number) {
   case 1: res="ONE"; break;
   case 2: res="TWO"; break;
   case 3: res="THREE";  break;
   default: res=" i don't know";
 }

Scala:


val number=..
val res=""


res = i match{
   case 1 => "ONE"

   case 2 => "TWO"

   case 3 => "THREE"

   case _ => " i don't know"

}


Scala's case statement can't fall through, you don't have to use a break statement like in Java. The pattern matching is not restricted to primitives (int in java) you may use any type or object. 
Case classes
Note here that the underscore "_" has different meanings, so it should be used carefully and depending on the context in its.
Some Random thoughts pending:


Exceptions
Scala does not have the concept of checked exceptions. While this makes method declarations cleaner (IMHO), you have to take care of it either way. Since pattern matching works on types you can do nice things like this:


try {
..
} catch {
case e:SQLException => println(”Database error”)
case e:MalformedURLException => println(”Bad URL”)
case e:_ => println(”any other Error”)
}
Traits
Traits provide a mix-in mechanism which is similar to multiple inheritance but avoids some pitfalls like the diamond problem through a linearization mechanism. But still traits seem like a heavy topic since you have to think about initialization order. What I really like about traits is that you can attach or mix-in traits dynamically into an class:
trait funny { def saySome() = "hoho"}
class silent{}


val s= new silent() with funny
s.saySome //prints "hoho"


So you can put in Code in existing classes with extending them. I find this very interesting.
Left random Notes:

• class names don't have to match filenames
• While in Java you have only interfaces and classes in Scala you have 3 basic entities: classes, traits and objects
• the constructor concept seems a little awkward since you write it directly in the class definition
• imports can be scoped, this is pretty nice e.g. if you want to limit an important to an inner method 

[1] http://www.codecommit.com/blog/scala/roundup-scala-for-java-refugees