Algorithm design techniques as high-level functions

algs.scala

/* Kuba "lambdaofgod" Bartczuk
   technique based on example from "Algorithms a functional approach" 
   sort of example of divide-and-conquer - mergesort
   to do - dynamic programming
*/

def divideAndConquer[T1,T2](simple : T1 => Boolean,
                            solve : T1 => T2, 
                            divide : T1 => List[T1], 
                            combine : (T1,List[T2]) => T2,
                            initProblem : T1) : T2 = {
    def dc(problem : T1) : T2 = {
        if (simple(problem))
            solve(problem)
        else
            combine(problem, divide(problem) map dc)}
    dc(initProblem)
}


def mergeSort[T]( l : List[T], ord : (T,T) => Boolean )  : List[T]= {

    def mSimple(l : List[T]) = { l.length <= 1 }

    def mSolve(l : List[T]) = l

    def mDivide(l : List[T]) = {
        val halflength = l.length / 2
        l.take(halflength) :: l.drop(halflength) :: Nil
    }

    def merge(lst : List[List[T]], comp : (T,T) => Boolean ) = {
         
        def mergeHelp(xs : List[T], ys: List[T]) : List[T] = {
                if (xs.isEmpty)
                    ys
                else if (ys.isEmpty)
                    xs
                else if ( comp(xs.head,  ys.head) ) 
                    xs.head :: mergeHelp(xs.tail,ys)
                else
                    ys.head :: mergeHelp(xs,ys.tail)
            }

        lst match {
            case xs :: ys :: _ => mergeHelp(xs,ys)
        }
    }

    divideAndConquer(mSimple, 
                    mSolve, 
                    mDivide, 
                    ( initProblem : List[T], lst : List[List[T]]   ) => merge(lst,ord) , 
                    l) 
}