Someone asked what was surely a homework question today on StackOverflow about matrix multiplication in Erlang. I set out to answer him in as simple a way as possible, but wound up writing a naive matrix generation and multiplication module.
The code to the module might be of interest to new Erlangers, as it adheres both to the style of zuuid and includes many examples of using a combination of list operations and explicit recursion to cut clutter and make the meaning of otherwise complex operations clear.
Here is the code:
%%% @doc
%%% A naive matrix generation, rotation and multiplication module.
%%% It doesn't concern itself with much checking, so input dimensions must be known
%%% prior to calling any of these functions lest you receive some weird results back,
%%% as most of these functions do not crash on input that go against the rules of
%%% matrix multiplication.
%%%
%%% All functions crash on obviously bad values.
%%% @end
-module(naive_matrix).
-export([random/2, random/3, rotate/1, multiply/2]).
-type matrix() :: [[number()]].
-spec random(Size, MaxValue) -> Matrix
when Size :: pos_integer(),
MaxValue :: pos_integer(),
Matrix :: matrix().
%% @doc
%% Generate a square matrix of dimensions {Size, Size} populated with random
%% integer values inclusive of 1..MaxValue.
random(Size, MaxValue) when Size > 0, MaxValue > 0 ->
random(Size, Size, MaxValue).
-spec random(X, Y, MaxValue) -> Matrix
when X :: pos_integer(),
Y :: pos_integer(),
MaxValue :: pos_integer(),
Matrix :: matrix().
%% @doc
%% Generate a matrix of dimensions {X, Y} populated with random integer values
%% inclusive 1..MaxValue.
random(X, Y, MaxValue) when X > 0, Y > 0, MaxValue > 0 ->
Columns = lists:duplicate(X, []),
Populate = fun(Col) -> row(Y, MaxValue, Col) end,
lists:map(Populate, Columns).
-spec row(Size, MaxValue, Acc) -> NewAcc
when Size :: non_neg_integer(),
MaxValue :: pos_integer(),
Acc :: [pos_integer()],
NewAcc :: [pos_integer()].
%% @private
%% Generate a single row of random integers.
row(0, _, Acc) ->
Acc;
row(Size, MaxValue, Acc) ->
row(Size - 1, MaxValue, [rand:uniform(MaxValue) | Acc]).
-spec rotate(matrix()) -> matrix().
%% @doc
%% Takes a matrix of {X, Y} size and rotates it left, returning a matrix of {Y, X} size.
rotate(Matrix) ->
rotate(Matrix, [], [], []).
-spec rotate(Matrix, Rem, Current, Acc) -> Rotated
when Matrix :: matrix(),
Rem :: [[number()]],
Current :: [number()],
Acc :: matrix(),
Rotated :: matrix().
%% @private
%% Iterates doubly over a matrix, packing the diminished remainder into Rem and
%% packing the current row into Current. This is naive, in that it assumes an
%% even matrix of dimentions {X, Y}, and will return one of dimentions {Y, X}
%% based on the length of the first row, regardless whether the input was actually
%% even.
rotate([[] | _], [], [], Acc) ->
Acc;
rotate([], Rem, Current, Acc) ->
NewRem = lists:reverse(Rem),
NewCurrent = lists:reverse(Current),
rotate(NewRem, [], [], [NewCurrent | Acc]);
rotate([[V | Vs] | Rows], Rem, Current, Acc) ->
rotate(Rows, [Vs | Rem], [V | Current], Acc).
-spec multiply(ValueA, ValueB) -> Product
when ValueA :: number() | matrix(),
ValueB :: number() | matrix(),
Product :: number() | matrix().
%% @doc
%% Accept any legal combination of scalar and matrix values to be multiplied.
%% The correct operation will be chosen based on input values.
multiply(A, B) when is_number(A), is_number(B) ->
A * B;
multiply(A, B) when is_number(A), is_list(B) ->
multiply_scalar(A, B);
multiply(A, B) when is_list(A), is_list(B) ->
multiply_matrix(A, B).
-spec multiply_scalar(A, B) -> Product
when A :: number(),
B :: matrix(),
Product :: matrix().
%% @private
%% Simple scalar multiplication of a matrix.
multiply_scalar(A, B) ->
multiply_scalar(A, B, []).
-spec multiply_scalar(A, B, Acc) -> Product
when A :: number(),
B :: matrix(),
Acc :: matrix(),
Product :: matrix().
%% @private
%% Scalar multiplication is implemented here as an explicit recursion over
%% a list of lists, each element of which is subjected to a map operation.
multiply_scalar(A, [B | Bs], Acc) ->
Row = lists:map(fun(N) -> A * N end, B),
multiply_scalar(A, Bs, [Row | Acc]);
multiply_scalar(_, [], Acc) ->
lists:reverse(Acc).
-spec multiply_matrix(A, B) -> Product
when A :: matrix(),
B :: matrix(),
Product :: matrix().
%% @doc
%% Multiply two matrices together according to the matrix multiplication rules.
%% This function does not check that the inputs are actually proper (regular)
%% matrices, but does check that the input row/column lengths are compatible.
multiply_matrix(A = [R | _], B) when length(R) == length(B) ->
multiply_matrix(A, rotate(B), []).
-spec multiply_matrix(A, B, Acc) -> Product
when A :: matrix(),
B :: matrix(),
Acc :: matrix(),
Product :: matrix().
%% @private
%% Iterate a row multiplication operation of each row of A over matrix B until
%% A is exhausted.
multiply_matrix([A | As], B, Acc) ->
Prod = multiply_row(A, B, []),
multiply_matrix(As, B, [Prod | Acc]);
multiply_matrix([], _, Acc) ->
lists:reverse(Acc).
-spec multiply_row(Row, B, Acc) -> Product
when Row :: [number()],
B :: matrix(),
Acc :: [number()],
Product :: [number()].
%% @private
%% Multiply each row of matrix B by the input Row, returning the list of resulting sums.
multiply_row(Row, [B | Bs], Acc) ->
ZipProd = lists:zipwith(fun(X, Y) -> X * Y end, Row, B),
Sum = lists:sum(ZipProd),
multiply_row(Row, Bs, [Sum | Acc]);
multiply_row(_, [], Acc) ->
Acc.
Hopefully reading that on a blog won’t drive anyone too nuts. I’ll probably include an expanded version of that (or something related) in a convenience library eventually. Unless I forget. Meh.