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

Ioke

Programming language, that seems like a abstract term because in most cases programmers just use it as a tool in their job. What motivations could be reason for creating a programming language.
Today I watched[1] Ola Bini talking about his creation Ioke. He discusses several properties of Ioke among them how close Ioke normal syntax is to its AST representation or Homoiconicity[2]

[1]http://blip.tv/file/2229441
[2]http://en.wikipedia.org/wiki/Homoiconicity

Clojure

Clojure is a dynmanic programming language which run on the JVM.  It is also a functional language which offers nice tools for concurrency handling. Since it doesn't give you the imperative fallback like scala it can be hard certain times to express a problem as your used to it. It is also a LISP which means it is essentially build upon a few primitives.

Counting lines in a file


(ns tokenize
(:import (java.io BufferedReader FileReader)))

;# This is a comment?
(defn process-file [file-name line-function counter]
(println " starting from imperative "
 (with-open [rdr (BufferedReader. (FileReader. file-name))]
  (reduce line-function counter (line-seq rdr) ))))

 (defn process-line [acc line]
  (+ acc 1))

(process-file "../../<filepath>" process-line 0)

Simple sum

(defn mysum [base arg1]
 (+ base arg1))

(println " works "(mysum (mysum 1 2) 4))
(time (dotimes [i 5] (println "woha!")))

line counting shorter


(ns tokenize
(:import (java.io BufferedReader FileReader)))
  (defn process-file [file-name]
   (with-open [rdr (BufferedReader. (FileReader. file-name))]
   (doseq [line (line-seq rdr)] (println line))))
(process-file "<filepath>")

Hello Clojure

(println "Hello, world!" (.. System (getProperties) (get "os.name")))

Since Clojure is a functional language and don't offer imperative constructs like loops it takes a bit to get used to but it is definitely  worth a first look. Evaluation concerning how it works out, building bigger systems and what performance issue possibly arise is of course a matter of further investigaion.

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/

Scala functions

Scala offers so many different concepts that it sometimes can be quite overwhelming. Scala blends object orientated and functional programming. The very basic block of functional programming is of course a function. Now a functions seem similar to a method but a function in scala can be a value. Today I found another usefull resource from the blogsphere[1]. The essential points discussed:

• the apply method
• Closures
• Partial Functions
• apply (ied) in many places

[1]http://creativekarma.com/ee.php/weblog/comments/scala_function_objects_from_a_java_perspective/