Chewing The Cud

Using the 99 Lisp Problems as a guide, I have been writing the problems in Erlang to grow more comfortable with the non-concurrent aspects of the language. Once completed, the goal is then to add in some concurrency exercises to round out the Erlang experience. I have to say, to this point, I feel I’m beginning to grok the ole Erlang list-handling / pattern-matching capabilities.

<update date=”December 22nd, 2006″> Reading the Erlang efficiency guide I found out that appending lists is not the greatest way to do list creation, so I rewrote the applicable exercises with the suggestion of simply reversing the list at the end.</update>
Here, then, are my solutions to the first ten problems:

%% Find the last box of a list.

%% Example: (my-last ‘(a b c d)) -> (D)
p01(L) when length(L) =< 1 -> L;
p01([_ | L]) -> p01(L).

%% Find the last but one box of a list.
%% Example: (my-but-last ‘(a b c d)) -> (C D)
p02(L) when length(L) =< 2 -> L;
p02([_ | L]) -> p02(L).

%% Find the K’th element of a list. The first element in the list is number 1.
%% Example: (element-at ‘(a b c d e) 3) -> C
p03([], _) -> [];
p03(_, Pos) when Pos < 1 -> bad_pos;
p03([H | _], 1) -> H;
p03([_ | L], Pos) -> p03(L, Pos-1).

%% Find the number of elements of a list.
p04([]) -> 0;
p04(L) -> p04count(L, 0).

p04count([], C) -> C;
p04count([_ | L], C) -> p04count(L, C+1).

%% Reverse a list.
p05([]) -> [];
p05(L) -> p05reverse(L, []).

p05reverse([], RevL) -> RevL;
p05reverse([H | L], RevL) -> p05reverse(L, [H | RevL]).

%% Find out whether a list is a palindrome. A palindrome can be read forward or backward; e.g. (x a m a x).
p06([]) -> true;
p06(L) when length(L) == 1 -> true;
p06(L) -> L == p05(L).

%% Flatten a nested list structure. Transform a list, possibly holding lists as elements into a `flat’ list by replacing each list with its elements (recursively).
%% Example: (my-flatten ‘(a (b (c d) e))) -> (A B C D E)
%% Hint: Use the predefined functions list and append.
p07([]) -> [];
p07(L) when not is_list(L) -> [L];
p07([H | L]) ->
Head = p07(H),
Tail = p07(L),
Head ++ Tail.

%% Eliminate consecutive duplicates of list elements.
%% If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed.
%% Example: (compress ‘(a a a a b c c a a d e e e e)) -> (A B C A D E)
p08([]) -> [];
p08([H | L]) -> p08compress(L, H, [H]).

p08compress([], _Curr, Compressed) -> lists:reverse(Compressed);
p08compress([H | L], Curr, Compressed) ->
case Curr of
H -> p08compress(L, Curr, Compressed);
_Else -> p08compress(L, H, [H | Compressed])
end.

%% Pack consecutive duplicates of list elements into sublists. If a list contains repeated elements they should be placed in separate sublists.
%% Example: (pack ‘(a a a a b c c a a d e e e e)) -> ((A A A A) (B) (C C) (A A) (D) (E E E E))
p09([]) -> [];
p09([H | L]) -> p09pack(L, H, [H], []).

p09pack([], _Curr, SubL, Packed) -> lists:reverse([SubL | Packed]);
p09pack([H | L], Curr, SubL, Packed) ->
case Curr of
H -> p09pack(L, Curr, [H | SubL], Packed);
_Else -> p09pack(L, H, [H], [SubL | Packed])
end.

%% Run-length encoding of a list.
%% Use the result of problem P09 to implement the so-called run-length encoding data compression method.
%% Consecutive duplicates of elements are encoded as lists (N E) where N is the number of duplicates of the element E.
%% Example: (encode ‘(a a a a b c c a a d e e e e)) -> ((4 A) (1 B) (2 C) (2 A) (1 D)(4 E))
p10([]) -> [];
p10(L) -> p10encode(p09(L), []).

p10encode([], Encoded) -> lists:reverse(Encoded);
p10encode([[Elem | SubL] | L], Encoded) -> p10encode(L, [[length(SubL)+1, Elem] | Encoded]).

Those who grok Erlang and happen to find this blog, please feel free to offer criticism of my implementations.

This entry was posted on Wednesday, December 13th, 2006 at 12:30 pm and is filed under Fun, Geekdom, Research. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.