[erlang-questions] Bubble sort in Erlang

[andrew cooke]

> Hi all,
>
> I've recently picked up the "Programming Erlang" book and started
> experimenting with Erlang. So I wanted to implement some toy
> algorithms - would you believe me that I was kind of stuck for
> several days on the train while going to work implementing a simple
> bubble sort algorithm? I think FP really hit my head - that's the
> first time I've tried any functional programming. The hardest part
> for me was (and still is) maintaining and mutating the state (like
> whether a swap has occurred). So I thought because I have to use
> recursion instead of iteration, I could maintain the state using
> parameter passing. Here it goes, my first Erlang toy program:
>
> -module(bsort).
> -export([bubble_sort/1, bstage/1, bstage/2]).
>

you can put the call to bstage in the case statement which save you
introducing "Status" (although below i argue you shouldn't be doing this
at all).

> bubble_sort([A,B|Tail]) when Tail =/= [] ->
> 	{Status, List} = bstage([A,B|Tail]),
> 	case Status of
> 		sorted -> List;
> 		not_sorted -> bubble_sort(List)
> 	end;

if you put this before the definition above you won't need to check for an
empty Tail since that case is handled here.  You can also separate out the
if into guard conditions, which I think looks nicer.

> bubble_sort([A,B]) ->
> 	if
> 		A > B -> [B, A];
> 		true -> [A, B]
> 	end;

> bubble_sort([A]) -> [A];
> bubble_sort([]) -> [].

in fact in general it's best to put the simplest definitions at the top -
partly so that you don't have to worry so much about the more complex ones
and also because when reading it's nice to know what the exit conditions
are.


here you seem to be using a flag to indicate that the system is still
bubbling.  i haven't tried to follow what you are doing in detail, but in
general you shouldn't need to do this.  instead, you should simply call
yourself again if you need to.

also, you have some appends in the code (++).  generally that means you
should be passing around an accumulator list instead.

> bstage(L) ->
> 	{Swapped, List} = bstage(L, false),
> 	case Swapped of
> 		false -> {sorted, List};
> 		true -> {not_sorted, List}
> 	end.
>
> bstage([A,B|Tail], Swapped) when Tail =/= [] ->
> 	if
> 		A > B -> {_, List1} = bstage([A|Tail], true),
> 				{true, [B] ++ List1};
> 		true -> {Swap, List} = bstage([B|Tail], Swapped),
> 				{Swap, [A] ++ List}
> 	end;

if you put my two comments above together, you may find that the function
below can, because it receives a list it is accumulating on, pass "the
whole list" to bubble_sort directly, rather that returning "true" and
leaving that task to the higher levels.

remember that with tail recursion there's no problem repeatedly calling
functions.

> bstage([A,B], Swapped) ->
> 	if
> 		A > B -> {true, [B,A]};
> 		true -> {Swapped, [A,B]}
> 	end.

i don't know if this helps or if it's too vague/abstract.  sorry i don't
have more time to understand in detail, but i hope the comments above
explain the kind of "gut reactions" that i would follow in trying to
rewrite this cleanly (ie without the flag that indicates that the function
needs to be called again).

you're getting there and i think this is the right way to learn.  keep
going :o)

andrew

ps i feel a bit embarrassed giving advice - i am not the worlds greatest
functional programmer.  so if someone contradicts me they are probably
right.


>
> Any comments are greatly appreciated.
>
> Kind regards,
> Milen
>
>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions
>
>