Functional alternative?

Question

Hi all,

As I continue my quest of learning functional programming, I've come to wonder if there may be alternatives to my default "procedural" way of thinking. To be more specific, I'm looking at a function I wrote. Here is what it does:

Swap two elements of an unordered list of numbers, such that one of the elements  
 is now in the right place
Add the sum of the swapped values to an accumulated total   
Repeat until list is sorted

So, right now I'm using a standard loop* with an accum variable to do the above. It works fine and all, and there's certainly nothing wrong with iteration in real life, but as the point of this exercise is to expand my way of thinking, I'm curious if there is a more functional approach to the above algorithm.

Thanks!

*(Actually recursion, but whatever)

Answer 1

Recursion is basically a functional programming mechanism. I guess you could replace your swap function with a function that took in a list and returned a list or something similarly silly, but that would be a bad idea unless written in a language which was actually functional.

Try implementing mergesort in Oz, SML, Prolog, or Lisp. E.g. something like this pseudocode for merge:

Merge(A,[])=A
Merge(H|T,H2|T2)=iif(H<H2,H|Merge(T,H2|T2),H2|Merge(H|T,T2)

Answer 2

From EigenClass:

The venerable master Leroy was walking with his student. Wishing to start a discussion with his master, the apprentice said "Master, I've heard that all loops must be replaced with tail-recursive functions. Is that true?" Leroy looked commiseratively at his student and replied "Foolish pupil, many tail-recursive functions are merely inefficient loops."

The student spent the next few weeks replacing tail-recursive functions with explicit loops. He finally showed his code to master Leroy, seeking his approval. Leroy hit him with a stick. "When will you learn? Explicit loops are a poor man's tail-recursive functions." At that moment, the student became enlightened.

Edit: Referring to Xavier Leroy, primary developer of OCaml

Since I can't see your function to understand how functional* it is, I don't know. But it seems like what you are doing is correct. My main suggestion would be looking at data structures that lend themselves well to functional programming --but you are using lists, so that's out, although, lists aren't the best data structure in this case. As well as the algorithm. If you are pigeon holed into using the insertion sort, then you might not be able to use merge sort or other more efficient methods.