選択ソート - 再帰を伴う機能的スタイル

Question

Scalaの学習を始めたばかりで、Functional Programmingを掘り下げようとしています。私はSelection Sort Functionalスタイルの記事の多くを見てきました。与えられたすべての解決策を完全に理解することはできませんでした。私のScalaのスキルはまだNascentです。

私は末尾再帰を使用してScalaコードを書いており、そのスタイルに関するフィードバックをいただければ幸いです。 Functional Programmingのように見えますか？これを改善したり、より機能的にする方法はありますか？

import scala.annotation.tailrec 

object FuncSelectionSort { 
/** 
* Selection Sort - Trying Functional Style 
*/ 
def sort(a: Array[Int]) = { 

    val b: Array[Int] = new Array[Int](a.size) 
    Array.copy(a, 0, b, 0, a.size) 

    // Function to swap elements 
    def exchange(i: Int, j: Int): Unit = { 
     val k = b(i); 
     b(i) = b(j); 
     b(j) = k; 
    } 

    @tailrec 
    def helper(b: Array[Int], n: Int): Array[Int] = { 
     if (n == b.length-1) return b 
     else { 
      val head = b(n); 
      val minimumInTail = b.slice(n, b.length).min; 

      if (head > minimumInTail) { 
       val minimumInTailIndex = b.slice(n, b.length).indexOf(minimumInTail); 
       exchange(n, minimumInTailIndex + n); 
      } 

      helper(b, n + 1) 
     } 
    } 
    helper(b, 0) 
    } 
} 

私が採用しようとしているロジックはかなり単純です。配列の最初のインデックスから始め、残りの配列の最小値を求めます。しかし、次の再帰のためにArray.tai​​lを渡すのではなく、私は完全な配列を渡し、各スライスが前の再帰スライスよりも小さいスライスをチェックします。

例えば、 場合、配列（10、4、6、9、3、5） 最初のパス - >ヘッド= 10、スライス= 4,6,9,3,5 最初のパス - >ヘッド= 4、slice = 6,9,3,5

私は尾を通過するのと同じように感じますが、同じ方法でスライスして見たいと思っていました。

あなたのお手伝いをお待ちしております。

Answer 1

作業コードの詳細については、codereviewを参照してください。しかし、私は1つのことを言うことができます：つまり、インプレースソート配列自体は、関数型プログラミングの良い例ではありません。これは、私達がデータの再帰とうまく適合しないため、私たちは純粋主義者が好きではないからです。特に再帰や変異の混合は本当に良いスタイルではありません。

完全な元の配列をコピーし、通常の命令コード（ループとインプレーススワップ）で実装されたインプレース選択ソートを使用することです。関数にカプセル化されていれば、これは外部に対して純粋です。このパターンは、標準ライブラリでよく使用されます。 cf. List.scala。

他の変異体、および不変のプログラミングを学ぶためにおそらくより有益には、連結リストの上に不変の再帰的なアルゴリズムを使用することです：プログラミングのそのスタイルから

def sorted(a: List[Int]): List[Int] = a match { 
    case Nil => Nil 
    case xs => xs.min :: sorted(xs.diff(List(xs.min))) 
} 

、あなたは、機能的な考え方について多くを学びます（ただし、効率を脇に置いておく）。エクササイズ：そのコードを末尾再帰に変換します。

（実際には、挿入するソートはすべてのステップで「削除」する必要がなく、ソートされたリンクリストを構築できるので、このパターンでうまく機能します;実装することもできます）。