CODEWITHSUNDEEP
javasortingscalahaskell
Berlin Brown
Berlin Brown

Reputation: 11734

Basic Insertion sort in Scala, port of Haskell version

I was trying to port this particular insertion sort from Haskell. I get strange incorrect output in most cases with a List longer than the input or sometimes copied values. Do you see something I am missing. Or maybe I not copying the syntax from Haskell properly:

If you provide a fix, could you use similar semantics, I was trying to understand this particular version.

object InsertionSortApp {

/* 
 * Based on Haskell version:
  insert e [] = [e]
  insert e lst@(x:xs)
    | e < x     = e : lst
    | otherwise = x : (insert e xs)
  insertionSort lst = insertionSort' lst [] where
    insertionSort' [] lst = lst
    insertionSort' (x:xs) lst = insertionSort' xs (insert x lst)
 */

  def insert(e : Integer, lst : List[Int]) : List[Int] = {
      def insertPrime(xs: List[Int]) : List[Int] = xs match {
        case Nil => List(e)
        case x :: xs if (e < x) => e :: lst        
        case x :: xs => x :: insertPrime(xs)               
      }   
      return insertPrime(lst)
  }

  def insertionSort(origList: List[Int]) : List[Int] = {
      def insertionSortPrime(xs: List[Int], lst: List[Int]) : List[Int] = xs match {
        case Nil => lst
        case x :: xs => insertionSortPrime(xs, insert(x, lst))
      }
      insertionSortPrime(origList, List())
  }

  def main(args : Array[String]) : Unit = {
    println("Running - Insertion Sort Test")
    val lst = List(1, 7, 3, 4, 5)
    println("Test: " + (insertionSort(lst)))
  }
} // End of object //

Upvotes: 4

Views: 1495

Answers (4)

pangiole
pangiole

Reputation: 991

Even though, when coding Scala, I'm used to prefer functional programming style (via combinators or recursion) over imperative style (via variables and iterations), THIS TIME, for this specific problem, old school imperative nested loops result in simpler and performant code.

I don't think falling back to imperative style is a mistake for certain classes of problems, such as sorting algorithms which usually transform the input buffer (more like a procedure) rather than resulting to a new sorted collection.

Here it is my solution:

package bitspoke.algo

import scala.math.Ordered
import scala.collection.mutable.Buffer

abstract class Sorter[T <% Ordered[T]] {

  // algorithm provided by subclasses
  def sort(buffer : Buffer[T]) : Unit

  // check if the buffer is sorted
  def sorted(buffer : Buffer[T]) = buffer.isEmpty || buffer.view.zip(buffer.tail).forall { t => t._2 > t._1 }

  // swap elements in buffer
  def swap(buffer : Buffer[T], i:Int, j:Int) {
    val temp = buffer(i)
    buffer(i) = buffer(j)
    buffer(j) = temp
  }
}

class InsertionSorter[T <% Ordered[T]] extends Sorter[T] {
  def sort(buffer : Buffer[T]) : Unit = {
    for {
      i <-  1 until buffer.length
      j <-  i until 0 by -1
      if (buffer(j) < buffer(j - 1))
    }
    swap(buffer, j, j - 1)
  }
}

As you can see, to achieve parametric polymorphism, rather than using java.lang.Comparable, I preferred scala.math.Ordered and Scala View Bounds rather than Upper Bounds. That's certainly works thanks to Scala Implicit Conversions of primitive types to Rich Wrappers.

You can write a client program as follows:

import bitspoke.algo._
import scala.collection.mutable._

val sorter = new InsertionSorter[Int]
val buffer = ArrayBuffer(3, 0, 4, 2, 1)
sorter.sort(buffer)

assert(sorter.sorted(buffer))

Upvotes: 0

Landei
Landei

Reputation: 54584

The Haskell version (and hence your Scala version) can be simplified. Consider:

insertSort xs = foldr insert [] xs

So your insertSort method in Scala boils down to a foldRight call. However as Scala is a strict language, foldLeft should be preferred instead. In Haskell you could write:

insertSort xs = foldl (flip insert) [] xs

So all you have to do for this is to flip the argument order in insert and call foldLeft in your insertSort method.

Upvotes: 0

Daniel C. Sobral
Daniel C. Sobral

Reputation: 297265

For whatever it is worth, while Scala does not have multiple dispatch, the pattern matching is somewhat close (minus it being strict):

def insert:  (Int, List[Int]) => List[Int] = {
  case (e, List())          => List(e)
  case (e, lst @ (x :: xs)) =>
    if (e < x) e :: lst
    else x :: insert(e, xs)
}

def insertionSort(lst: List[Int]) = {
  def `insertionSort'`: (List[Int], List[Int]) => List[Int] = {
    case (List(), lst)  => lst
    case (x :: xs, lst) => `insertionSort'`(xs, insert(x, lst))
  }
  `insertionSort'`(lst, Nil)
}

I wrote insert and insertionSort' as returning functions to avoid naming the parameters explicitly, just to make the equivalence to Haskell clearer. Of course, in normal Scala code I'd receive some parameters and match on them·

Upvotes: 2

hammar
hammar

Reputation: 139900

In insertPrime, change this line

 case x :: xs if (e < x) => e :: lst

to

 case x :: xs if (e < x) => e :: x :: xs

Upvotes: 5

Related Questions