在Scala中的基本插入排序,Haskell版本的端口

Question

我试图从Haskell移植这个特定的插入排序.在大多数情况下,如果List长于输入或有时复制的值,我会得到奇怪的错误输出.你看到我失踪的东西吗？或者我可能没有正确地从Haskell复制语法:

如果你提供修复,你可以使用类似的语义,我试图理解这个特定的版本.

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

在insertPrime,改变这一行

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

至

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