Lytol - 4 months ago 38

Scala Question

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

Answer

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