PDXErlang intersection implementation w/ Nick

gistfile1.erl

-module(intersection).
-compile(export_all).

intersection(ListA, ListB) ->
  intersection([], ListA, ListB).

intersection(Acc, [], ListB) ->
  Acc;

intersection(Acc, ListA, ListB) ->
  [A|Rest] = ListA,
  Acc1 = case match(A, ListB) of
    true  -> [A|Acc];
    false -> Acc
  end,

  intersection(Acc1, Rest, ListB).


match(X, []) ->
  false;
match(X, [Y|Rest]) when X == Y ->
  true;
match(X, [Y|Rest]) ->
  match(X, Rest).

The above solution isn't perfect. For example, it returns the intersection list in reverse order.

This gist is in relation to the following "ErlangGames" problem presented at the PDXErlang user group:
https://gist.github.com/1937161

A more efficient solution to the problem, w/ an O(n) runtime, might look like:

intersection(ListA, ListB) -> intersection([], ListA, ListB).
intersection(Acc, [A|As], [B|Bs]) when A == B -> intersection([A|Acc], As, Bs);
intersection(Acc, [A|As], [B|Bs]) when A < B  -> intersection(Acc, As, [B|Bs]);
intersection(Acc, [A|As], [B|Bs]) when A > B  -> intersection(Acc, [A|As], Bs);
intersection(Acc, _, _) -> lists:reverse(Acc).

Clever. I like the decomposition. Worth noting that the given lists also have to be sorted.