Questions In Matrix Multiplication

Discussion of Scheme and Racket
Post Reply
sepuku
Posts: 12
Joined: Thu May 12, 2011 11:00 am

Questions In Matrix Multiplication

Post by sepuku » Wed Nov 09, 2011 3:28 pm

Hello there i have managed to multiply matrices with this(as shown at rosetta code):

Code: Select all

(define (matrix-multiply matrix1 matrix2)
   (map
    (lambda (row)
     (apply map
      (lambda column
        (apply + (map * row column)))
       matrix2))
    matrix1))
where my map looks like this:

Code: Select all

;;map: act to a list with a procedure
;;proc ---> lst

(define (map proc lst)
  (if (null? lst)
      '()
      (cons (proc (car lst))
            (map proc (cdr lst)))))
I have tested it and runs great!But i have some questions since i'm still learning:

1)In the first prodecure(line 6) we call as "map * row column" but my map is like (map proc lst).In line 6 there is one more argument.So i can't understand why and how it works.

2)In the second lambda why is not "column" inside parenthesis?Isn't the format of a lambda something like:

Code: Select all

((lambda (x) (+ x x)) (* 3 4))
and this returning 24?

I haven't found anywhere a lambda without arguments a the parenthesis.

Any kind of info should be useful since i'm a learn.Even the slightest.

Thanx in advance.

saulgoode
Posts: 45
Joined: Tue Dec 14, 2010 1:39 am

Re: Questions In Matrix Multiplication

Post by saulgoode » Thu Nov 10, 2011 1:51 am

sepuku wrote:1)In the first prodecure(line 6) we call as "map * row column" but my map is like (map proc lst).In line 6 there is one more argument.So i can't understand why and how it works.
In general, the number of lists supplied when using 'map' needs to match the number of arguments expected by function. For example, if you were to map 'cons' then you would need to supply two lists:

Code: Select all

(map cons '(1 2 3) '(4 5 6)) ==> ((1 . 4) (2 . 5) (3 . 6))
The multiplication operator accepts any number of arguments, so you are free to pass as many lists as you want; all the cars of the lists will be multiplied, all the cadrs will be multiplied together, all the caddrs... -- producing a new list.

Code: Select all

(map * '(1 2 3) '(4 5 6) '(7 8 9)) ==> (28 80 162) ;; I.E., ((* 1 4 7) (* 2 5 8) (* 3 6 9))
sepuku wrote:2)In the second lambda why is not "column" inside parenthesis?Isn't the format of a lambda something like:

Code: Select all

((lambda (x) (+ x x)) (* 3 4))
and this returning 24?

I haven't found anywhere a lambda without arguments a the parenthesis.
That is a special notation for passing a variable number of arguments to a procedure (it is equivalent to "(define (foo . x) ...") -- if that form is familiar to you. For example

Code: Select all

(define foo (lambda x (display x)))

(foo 1 2 3) ==> (1 2 3)
(foo 1) ==> (1)
(foo) ==> () ;; i.e. the empty list

(define matrix1 '((11 12) (21 22)))
(foo matrix1) == (((11 12) (21 22))))

sepuku
Posts: 12
Joined: Thu May 12, 2011 11:00 am

Re: Questions In Matrix Multiplication

Post by sepuku » Thu Nov 10, 2011 7:18 am

First of all thank you for your reply. :)
Thank you for exaplaining the map procedure.So far i was not aware that the number of arguments of map depend on the procedure we map.(although i should :oops: )
Now this gives birth to a new question :
The multiplication operator accepts any number of arguments
to make a multiplication we need at least 2 arguments right? When we (map * row) what multiplication is done?
If i understand well the substitutions, this is like saying (map * matrix2).Is that correct?I can not understand how the substitution works in all the program...maybe it's because of the lambdas :roll:

for example when we have this:

Code: Select all

(matrix-multiply '((1 2) (3 4)) '((-3 -8 3) (-2 1 4)))
We want the first element of the resulting matrix to be (+ (* 1 -3) (* 2 -2))

this happens in

Code: Select all

(apply + (map * row column))
But how it understands what is everytime "row" and "column" ? :oops:

sepuku
Posts: 12
Joined: Thu May 12, 2011 11:00 am

Re: Questions In Matrix Multiplication

Post by sepuku » Thu Nov 10, 2011 11:31 am

Ahhh wrong!!! It's not (map * row), it's (map * row column).

But is my substitution correct? :roll:

