在功能Scala中进行选择排序 [英] Selection sort in functional Scala

问题描述

我正在编写Scala编程，并编写了选择排序算法的快速实现。然而，由于我在函数式编程中仍然有点绿，所以我很难转化为更加斯卡拉式的风格。对于那里的Scala程序员来说，我该如何使用Lists和val来做到这一点，而不是回到我的命令式的方式中去？

http://gist.github.com/225870

解决方案

正如 starblue已经说过的，您需要一个功能计算列表的最小值并返回删除了该元素的列表。这里是我的尾递归实现类似的东西（因为我相信 foldl 是标准库中的尾递归），并且我试图尽可能地使其功能化:)。它返回一个列表，其中包含原始列表中的所有元素（但反过来 - 请参阅下面的解释），以最小值作为首字母。

  def minimum（xs：List [Int]）：List [Int] = 
（List（xs.head）/：xs.tail）{
（ys，x）=> 
 if（x  else（ys.head :: x :: ys.tail）
} 
  
 $ b 
这基本上做了一个折叠，从包含 xs 如果 xs 的第一个元素小于该列表的头部，我们会将它加入列表 ys 。否则，我们将它添加到列表 ys 作为第二个元素。等递归，我们已经将我们的列表折叠到一个新列表中，该列表包含最小元素作为头部和包含 xs 的所有元素的列表（不一定在相同的顺序），最小删除，作为尾巴。注意这个函数不会删除重复项。
 
 
 
创建这个帮助函数后，现在可以很容易地实现选择排序。
  def selectionSort（xs：List [Int]）：List [Int] = 
 if（xs.isEmpty）List（）
 else {$ b $如果（ys.tail.isEmpty）
 ys 
 else 
 ys.head :: selectionSort（ys.tail）
}，则b val ys = minimum（xs）
} 
  
不幸的是，这个实现是不是尾递归，所以它会炸掉大列表的堆栈。无论如何，你不应该对大型列表使用O（n ^ 2）排序，但仍然...如果实现是尾递归的，那将是很好的。我会尝试去思考一些事情......我认为它会看起来像实现一个折叠。
 
 
 
 尾递归！ 
 
 
 
为了使其具有尾递归功能，我在函数式编程中使用了相当常见的模式 - 累加器。它有点落后，因为现在我需要一个称为最大值的函数，它基本上与最小值相同，但是与最大元素 - 它的实现尽可能少，但使用> 而不是< 。
  def selectionSort（xs：List [Int]）= {
 def selectionSortHelper（xs：List [Int]，accumulator：List如果（xs.isEmpty）累加器
 else {
 val ys =最大（xs）
 selectionSortHelper（ys.tail，ys。），则列表[Int] = 
。 head :: accumulator）
} 
 
 selectionSortHelper（xs，Nil）
} 
  
 编辑：更改了答案，将辅助函数作为选择排序函数的子函数。 
 
 
它基本上将最大值累加到一个列表中，最终返回列表作为基本情况。您还可以通过用 throw new NullPointerException 替换 accumulator 来查看尾递归，然后检查堆栈跟踪。  
 
 
以下是使用累加器逐步分类的步骤。左边显示 xs 列表，右边显示 accumulator 。 
 
 
  64 * 25 12 22 11 -------无
 11 22 12 25 * ------- 64 
 22 * 12 11 ------- 25 64 
 11 12 * ------- 22 25 64 
 11 * ------- 12 22 25 64 
无------- 11 12 22 25 64 
  
以下显示一步一步折叠来计算最大值： 
 
 
 最大（25 12 64 22 11）
 
 25 ::无/：12 64 22 11  -  25> 12，所以它保持为
 25 :: 12 /：64 22 11  - 与上述相同
 64 :: 25 12 /：22 11  -  25< 64，所以新头是64 
 64 :: 22 25 12 /：11  - 并保持这样
 64 :: 11 22 25 12 /：无 - 直到最后
 
 64 11 22 25 12 
  
 
I'm making my way through "Programming in Scala" and wrote a quick implementation of the selection sort algorithm. However, since I'm still a bit green in functional programming, I'm having trouble translating to a more Scala-ish style. For the Scala programmers out there, how can I do this using Lists and vals rather than falling back into my imperative ways?


http://gist.github.com/225870
解决方案
As starblue already said, you need a function that calculates the minimum of a list and returns the list with that element removed. Here is my tail recursive implementation of something similar (as I believe foldl is tail recursive in the standard library), and I tried to make it as functional as possible :). It returns a list that contains all the elements of the original list (but kindof reversed - see the explanation below) with the minimum as a head.
def minimum(xs: List[Int]): List[Int] =
  (List(xs.head) /: xs.tail) {
    (ys, x) =>
      if(x < ys.head) (x :: ys)
      else            (ys.head :: x :: ys.tail)
  }
This basically does a fold, starting with a list containing of the first element of xs If the first element of xs is smaller than the head of that list, we pre-append it to the list ys. Otherwise, we add it to the list ys as the second element. And so on recursively, we've folded our list into a new list containing the minimum element as a head and a list containing all the elements of xs (not necessarily in the same order) with the minimum removed, as a tail. Note that this function does not remove duplicates.

After creating this helper function, it's now easy to implement selection sort.
def selectionSort(xs: List[Int]): List[Int] =  
  if(xs.isEmpty) List()
  else {
    val ys = minimum(xs)
    if(ys.tail.isEmpty) 
      ys
    else
      ys.head :: selectionSort(ys.tail)
  }
Unfortunately this implementation is not tail recursive, so it will blow up the stack for large lists. Anyway, you shouldn't use a O(n^2) sort for large lists, but still... it would be nice if the implementation was tail recursive. I'll try to think of something... I think it will look like the implementation of a fold.

Tail Recursive!

To make it tail recursive, I use quite a common pattern in functional programming - an accumulator. It works a bit backward, as now I need a function called maximum, which basically does the same as minimum, but with the maximum element - its implementation is exact as minimum, but using > instead of <.
def selectionSort(xs: List[Int]) = {
  def selectionSortHelper(xs: List[Int], accumulator: List[Int]): List[Int] =
    if(xs.isEmpty) accumulator
    else {
          val ys = maximum(xs)
          selectionSortHelper(ys.tail, ys.head :: accumulator)
    }

  selectionSortHelper(xs, Nil) 
  }
EDIT: Changed the answer to have the helper function as a subfunction of the selection sort function.

It basically accumulates the maxima to a list, which it eventually returns as the base case. You can also see that it is tail recursive by replacing accumulator by throw new NullPointerException - and then inspect the stack trace.

Here's a step by step sorting using an accumulator. The left hand side shows the list xs while the right hand side shows the accumulator. The maximum is indicated at each step by a star.
64* 25 12 22 11  ------- Nil
11 22 12 25*     ------- 64
22* 12 11        ------- 25 64
11 12*           ------- 22 25 64
11*              ------- 12 22 25 64
Nil              ------- 11 12 22 25 64
The following shows a step by step folding to calculate the maximum:
maximum(25 12 64 22 11)

25 :: Nil         /: 12 64 22 11  -- 25 > 12, so it stays as head
25 :: 12          /: 64 22 11     -- same as above
64 :: 25 12       /: 22 11        -- 25 < 64, so the new head is 64
64 :: 22 25 12    /: 11           -- and stays so
64 :: 11 22 25 12 /: Nil          -- until the end

64 11 22 25 12


                        
这篇关于在功能Scala中进行选择排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！