mergesort([Last]) ->
[Last];
mergesort(List) ->
[Left, Right] = split(List, [], []),
io:format("~w ~w~n", [Left, Right]),
merge(mergesort(Left), mergesort(Right)).
split([Last], Acc1, Acc2)->
[ [Last | Acc1], Acc2 ];
split([First | Rest], Acc1, Acc2) when length(Acc1) <>
split(Rest, [First | Acc1], Acc2);
split([First | Rest], Acc1, Acc2) ->
split(Rest, Acc1, [First | Acc2]).
merge([], R) ->
R;
merge(L, []) ->
L;
merge([L_h | L_t], [R_h | R_t]) when R_h =<>
[R_h | merge([L_h | L_t], R_t)];
merge([L_h | L_t], [R_h | R_t]) ->
[L_h | merge(L_t, [R_h | R_t])].
Ugh. I thought mergesort would be my redemption, since in my mind, it looked shorter. But I ended up having to write split(), since I didn't know the libraries well enough, and couldn't think of a good list comprehension to split the list. Admittingly, it's like deciding to forgo inventing the combustible engine and deciding to start walking--I just built it out what I little I knew. If you're so inclined, you can also try one-liner-ing (also not a word) mergesort, as the bar I set was pretty low. :( Like Bryan says:
"Get back into Erlang! it's good for you. ;)"
Speaking of Bryan, he posted a solution to bubblesort that was pretty good in the last post. It was a good lesson. Like anything worthwhile learning, languages are often easy enough to pick up, but hard to master. This was a good wakeup call to go through the examples in the book and master more Erlang before trying to write anything else on my own.
Your example provides a good review of walking through and selecting elements in lists, but since you are working with lists, you really should be looking at the lists module documentation. Both split and merge are provided. It almost makes it feel like cheating:
ReplyDelete-module(merge).
-export([sort/1]).
sort(List) ->
case length(List) of
N when N > 1 ->
{A,B} = lists:split(N div 2, List),
lists:merge(sort(A), sort(B));
_ ->
List
end.
Keep hacking!
Yeah, I figured there'd be stuff in there that would make it feel like cheating. :) Good show. I did rather like the bubblesort.
ReplyDeleteI know I asked for one-liners, but is there a reason against using case statements? I've usually avoided them since my experience in C have seen people abuse them by putting overly complex code in huge case statements.
Is there any such practice against overuse of case statements in Erlang that you know of?
Well, I wouldn't call myself deeply familar with lots of other people's Erlang code. But, from what I've seen, there's not so much of a ban on "case" as there is a strong dicouragement of case nesting. That can get as messy in Erlang as any other language.
ReplyDeleteI usually use a case when there's some value I want to memoize. For example, my code about could have been:
sort(List) when length(List) > 1 ->
{A,B} = lists:split(length(List) div 2, List),
lists:merge(sort(A), sort(B));
sort(List) ->
List.
It's even shorter this way, but I didn't like the look of computing length(List) twice.