saulgoode
Posts: 45
Joined: Tue Dec 14, 2010 1:39 am

Re: Questions In Matrix Multiplication

Post by saulgoode » Thu Nov 10, 2011 1:48 pm

sepuku wrote:to make a multiplication we need at least 2 arguments right?
Technically, no. If passed no arguments, the '*' function in Scheme returns "1"; if passed one argument, it returns that argument.
sepuku wrote:When we (map * row) what multiplication is done?
Perhaps this would be made clear by considering the following implementation of a multiply procedure that accepts a variable number of arguments, but relies upon a 'mult2' function which requires exactly two arguments (ignoring that Scheme already provides this functionality).

Code: Select all

(define (my-* . args)
  (define (iter lis previous-value)
    (if (null? lis)
      previous-value
      (iter (cdr list) (mult2 (car lis) previous-value)) ))
  (iter args 1) )

; or the same thing using lambda notation
;
(define my-*
  (lambda args
    (define iter
      (lambda (lis previous-value)
        (if (null? lis)
          previous-value
          (iter (cdr lis) (mult2 (car lis) previous-value)) )))
    (iter args 1) ))
When you map 'my-*' to a single list of numbers, each of those numbers gets multiplied by "1" to form a new list. In other words, Nothing really happens except that you've created a new copy of the original list. The behavior of the '*' function is identical (we could have named our function '*' but then we'd need to ensure that mult2 didn't reference it as such).
sepuku wrote:If i understand well the substitutions, this is like saying (map * matrix2).Is that correct?I can not understand how the substitution works in all the program...maybe it's because of the lambdas :roll:

for example when we have this:

Code: Select all

(matrix-multiply '((1 2) (3 4)) '((-3 -8 3) (-2 1 4)))
We want the first element of the resulting matrix to be (+ (* 1 -3) (* 2 -2))

this happens in

Code: Select all

(apply + (map * row column))
But how it understands what is everytime "row" and "column" ? :oops:
Actually, I think the secret to understanding this lies in how "(apply map (lambda colums" works. The "apply +" is not evaluated until after both lambdas are created.

Consider the evaluation of "(apply map list '((-3 -8 3) (-2 1 4)))", a list is created from the cars of each of the two lists, from each of the cadrs, and from each of the caddrs.

Code: Select all

(apply map list '(-3 -8 3) '(-2 1 4)) ==> ((-3 -2) (-8 1) (3 4))
The actual breakdown of this is a little bit involved, but fairly straightforward; I will leave that for you to investigate on your own. Our main interest is how this transforms when our internal lambda is substituted for the 'list' function. If we use the "identity" lambda function (i.e., a lambda that when invoked returns its argument), we get the same result as for the above code but now we have a way to "do stuff" with the arguments other than just inserting them in a list.

Code: Select all

(apply map (lambda x x) '((-3 -8 3) (-2 1 4))) ==> ((-3 -2) (-8 1) (3 4))
; just to show that the mapped cars, cadrs, etc are passed to the body of our lambda:
(apply map (lambda x (reverse x)) '((-3 -8 3) (-2 1 4))) ==> ((-2 -3) (1 -8) (4 3))
So our (inner) lambda has been passed each of those three lists (of two numbers) and is tasked with the job of multiplying them, element-by-element, with one of the 'row's of 'matrix1' (in particular, the row that is being mapped as an argument to the outer lambda).

Code: Select all

(define row '(1 2)) ;; simulate the outer lambda mapping of the first row of matrix1
; just as an exercise, compute the non-summed products of the row elements by the column elements
(apply map (lambda column
  (map * row column)) '((-3 -8 3) (-2 1 4))) ==> ((-3 -4) (-8 2) (3 8)) ;; before adding the factors

; now, insert our 'apply +' operation to sum the products of the element multiplication
(apply map (lambda column
  (apply + (map * row column))) '((-3 -8 3) (-2 1 4))) ==> (-7 -6 11) ;; yay! this is the first row of the matrix product

sepuku
Posts: 12
Joined: Thu May 12, 2011 11:00 am

Re: Questions In Matrix Multiplication

Post by sepuku » Thu Nov 17, 2011 6:23 pm

First of all i'm really sorry for the late answer.But i study and write code in my free time and i have not much lately.

Secondly i want to thank you for the posted paradigms.Although it should be obvious,before your post it wasn't. :D

Once again thank you for your time. :mrgreen:

Post Reply