speak, it ain’t illegal yet

October 27, 2006

Visualizing problems in Erlang

Filed under: erlang, mergesort — diginux @ 7:31 am


Ever since I started learning Erlang almost 10 months ago, I have always just had this deep down unexplainable gut feeling that Erlang is neat. Erlang just feels so right. The flow from idea to implementation in Erlang is so smooth, sometimes I second guess myself, “can it really be this easy?!”

Last night I couldn’t sleep, so naturally I stayed in bed thinking about Erlang, and I think I might have figured out why Erlang is so nice: visualization.

Let’s just take an example. Let’s say I tell you to write Quick Sort in C.

The first thing you would probably do is look up the algorithm which is:

function quicksort(q)
    var list less, pivotList, greater
    if length(q) = 1
        return q
    select a pivot value pivot from q
    for each x in q except the pivot element
        if x
To code the algorithm, you need to start thinking about the implementation details, such as how you will manage the pivot list, what type of values will your quick sort support, etc. It is very difficult to go from the algorithm directly to C, there are too many C things to worry about first.
void quickSort(int numbers[], int array_size)
{
 q_sort(numbers, 0, array_size - 1);
}
void q_sort(int numbers[], int left, int right)
{
 int pivot, l_hold, r_hold;
 l_hold = left;
 r_hold = right;
 pivot = numbers[left];
 while (left = pivot) && (left  pivot)
   q_sort(numbers, pivot+1, right);
}

Now let’s say I tell you to think about writing a Merge Sort in Erlang. You instantly realize this problem is dead easy using a list a few recursion calls and Erlang’s powerful list operators. There are no memory issues to think about, no type checking to worry about, no extra temporary values to handle, no having to “translate” your programs calls to fit the algorithm. With Erlang you can actually imagine in your head, having a long list of things, doing a few list operations, then using recursion and being done.

sort([Pivot|T]) ->
   sort([ X || X = Pivot]);
sort([]) -> [].

While I admit it takes a functional mindset to get used to seeing things this way, once you do have it, it is an almost instantaneous process of going from algorithm to code. Being able to visualize both the algorithm and the Erlang code together at the same time without much difficulty and implementing them immediately makes programming a lot more enjoyable and fulfilling. Gone are the days of tedious details and mindless translations.

References:
1.http://en.wikipedia.org/wiki/Quicksort
2.http://www.erlang.org/doc/doc-5.4.12/doc/programming_examples/list_comprehensions.html

2 Comments »

  1. hello
    please send me merge sort with erlang language if possible
    thank you

    Comment by dfdsf — March 13, 2008 @ 12:20 pm

  2. lists:sort in erlang uses merge-sort, so there isn’t really a need to write your own, but just in case you can find implements here

    http://en.literateprograms.org/Merge_sort_(Erlang)

    and here(read the first comment)

    http://webjazz.blogspot.com/2007/10/well-once-i-got-started-i-kinda-couldnt.html

    Comment by diginux — March 13, 2008 @ 12:27 pm

RSS feed for comments on this post. TrackBack URI

Leave a comment

Blog at WordPress.com.