2013-07-14

Functional Desing in Scala: Function definition

1:37 PM Posted by Yuriy Polyulya , ,

Methods and Functions can be defined in Scala with def and val keywords correspondingly.

Motivation:
    To define style of function definition in Scala. Show advantages and disadvantages of both way of function definition. Choose more natural style for functional design in Scala.

Proposal:
    Use anonymous functions instead of methods; always use curried function (Haskell style function); when deep parameters extraction needed - use PartialFunction. Make it possible to use composition and Functional Primitives (Function, Applicative, Monad) over functions.

Code:
  val flip: Int => State => State = 
    dy => {  // first argumetn
      // second argument with parameter extraction and guard conditions:
      case state @ State(Block(x, y), _, (w, h)) if(y > (h /2)) =>
        state copy (
          current = new Block(w - x, y + dy))

      // second argument without guard conditions:
      case state @ State(Block(x, y), _, _) =>
        state copy (
          current = new Block(x, y + dy))
   }

  // for types:
  case class Block(x: Int, y:Int)
  case class State(current: Block, wall: Seq[Block], gridSize: (Int, Int))





1. Function definition by "def" and "val" keywords:

Code:
  def f1(x: Int, y: Int): Int = x + y           // method type

  // OR:
  val f2: (Int, Int) => Int = (x, y) => x + y   // function type

  // Function call is equivalent:
  f1(10, 20)   ==  f2(10, 20)

Method type can be easy transformed to function type: Eta Expansion (SLS 6.26.5)
Code:
  def f1(x: Int, y: Int): Int = x + y
  val f2 = f1 _

  // Function call is equivalent:
  f1(10, 20) == f2(10, 20)

2. Parametric polymorphism on method definition:

Code:
  def head1[T](list: List[T]): T = list.head
  
  // OR:
  val head2: List[_] => _ = (l: List[_]) => l.head
In this case we can't manage relation between types and Eta expansion does not proper work with polymorphic functions:

Code:
  def head1[T](list: List[T]): T = list.head
  val head2 = head1 _       // Function[Nothing, Nothing]
  
  // Function call:
  head2(List(1, 2, 3))      // [Error] type mismatch found: Int(1); required: Nothing
Note: Parametric polymorphism is not applicable to anonymous function.

3. Lazy parameters (by-name parameters):

Code:
  def f1(x: Int)(y: => Int): Int = {
    var acc = 0
    while(x != y) acc += 1
    acc
  }

  // OR:
  val f2: Int => (=> Int) => Int =
    x => y => {
      var acc =0
      while(x != y) acc += 1
      acc
    }

  // OR use eta expansion:
  val f3 = f1 _

  // Function call:
  var i =0
  val res = f1(10) { // or f2 or f3
    i += 1
    i
  }

4. Recursion and tail recursion optimization:

It is natural to define recursive function in Functional Programming. Easy to define recursive function for method but for anonymous function need to use Y-combinator.

Code:
  // Y-Combinator definition:
  def Y[A,B](f: (A=>B)=>(A=>B)): A=>B = f(Y(f))(_)

  def fact1(n: Int): Int = {
    if(n == 1) 1 else n * fact1(n - 1)
  }

  // OR:
  val fact2: Int => Int =
    Y[Int,Int](f => n => if(n <= 0) 1 else f(n - 1) * n)

Tail recursion optimization applicable for method type only, but in case if it is needed internal method can be used. @tailrec attribute used for optimization guaranty.

5. Structural types in function/method definition:
Method & function can use stuctural type as parameter. Eta expansion perfect work with structural types.

Code:
  def f1(c: { def close(): Unit }): Unit = {
    c.close()
  }

  // OR:
  val f2: { def close(): Unit } => Unit =
    c => c.close()

  // Eta expansion:
  val f3 = f1 _

6. Curried function and function composition:

Currying is the technique of transforming a function that takes multiple arguments in such a way that it can be called as a chain of functions, each with a single argument.
Currying is applicable to functions only (some method declaration can b looks like curried function but it is not really curried method).

Code:
  val f: (Int, Int) => Int = (x, y) => x + y
  val fcurr = f.curried                            // function currying
  val g = fcurr(2)                                 // partially applied function

  g(4)                                             // == 2 + 4

Function composition is the application of one function to the results of another. In Scala function of one argument can be compose by "compose" and "andThen" methods.

Code:
  val f: Int => Int = x => x + 2
  val g: Int => Int = x => x * 2

  // Function composition:
  (f compose g)(1)         // == 4
  (f andThen g)(1)         // == 6

7. Parameter pattern matching:

PartialFunction is subtype of Function in Scala. This fact makes it possible to use advanced features of PartialFunction where Function type is expected.

Code:
  case class Block(x: Int, y:Int)                                          
  case class State(current: Block, wall: Seq[Block], gridSize: (Int, Int)) 
                                                                           
  val flip: State => State = {                                             
    case state @ State(Block(x, y), _, (w, _)) =>                          
      state copy (                                                         
        current = new Block(w - x, y))                                     
  }                                                                        
                                                                           
  val flipCondition: State => State = {                                    
    case state @ State(Block(x, y), _, (w, h)) if(y > (h /2)) =>           
      state copy (                                                         
        current = new Block(w - x, y))                                     
    case state: State => state                                             
  }                                                                        

To extract parameters from function argumets use pattern matching features:
- Variable Patterns (SLS 8.1.1)
- Extractor Patterns (SLS 8.1.8)
- Pattern Binders via '@' (SLS 8.1.3) (Haskell as-patterns)

Conclusion:


Features \ TypesMethodFuntion
Definition def val (_ => _)
Parametric polymorphism + -
Lazy parameters + +
Recursion + + (by internal def)
Strucural type arguments + +
Currying and Composition - +
Argument pattern matching + (by internal match) +