"I have a mind like a steel... uh... thingy." Patrick Logan's weblog.

Search This Blog

Loading...

Saturday, September 08, 2007

Morse Codes in Erlang

The portland erlang group is considering some of the ruby quizzes to dive into erlang. If you're not used to programming recursively, you'll probably want to start with simpler problems like implementing the member function, factorial, or count to determine the number of occurrences of some element in a list. When those are comfortable, then the ruby quizzes might be a good challenge.

Here's a sequential, recursive solution in erlang to ruby quiz #121: morse code. It's not *tail* recursive so it could maybe blow out some stack given a really long morse code word. (I assume morse code is translated one word at a time, with spaces between words.)

A tail recursive implementation... hmm... would be a bit more complicated. The two "stacks" are the dots and dashes yet to be decoded and the codes to be considered with each undecoded substring. So one way would be to manage the stacks explicitly in one recursive "loop". Another way would be to use continuation passing style.

Here's (I think) a fairly straight-forward recursive style, morse.erl...

-module(morse).
-export([codes/0, decode/1]).

-import(lists, [prefix/2, reverse/1]).
-import(string, [len/1, substr/2]).

%% http://www.rubyquiz.com/quiz121.html
%%
%% decode/1 when given a string of dots and dashes returns a list of
%% all possible decodings using morse code.
%%
%% Examples:
%%
%% morse:decode(".-").
%% ["ET","A"]
%%
%% lists:member("SOFIA", morse:decode("...---..-....-")).
%% true
%%
%% lists:member("SOPHIA", morse:decode("...---..-....-")).
%% false
%%
%% lists:member("EUGENIA", morse:decode("...---..-....-")).
%% true
%%
%% length(morse:decode("...---..-....-")).
%% 5104

codes() -> 
  [{$A, ".-"},   {$B, "-..."}, {$C, "-.-."}, {$D, "-.."},  {$E, "."}, 
   {$F, "..-."}, {$G, "--."},  {$H, "...."}, {$I, ".."},   {$J, ".---"}, 
   {$K, "-.-"},  {$L, ".-.."}, {$M, "--"},   {$N, "-."},   {$O, "---"}, 
   {$P, ".--."}, {$Q, "--.-"}, {$R, ".-."},  {$S, "..."},  {$T, "-"}, 
   {$U, "..-"},  {$V, "...-"}, {$W, ".--"},  {$X, "-..-"}, {$Y, "-.--"}, 
   {$Z, "--.."}].

decode("") ->
  [];
decode(String) when is_list(String) ->
  decode(String, "", [], codes()).

decode("", "", Results, _Codes) ->
  Results;
decode("", PartialDecoding, Results, _Codes) ->
  [reverse(PartialDecoding) | Results];
decode(_String, _PartialDecoding, Results, []) ->
  Results;
decode(String, PartialDecoding, Results, [{Char, Code} | Rest]) ->
  MoreResults =
    case prefix(Code, String) of
      true ->
        decode(substr(String, 1 + len(Code)), [Char | PartialDecoding], Results, codes());
      false ->
        Results
    end,
  decode(String, PartialDecoding, MoreResults, Rest).

4 comments:

Merlyn Albery-Speyer said...

Interesting! I wish I'd known of the lists:prefix method - that would have made life easier for me. For some reason I didn't think you could do f(g()) in Erlang. I've been writing X = g(), f(X). The -import syntax is handy too.

Michael Watkins said...

"All possible decodings"

That's the assumption which is incorrect. Properly transmitted morse code has an inter-character "space" which prevents, operator (or computerized sender) willing, two characters from being interpreted as a third, i.e.

. + .. != ...

de VE7WV

Patrick Logan said...

"For some reason I didn't think you could do f(g()) in Erlang."

The one place, oddly, that function calls do not work at all is the "if" expression. That uses "guards" which cannot be function calls. So...

B = function_returning_boolean(Foo),
if
B ->
do_something_true();
true ->
do_something_false()
end.

I don't like that so much, which is why I used the "case" expression in the morse code example.

Patrick Logan said...

'Properly transmitted morse code has an inter-character "space"'

Yeah, but that's no fun. :-)

Blog Archive

About Me

Portland, Oregon, United States
I'm usually writing from my favorite location on the planet, the pacific northwest of the u.s. I write for myself only and unless otherwise specified my posts here should not be taken as representing an official position of my employer. Contact me at my gee mail account, username patrickdlogan.