java - Scala 中的基本插入排序，Haskell 版本的端口

Question

我试图从 Haskell 移植这个特定的插入排序。在大多数情况下，我得到奇怪的不正确输出，列表比输入长，有时是复制的值。你看到我想念的东西了吗？或者我没有正确地从 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