Базовая сортировка вставок в 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

Answer 2

Сколько бы это ни стоило, в то время как Scala не имеет многократной отправки, сопоставление с образцом несколько близко (за исключением того, что оно строгое):

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)
}

Я написал insert и insertionSort' как возвращающие функции, чтобы избежать явного именования параметров, просто чтобы сделать эквивалентность Haskell более понятной. Конечно, в обычном Scala-коде я получал бы некоторые параметры и сопоставлял бы их ·

Answer 3

Несмотря на то, что при кодировании Scala я привык отдавать предпочтение стилю функционального программирования (с помощью комбинаторов или рекурсии), а не императивному стилю (с помощью переменных и итераций), ЭТО ВРЕМЯ, для этой конкретной проблемы императивные вложенные циклы старой школы приводят к более простой и производительный код.

Я не думаю, что возврат к императивному стилю является ошибкой для определенных классов проблем, таких как алгоритмы сортировки, которые обычно преобразуют входной буфер (скорее как процедура), а не приводят к новой отсортированной коллекции.

Вот мое решение:

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)
  }
}

Как видите, для достижения параметрического полиморфизма вместо использования java.lang.Comparable я предпочел scala.math.Ordered и Scala View Bounds, а не Upper Bounds. Это, безусловно, работает благодаря Scala Implicit преобразованию примитивных типов в Rich Wrappers.

Вы можете написать клиентскую программу следующим образом:

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))

Answer 4

Версия Haskell (и, следовательно, ваша версия Scala) может быть упрощена.Рассмотрим:

insertSort xs = foldr insert [] xs

Итак, ваш метод insertSort в Scala сводится к вызову foldRight.Однако, поскольку Scala является строгим языком, вместо него следует отдавать foldLeft.В Haskell вы можете написать:

insertSort xs = foldl (flip insert) [] xs

Так что все, что вам нужно для этого сделать, - это перевернуть порядок аргументов в insert и вызвать foldLeft в вашем методе insertSort.