Skip to content

Instantly share code, notes, and snippets.

@developedby

developedby/matmul.bend

Last active July 11, 2024 11:19
Show Gist options
  • Save developedby/6a6632e344b30d7fada5acc1c1c66c43 to your computer and use it in GitHub Desktop.
Save developedby/6a6632e344b30d7fada5acc1c1c66c43 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
matmul.bend
########################################
# Authors:
# - Arthur M Passos, 2024 (original implementation)
# - Nicolas Abril, 2024 (n³ implementation)
########################################
# Matrix Multiplication using Bend's default recursive Lists type;
#
# Matrices are encoded as a List of Lists of Numbers.
# Multiplication is calculated as the row dot products of
# the first matrix with the transpose of the second matrix.
########################################
############## List utils ##############
def List/len(l):
def go(l, len, acc):
match l:
case List/Nil:
return (len, DiffList/to_list(acc))
case List/Cons:
return go(l.tail, len + 1, DiffList/append(acc, l.head))
return go(l, 0, DiffList/new)
def List/to_dot_product( la, lb ):
match la:
case List/Nil:
return 0
case List/Cons:
match lb:
case List/Nil:
return 0
case List/Cons:
return (la.head * lb.head) + List/to_dot_product(la.tail, lb.tail)
# DiffList/new() -> (List(T) -> List(T))
# Create a new difference list
DiffList/new = λx x
# DiffList/append(diff: List(T) -> List(T), val: T) -> (List(T) -> List(T))
# Append a value to the end of the difference list
DiffList/append diff val = λx (diff (List/Cons val x))
# DiffList/cons(diff: List(T) -> List(T), val: T) -> (List(T) -> List(T))
# Append a value to the beginning of the difference list
DiffList/cons diff val = λx (List/Cons val (diff x))
# DiffList/to_list(diff: List(T) -> List(T)) -> (List(T))
# Convert a difference list to a list
DiffList/to_list diff = (diff List/Nil)
##########################################
############## Matrix utils ##############
def Matrix/shape(matrix):
match matrix:
case List/Nil:
return ((0, 0), List/Nil)
case List/List/Cons:
(n_rows, matrix.tail) = List/len(matrix.tail)
n_rows = n_rows + 1
(n_cols, matrix.head) = List/len(matrix.head)
return ((n_rows, n_cols), List/Cons(matrix.head, matrix.tail))
##########################################
############## Transposing ###############
def Matrix/to_transpose(matrix):
match matrix:
case List/Nil:
# No more rows
return List/Nil
case List/Cons:
match matrix.head:
case List/Nil:
# No more columns
return List/Nil
case List/Cons:
matrix.head = List/Cons(matrix.head.head, matrix.head.tail)
matrix = List/Cons(matrix.head, matrix.tail)
(first_col, matrix) = Matrix/split_first_col(matrix)
return List/Cons(first_col, Matrix/to_transpose(matrix))
# Matrix/split_first_col(matrix: List(List(Number(t)))) -> (List(Number(t)), List(List(Number(t))))
# Returns the first column of the matrix as a list and the rest of the matrix without the first column
def Matrix/split_first_col(matrix):
def go(matrix, col_acc, mat_acc):
match matrix:
case List/Nil:
return (DiffList/to_list(col_acc), DiffList/to_list(mat_acc))
case List/Cons:
match matrix.head:
case List/Nil:
return (DiffList/to_list(col_acc), DiffList/to_list(mat_acc))
case List/Cons:
col_acc = DiffList/append(col_acc, matrix.head.head)
mat_acc = DiffList/append(mat_acc, matrix.head.tail)
return go(matrix.tail, col_acc, mat_acc)
return go(matrix, DiffList/new, DiffList/new)
def Matrix/to_mat_mul(mat_a, mat_b):
def mul_transpose(mat_a, mat_b_t):
match mat_a:
case List/Nil:
return List/Nil
case List/Cons:
match mat_b_t:
case List/Nil:
return List/Nil
case List/Cons:
row = Matrix/to_vec_mat_mul(mat_a.head, mat_b_t)
return List/Cons(row, mul_transpose(mat_a.tail, mat_b_t))
mat_b_t = Matrix/to_transpose(mat_b)
((a_rows, a_cols), mat_a) = Matrix/shape(mat_a)
((b_rows, b_cols), mat_b_t) = Matrix/shape(mat_b_t)
if (a_cols != b_rows):
return "ERROR: Wrong matrices size:"
else:
return mul_transpose(mat_a, mat_b_t)
# Multiplies a row vector by a matrix
def Matrix/to_vec_mat_mul(vector, matrix):
match matrix:
case List/Nil:
return List/Nil
case List/Cons:
dot = List/to_dot_product(vector, matrix.head)
return List/Cons(dot, Matrix/to_vec_mat_mul(vector, matrix.tail))
def main:
matrixA = [
[1, 2, 3],
[4, 5, 6]
]
matrixB = [
[7, 8],
[9, 10],
[11, 12]
]
# matrixA * matrixB = [[58, 64], [139, 154]]
matrixC = [
[12, 7, 3],
[4, 5, 6],
[7, 8, 9]
]
matrixD = [
[5, 8, 1],
[6, 7, 3],
[4, 5, 9]
]
# matrixC * matrixD =
# [[114, 160, 60],
# [74, 97, 73],
# [119, 157, 112]]
matrixE = [
[1, 2, 3],
[3, 4, 5],
[7, 6, 4],
[1, 2, 3],
[3, 4, 5],
[7, 6, 4],
[1, 2, 3],
[3, 4, 5],
[1, 2, 3],
[3, 4, 5],
[7, 6, 4],
[1, 2, 3],
[3, 4, 5],
[7, 6, 4],
[1, 2, 3],
[3, 4, 5],
[1, 2, 3],
[3, 4, 5],
[7, 6, 4],
[1, 2, 3],
[3, 4, 5],
[7, 6, 4],
[1, 2, 3],
[3, 4, 5],
[1, 2, 3],
[3, 4, 5],
[7, 6, 4],
[1, 2, 3],
[3, 4, 5],
[7, 6, 4],
[1, 2, 3],
[3, 4, 5],
]
matrixF = [
[5, 2, 6],
[5, 6, 7],
[7, 6, 4]
]
# matrixE * matrixF =
# [[36, 32, 32],
# [70, 60, 66],
# [93, 74, 100],
# [36, 32, 32],
# [70, 60, 66],
# [93, 74, 100],
# [36, 32, 32],
# [70, 60, 66],
# [36, 32, 32],
# [70, 60, 66],
# [93, 74, 100],
# [36, 32, 32],
# [70, 60, 66],
# [93, 74, 100],
# [36, 32, 32],
# [70, 60, 66],
# [36, 32, 32],
# [70, 60, 66],
# [93, 74, 100],
# [36, 32, 32],
# [70, 60, 66],
# [93, 74, 100],
# [36, 32, 32],
# [70, 60, 66],
# [36, 32, 32],
# [70, 60, 66],
# [93, 74, 100],
# [36, 32, 32],
# [70, 60, 66],
# [93, 74, 100],
# [36, 32, 32],
# [70, 60, 66]]
return Matrix/to_mat_mul(matrixE, matrixF)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment