Thursday, October 04, 2007

Bubblesort in Erlang

It's amazing how if a language isn't a part of your daily work, how rusty you get at it. Oh erlang, how I didn't mean to neglect you! I finally convinced Ian to give Erlang a shot, and he's been going through Joe Armstrong's book. He decided to write bubblesort, and it took him hours. This is what he had to say:
I'm having some difficulty
getting used to the idea of a language where every variable is a const.
its interesting, though.

but I have to admit the one line erlang quicksort is one of the
prettiest code snippits I've ever seen.

but "=:=" for equivalence? a three character long operator? who do
they think they are?

I wrote bubble sort and merge sort in erlang last night. it took
hours. the code looks horrible. for the first time since learning
basic in high school I feel like a foreigner in a strange land. its
invigorating.

actually I find it a bit intimidating. when something takes more than a
few lines of code I wonder if I'm doing it wrong. if joe armstrong ever
saw my bubble sort he'd probably take my book away.
I decided to give it a shot. It's certainly a far better exercise than FizzBuzz. Given that I had written a neural network in erlang before, I figured I'd be more than ok with bubblesort. Right?

Wrong.

It's taken an embarrassingly long time to get it right, plus, I took a shortcut that isn't very optimal. If I ever had to write this in an interview in Erlang, They'd take my keyboard away. Here's what I came up with:
-module(bubblesort).
-export([sort/1]).

sort([First | Rest]) ->
sort_helper([First | Rest], swap(First, Rest)).

sort_helper(List, New_list) when List =:= New_list ->
List;
sort_helper(List, [First | Rest]) ->
sort_helper([First | Rest], swap(First, Rest)).

swap(Current, []) ->
[Current];
swap(Current, [First | Rest]) when Current =< First ->
[Current] ++ swap(First, Rest);
swap(Current, [First | Rest]) ->
[First] ++ swap(Current, Rest).

Notice that I use the guard "List =:= New_list" to determine if a swap took place. In a large list, this would add n comparisons on every pass. Horrible. But since it's an exercise, I neglected to keep track of swaps.

More than half the time was wrestling with the syntax. I had forgotten a lot of it, and mixed up [First, Rest] with [First | Rest], and I kept forgetting that I needed to prefix the functions by their module names. It's bubblesort:swap(...) when you want to call it, and I was scratching my head for 10 mins. But the other time was just thinking recursively. Unless you're working in a language the heavily uses recursive to iteration, you don't often use it. But defn I prefer recursive as it's much more succinct. Can anyone come up with a one-liner Bubblesort?

For reference, "the one liner" quicksort Ian was talking about:
qsort([]) -> 
[];
qsort([Pivot | T]) ->
qsort([X || X <- T, X < Pivot]) ++ [Pivot] ++ qsort([X || X <- T, X >= Pivot]).

4 comments:

  1. Alright, you captured by Friday lunch time attention. ;) After whipping out a few uglier versions, I finally came up with this:

    -module(bubble).
    -export([sort/1]).

    sort(List) ->
    case lists:foldl(fun(A, {_, []}) -> {noswap, [A]};
    (A, {_, [B|R]}) when A < B -> {swap, [B,A|R]};
    (A, {S, R}) -> {S, [A|R]}
    end, {noswap, []}, List) of
    {swap, New} ->
    sort(lists:reverse(New));
    {noswap, _} ->
    List
    end.

    (Blech - what's the best way to post code in a Blogger comment?)

    Get back into Erlang! It's good for you! ;)

    ReplyDelete
  2. for the first time since learning
    basic in high school I feel like a foreigner in a strange land. its
    invigorating.


    I totally agree with Ian.

    Your blog entry prompted me to blog on the topic of coding style in Erlang: http://curious-attempt-bunny.blogspot.com/2007/10/coding-style-in-erlang.html

    One thing to note:

    sort([First | Rest]) ->
    sort_helper([First | Rest], swap(First, Rest)).

    This involves Erlang rebuilding the list. In the case you don't need First and Rest but you can do this:

    sort([First | Rest] = List) ->
    sort_helper(List, swap(List)).

    ReplyDelete
  3. sort(X) ->
    sort(X, s(X)).

    sort(X,X) -> X;
    sort(_,Y) -> sort(Y, s(Y)).

    s([X,Y|L]) when X>=Y -> [X|s([Y|L])];
    s([X,Y|L]) when X<Y -> [Y|s([X|L])];
    s(L) -> L.

    ReplyDelete
  4. took me an few hours to implement while i was studying erlang

    bubble_sort(L) ->
    if
    length(L) > 1 ->
    SL=bubble_sort_p(L),
    bubble_sort(lists:sublist(SL,1,length(SL)-1)) ++ [lists:last(SL)];
    true -> L
    end.

    bubble_sort_p([]) -> [];
    bubble_sort_p([F | R]) ->
    case length(R) > 0 of
    true -> case F > hd(R) of
    true -> [hd(R)] ++ bubble_sort_p([F|tl(R)]);
    false -> [F] ++ bubble_sort_p([hd(R)|tl(R)])
    end;
    false -> [F]
    end.


    I think I start to like Erlang but I need to start thinking differently

    ReplyDelete