How to multiply lists of lists together in Erlang?

Question

I am trying to multiple two matrices together, and I have code that makes the matrices and displays them using a list of lists. But I cannot figure out how to multiply the two matrices I have together.

Here is my code so far:

-module(main).
-export([main/0]).
-export([matrix/2, random/2]).

main() ->
    MatrixA = random(3, 100),
    MatrixB = random(3, 100),

    main:matrix(MatrixA, MatrixB).

matrix(MatrixA, MatrixB) ->

    Print = fun(X) -> io:format("~w, ", [X]) end,

    io:fwrite("Matrix A: "),
    lists:foreach(Print, MatrixA),
    io:fwrite("\n\nMatrix B: "),
    lists:foreach(Print, MatrixB),
    io:fwrite("\n\nMatrix C: "),
    io:fwrite("\n").

random(Size, MaxValue) ->
    random(1, 1, Size, MaxValue, [], []).

-define(VALUE(X, Y), value(X, Y, MaxValue)).

value(_, _, MaxValue) ->
    rand:uniform(MaxValue).

random(Size, Size, Size, MaxValue, Row, Acc) ->
    [[?VALUE(Size, Size) | Row] | Acc];

random(Size, Y, Size, MaxValue, Row, Acc) ->
    random(1, Y+1, Size, MaxValue, [], [[?VALUE(Size, Y) | Row] | Acc]);

random(X, Y, Size, MaxValue, Row, Acc) ->
    random(X+1, Y, Size, MaxValue, [?VALUE(X, Y) | Row], Acc).

Also, is there a way to alter this code so that the numbers in the matrix are decimal values?

Answer 1

NOTE: StackOverflow isn't really the place to tackle homework-type problems, but matrix multiplication is interesting because its listy nature is pretty central to the way we do almost everything in functional programs, so it can be a sort of showcase of different approaches. I think it will be pretty much impossible to submit my code below as homework (especially because it is now indexed on my own site, which is indexed by most schools' plagiarism detectors), but I do think you stand a chance of growing as a programmer if you meditate on this code, and mess around with and modify it to make it your own. And that's good for everyone.

Quick Note on Lists

To simply multiply a list against a list a few different approaches can be used. List comprehensions are pretty common:

multiply(Scalar, Row) ->
    [Scalar * Value || Value <- Row].

Also for multiplying permutations of lists against lists:

multiply(ListA, ListB) ->
    [A * B || A <- ListA, B <- ListB].

This gets you part of the way, but isn't quite what you want. You need to make that go deeper, and there are also actually quite a few rules to matrix multiplication, and if we don't want to write a completely mathematically flawed module we should probably include at least some of the input checks necessary to validate the input or at least crash on obviously bad input.

A Full-blown Example

I initially set out to explain why list operations work the way they do, but I wound up writing a whole naive matrix multiplication module to illustrate the point, so... meh, whatever.

I used list operations where I thought they were really obvious (and colsure of an in-scope value was convenient) and explicit recursion elsewhere (because there is a bit of state floating around in some of these operations, especially rotation).

READ THEM CAREFULLY

Pay particular attention to the way the random/2 and random/3 functions work, and compare them with your code. The version below is much simpler to reason about, and that is a good thing. As much as possible try to not make future readers of your code maintain a bunch of ongoing state in their brain when they read a single line, like having list operations or generators within another list operation -- unless it is a very simple transform that is going on and the statements are more expressive than if they were split apart.

Also, make use of labels that make your code self-documenting whenever possible.

As a final note on style, notice that the style here has typespecs (for Dialyzer -- here's a primer -- learn this), edoc annotations and is written in a way that complies with the style used for zuuid, which is a project written specifically to serve as a platform for discovering sound style and an example of the result.

%%% @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     :: matrix(),
         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.

Note that the above code does not make your matrices as float values. There is an Erlang BIF called float/1 that takes any number and returns a float -- so it is, of course, possible to make the above code do whatever you want in this regard with a minimum of fuss.