Basic sorting insertion in Scala, port version of Haskell

Question

I tried to migrate this particular insertion type from Haskell. In most cases, I get a strange incorrect output with a list that exceeds the input or sometimes copied values. You see something that I am missing. Or maybe I'm not copying the syntax from Haskell correctly:

If you provided a fix, can you use similar semantics, I tried 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 // 

Answer 1

In insertPrime change this line

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

to

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

Answer 2

In any case, although Scala does not have multiple submissions, pattern matching is somewhat close (minus 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 return functions, to avoid explicit parameter definitions, to make Haskell clearer equivalent. Of course, in normal Scala code, I would get some parameters and match them.

Answer 3

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

 insertSort xs = foldr insert [] xs 

So your Scala insertSort method comes down to calling foldRight . However, since Scala is a strict language, foldLeft preferred. In Haskell you can write:

 insertSort xs = foldl (flip insert) [] xs 

So all you have to do is flip the order of the arguments in insert and call foldLeft in your insertSort method.

Answer 4

Although in Scala coding I prefer the functional programming style (through combinators or recursion) to the imperative style (through variables and iterations), THIS TIME is for this particular problem, the old school imperative nested loops lead to a simpler and more efficient code.

I don’t think that returning to the imperative style is a mistake for certain classes of problems, such as sorting algorithms, which usually convert the input buffer (more like a procedure), and not lead to a new sorted collection.

Here 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, instead of using java.lang.Comparable I preferred scala.math.Ordered and Scala View borders rather than upper bounds. This 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))