Hi,
I'm trying to implement a simple matrix function that takes a
matrix, represented as a list with inner list (one list per row of
matrix) and returns it's inverse. This means that '((1 2) (3 4)) =>
'((1 3) (2 4)). I thought of three possible ways to write it, but
all have failed. I have posted my attempts below with
comments. (P.S.: I tried to stay away from mapcar-esque functions
because I wanted to understand the plain, recursive way to do this
but when those attempts failed I tried writing a version that relies
on mapping functions.)
;; 1st version
;; the idea is that the functions gets a list like:
;;
;; '((1 2) (3 4))
;;
;; then takes from it (done by the first mapcar) the list
;;
;; '(1 3)
;;
;; which is cons'ed into the next iteration which receives the
;; list:
;;
;; '((2) (4))
;;
;; This is supposed to be achieved by the second mapcar. I don't know
;; what's wrong with this, it won't even run. I'm clueless as to why
;; this doesn't work.
(defun inverse-matrix (A)
(if (null A)
nil
(cons (map first A)
(inverse-matrix
(list
(map
(lambda (x)
(or
(and x (list (first (rest x))))
nil)) A))))))
;; 2nd version
;; the problem with this is that when passed something like
;;
;; '((1 2) (3 4))
;;
;; it returns '((1 3) (3 4)). I don't understand how that 3 gets
;; in the last list. Could someone explain this?
(defun inverse-matrix2 (A)
(if (null A)
nil
(cons (first-row-elems A) (rest A))))
(defun first-row-elems (A)
(if (null A)
nil
(cons (first (first A))
(first-row-elems (rest A)))))
;; 3rd version
;; - have a helper function that passes a row and the
;; rest of the rows to another function.
;; - use the next function to cons the first element
;; of the first argument to the first element of the next argument.
;; The problem with this is that it loops infinitely. Why?
(defun inverse-matrix3 (row-elems rows-left)
(if (null row-elems)
nil
(cons (first row-elems) (first (first rows-left))))
(inverse-matrix3 (rest row-elems) (rest rows-left)))
;; note to call the helper -- bad function naming
(defun inverse-matrix3-helper (A)
(if (null A)
nil
(inverse-matrix3 (first A) (inverse-matrix3-helper (rest A)))))
I appreciate all the help.
Thanks a lot,
--
Jordan Katz <····@underlevel.net> | Mind the gap
P.S.: this is for my own, private study of CL. I'm not taking any CS
classes.
"Jordan Katz" <····@underlevel.net> wrote in message
···················@underlevel.underlevel.net...
> Hi,
>
> I'm trying to implement a simple matrix function that takes a
> matrix, represented as a list with inner list (one list per row of
> matrix) and returns it's inverse. This means that '((1 2) (3 4)) =>
> '((1 3) (2 4)). I thought of three possible ways to write it, but
> all have failed. I have posted my attempts below with
> comments. (P.S.: I tried to stay away from mapcar-esque functions
> because I wanted to understand the plain, recursive way to do this
Personally, I would never look for a recursive solution when you are dealing
with a list of elements as opposed to a tree of unknown depth. So I think some
kind of mapping or looping is you answer.
It seems recursing for matrix inversion won't work because you are changing its
shape anyway. Or at least it will be more complicated...or maybe its just
me..?
BTW the classic lisp solution to this is:
(defun transpose (m)
(apply #'mapcar #'list m))
but that is not likely to occur to someone just starting out!
I might suggest using loop and collect (hint: check the length of your rows)
> ;; This is supposed to be achieved by the second mapcar. I don't know
> ;; what's wrong with this, it won't even run. I'm clueless as to why
> ;; this doesn't work.
> (defun inverse-matrix (A)
> (if (null A)
> nil
> (cons (map first A)
> (inverse-matrix
> (list
> (map
> (lambda (x)
> (or
> (and x (list (first (rest x))))
> nil)) A))))))
>
A stylistic suggestion:
(defun inverse-matrix (a)
(if (null a)
nil
(cons (map first a)
(inverse-matrix
(list (map (lambda (x)
(or (and x (list (first (rest x))))
nil))
a))))))
In the code above "first" is an unbound variable. You probably mean (mapcar
#'first a)
I'll try to do more later..
--
Coby
(remove #\space "coby . beck @ opentechgroup . com")
Hi.
Im'e new to this groupe, as I use Lisp with AutoCAD I maby are using Lisp
different with AutoLisp , but you say ;
"Coby Beck" <·····@mercury.bc.ca> skrev i en meddelelse
······························@typhoon.tampabay.rr.com...
>
> "Jordan Katz" <····@underlevel.net> wrote in message
> ···················@underlevel.underlevel.net...
> > Hi,
> >
> > I'm trying to implement a simple matrix function that takes a
> > matrix, represented as a list with inner list (one list per row of
> > matrix) and returns it's inverse. This means that '((1 2) (3 4)) =>
> > '((1 3) (2 4)). I thought of three possible ways to write it, but
> > all have failed. I have posted my attempts below with
> > comments. (P.S.: I tried to stay away from mapcar-esque functions
> > because I wanted to understand the plain, recursive way to do this
>
> Personally, I would never look for a recursive solution when you are dealing
> with a list of elements as opposed to a tree of unknown depth. So I think
some
> kind of mapping or looping is you answer.
>
> It seems recursing for matrix inversion won't work because you are changing
its
> shape anyway. Or at least it will be more complicated...or maybe its just
> me..?
>
> BTW the classic lisp solution to this is:
> (defun transpose (m)
> (apply #'mapcar #'list m))
>
> but that is not likely to occur to someone just starting out!
>
> I might suggest using loop and collect (hint: check the length of your rows)
>
> > ;; This is supposed to be achieved by the second mapcar. I don't know
> > ;; what's wrong with this, it won't even run. I'm clueless as to why
> > ;; this doesn't work.
> > (defun inverse-matrix (A)
> > (if (null A)
> > nil
> > (cons (map first A)
> > (inverse-matrix
> > (list
> > (map
> > (lambda (x)
> > (or
> > (and x (list (first (rest x))))
> > nil)) A))))))
> >
>
> A stylistic suggestion:
>
> (defun inverse-matrix (a)
> (if (null a)
> nil
> (cons (map first a)
> (inverse-matrix
> (list (map (lambda (x)
> (or (and x (list (first (rest x))))
> nil))
> a))))))
>
> In the code above "first" is an unbound variable. You probably mean (mapcar
> #'first a)
>
> I'll try to do more later..
I se this quite different, as I allway's focus on the List, and then whatever is
in it, I do matrix operations when that is required, or use the list as
database, and sure somwhere in infinity or mem. run out ,there are a limit for a
recursive function, -------- still what you say, is that recurtion don't work on
list's ; that's not my experience ,it work on whatever you ask it to work. But
maby this is what make Lisp easy, you can use it the style you chose ;))
P.C.
"P.C." <··········@privat.dk> writes:
> Hi.
> Im'e new to this groupe, as I use Lisp with AutoCAD I maby are using Lisp
> different with AutoLisp , but you say ;
>
> "Coby Beck" <·····@mercury.bc.ca> skrev i en meddelelse
> ······························@typhoon.tampabay.rr.com...
> >
> > Personally, I would never look for a recursive solution when you
> > are dealing with a list of elements as opposed to a tree of
> > unknown depth. So I think some kind of mapping or looping is you
> > answer.
[...]
> I se this quite different, as I allway's focus on the List, and then
> whatever is in it, I do matrix operations when that is required, or
> use the list as database, and sure somwhere in infinity or mem. run
> out ,there are a limit for a recursive function, -------- still what
> you say, is that recurtion don't work on list's ; that's not my
> experience ,it work on whatever you ask it to work. But maby this is
> what make Lisp easy, you can use it the style you chose ;)) P.C.
It's true that you *can* use recursion to operate on lists. However,
it's a bad idea because each element in the list will use a stack
frame, and if you don't know how long the lists can be (or how much
stack will be left when your function is called), you don't know if
your function is safe. That is, if it will run out of stack space.
I think Coby was arguing for only using recursion when you need it.
When you need it, you need it, and you should use it[*], but when you
don't, it's just asking for problems.
[*] Well, sometimes it's even a good idea to rewrite recursive
algorithms to use a data stack instead of the control stack. But it
would just be annoying and confusing to rewrite a list processing
function to use a data stack instead of just making it iterative.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Hi.
"Thomas F. Burdick" <···@conquest.OCF.Berkeley.EDU> skrev i en meddelelse
····················@conquest.OCF.Berkeley.EDU...
> [*] Well, sometimes it's even a good idea to rewrite recursive
> algorithms to use a data stack instead of the control stack. But it
> would just be annoying and confusing to rewrite a list processing
> function to use a data stack instead of just making it iterative.
I se your point ,but I guess both apply and mapcar are imp. recursive anyway
from what I know.
But for me it's more than a matter of stacks, as I found, that code get more
smooth, if you can say, that it work in a way, where you "write the ansver". I
find it being a matter of "saying the ansver" then producing that ,can involve
some general function definations like (a (b c)) , still that don't make code
easyer understood by others.
Off-topic I got this common Lisp manual, size of an A5 ,thick as a brick where
some groupe describe the framework of Common Lisp, I allway's liked to find some
use for it, but that's difficult in AutoLISP ,as there you rather use as few
primitive functions with the specific AutoCAD orientet ,and then recursive
functions come in as a neat test bench ; but I don't re-write that much into
iretative as into statements ,if possible. Still I guess we all code sligtly
different.
P.C.
http://makeashorterlink.com/?B5574244
"P.C." <··········@privat.dk> writes:
> I se your point ,but I guess both apply and mapcar are imp. recursive anyway
> from what I know.
MAPCAR might be implemented recursively in implementations that offer
full tail-call elimination, but I'd wager that e.g. in most Common Lisp
implementations MAPCAR is implemented iteratively, even if they offer
full TCE. Case in point is CMU CL, which uses DO (which in turn is
implemented via TAGBODY and GO) to implement MAPCAR.
APPLY on the other hand is most likely to be a primitive[1] operation,
and not likely to be implemented recursively. In compiled
implementations APPLY is likely to be handled directly by the
compiler.
> But for me it's more than a matter of stacks, as I found, that code
> get more smooth, if you can say, that it work in a way, where you
> "write the ansver". I find it being a matter of "saying the ansver"
> then producing that ,can involve some general function definations
> like (a (b c)) , still that don't make code easyer understood by
> others.
I agree that there are certain things that are just more elegantly
expressed using (linear) recursion than iteration. OTOH there are
also things that I find much more lucidly expressed using iteration
constructs.
Regs, Pierre.
Footnotes:
[1] The part that does the actual applying that is. There is likely
to be some non-primitive part of APPLY which handles the LIST*
operation inherent in APPLY. That might even be implemented
recursively, though again, I'd wager in most implementations it
isn't.
--
Pierre R. Mai <····@acm.org> http://www.pmsf.de/pmai/
The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents. -- Nathaniel Borenstein
Hi.
"Pierre R. Mai" <····@acm.org> skrev i en meddelelse
···················@orion.bln.pmsf.de...
> I agree that there are certain things that are just more elegantly
> expressed using (linear) recursion than iteration. OTOH there are
> also things that I find much more lucidly expressed using iteration
> constructs.
Now you people proberly use setf and set ,rather than the setq mostly used in
AutoLISP, but like addressing multible lists used during a number calculations
,isn't the style I prefere.
I rather tell myself, that Lisp work perfect with functions as parameters, and
then instead of having the mem. filled with a number of setq var's ,I rather ask
if it's possible to make a function yield the list instantly within the
function.
It's nice to make step by step programming, but it'd my experience, that it is
much easyer, to define functions that will yield the list whenever it's needed,
instead of making setq store the list while computasion. Now it don't make code
easyer to understand while using a function as parameter ask you to check the
function instead of what bindings are done, and you can't recornise how the same
list are computet, but you don't need that many setq's that way, and it's my
experience, that this is a much more effective programming style , esp with
Lisp.
Have a nice day.
P.C.
http://makeashorterlink.com/?B5574244
"P.C." <··········@privat.dk> wrote in message
······························@dspool01.news.tele.dk...
> Hi.
>
> "Pierre R. Mai" <····@acm.org> skrev i en meddelelse
> ···················@orion.bln.pmsf.de...
> > I agree that there are certain things that are just more elegantly
> > expressed using (linear) recursion than iteration. OTOH there are
> > also things that I find much more lucidly expressed using iteration
> > constructs.
>
> Now you people proberly use setf and set ,rather than the setq mostly used in
> AutoLISP, but like addressing multible lists used during a number
calculations
> ,isn't the style I prefere.
> I rather tell myself, that Lisp work perfect with functions as parameters,
and
> then instead of having the mem. filled with a number of setq var's ,I rather
ask
> if it's possible to make a function yield the list instantly within the
> function.
> It's nice to make step by step programming, but it'd my experience, that it
is
> much easyer, to define functions that will yield the list whenever it's
needed,
> instead of making setq store the list while computasion.
I agree with this, but it is completely unrelated to the text you quoted and
the choice between iteration and recursion. If it was intended as refutation,
I think it misses the point. If not...I'll shut up now... : )
--
Coby
(remove #\space "coby . beck @ opentechgroup . com")
From: Brian P Templeton
Subject: Re: Newbie question about matrices.
Date:
Message-ID: <87u1tn2q44.fsf@tunes.org>
"P.C." <··········@privat.dk> writes:
> Hi.
>
> "Pierre R. Mai" <····@acm.org> skrev i en meddelelse
> ···················@orion.bln.pmsf.de...
>> I agree that there are certain things that are just more elegantly
>> expressed using (linear) recursion than iteration. OTOH there are
>> also things that I find much more lucidly expressed using iteration
>> constructs.
>
> Now you people proberly use setf and set ,rather than the setq mostly used in
> AutoLISP, [...]
In CL either SETQ or SETF is usually used; SETF has the advantage of
being able to do things like
(let ((foo '(a b c)))
(setf (car foo) 'z)
(car foo))
==> z
Whether SETQ or SETF is used for the simple (set... x foo) case is a
matter of personal taste; I've heard a few arguments for using SETF,
but I usually use SETQ for (set... x foo)-type assignments.
--
BPT <···@tunes.org> /"\ ASCII Ribbon Campaign
backronym for Linux: \ / No HTML or RTF in mail
Linux Is Not Unix X No MS-Word in mail
Meme plague ;) ---------> / \ Respect Open Standards
As was pointed out when you asked a similar question on
comp.lang.scheme, the operation you're trying to do is not matrix
inversion, but matrix transposition. You may call it what you wish, of
course.
Here are several plans for transposing an n x n matrix:
1. Write a (listref matrix rownum colnum) function. Write the
transpose function to use this to set (listref new-matrix i j) with
(listref old-matrix j i) for all i,j = 0 .. n-1, after first creating
new-matrix in the same shape as old-matrix. This is an imperative,
non-recursive solution.
2. Produce an intermediate form of the matrix as
(matrix-to-aux-form matrix) ->
(first-row first-column n-1xn-1-rest-of-matrix)
(aux-form-to-matrix first-row first-column submatrix) ->
matrix
(defun transpose (matrix)
(let ((aux (matrix-to-aux-form matrix)))
(aux-form-to-matrix (second aux) (first aux)
(transpose (third aux)))))
This is clearly recursive.
3. A straightforward Lisp solution is
(apply #'mapcar (cons #'list '((1 2 3) (4 5 6) (7 8 9)))) ->
((1 4 7) (2 5 8) (3 6 9))
If you want a more advanced problem when you finish with this one, you
can also look at transposition of tensors, where a tensor is a
generalization of a matrix which can have planes and hyperplanes (you
can have tensors with n x n x n or n x n x n x n or n x n x n x n x n,
etc, elements arranged in the appropriate hypercube. Now when you
transpose, you are specifying two of the axes and swapping the elements.
So you'd define a function
(tensor-transpose tensor axis other-axis)
Jeff
"Jeff Greif" <······@spam-me-not.alumni.princeton.edu> writes:
> As was pointed out when you asked a similar question on
> comp.lang.scheme, the operation you're trying to do is not matrix
> inversion, but matrix transposition. You may call it what you wish, of
> course.
>
> Here are several plans for transposing an n x n matrix:
>
> 1. Write a (listref matrix rownum colnum) function. Write the
> transpose function to use this to set (listref new-matrix i j) with
> (listref old-matrix j i) for all i,j = 0 .. n-1, after first creating
> new-matrix in the same shape as old-matrix. This is an imperative,
> non-recursive solution.
This is also one that writing would probably aid in your understanding
of the features offered by Common Lisp. Try to write everything you
need to make this work:
(defun transpose (matrix)
(multiple-value-bind
(width height)
(matrix-dimensions matrix)
(let ((new-matrix (make-matrix width height)))
(loop as i below width
do (loop as j below height
do (setf (matrix-ref new-matrix i j)
(matrix-ref matrix j i))))
new-matrix)))
Then you can work on making matrix-ref and (setf matrix-ref) work in
constant time :)
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Jordan Katz <····@underlevel.net> writes:
> I'm trying to implement a simple matrix function that takes a
> matrix, represented as a list with inner list (one list per row of
> matrix) and returns it's inverse. This means that '((1 2) (3 4)) =>
> '((1 3) (2 4)).
Since your matrix function transpose is zip is unzip, the
Zip in Elisp thread of December 2000 might enlighten you.
You'll find the relevant article of Kent Pitman at
http://groups.google.de/groups?hl=en&····················@world.std.com
--
"Das Auto hat keine Zukunft. Ich setze aufs Pferd." Wilhelm II. (1859-1941)
Jordan Katz <····@underlevel.net> writes:
>
> Hi,
>
> I'm trying to implement a simple matrix function that takes a
> matrix, represented as a list with inner list (one list per row of
> matrix) and returns it's inverse. This means that '((1 2) (3 4)) =>
> '((1 3) (2 4)). I thought of three possible ways to write it, but
> all have failed. I have posted my attempts below with
> comments. (P.S.: I tried to stay away from mapcar-esque functions
> because I wanted to understand the plain, recursive way to do this
> but when those attempts failed I tried writing a version that relies
> on mapping functions.)
OK. One thing that will help you out is to take advantage of the
interactive nature of the Lisp environment and try out individual parts
of the functions you write that don't seem to work the way you expect.
That may make locating the problems a bit easier, for example:
> ;; 1st version
> ;; the idea is that the functions gets a list like:
> ;;
> ;; '((1 2) (3 4))
> ;;
> ;; then takes from it (done by the first mapcar) the list
> ;;
> ;; '(1 3)
> ;;
> ;; which is cons'ed into the next iteration which receives the
> ;; list:
> ;;
> ;; '((2) (4))
> ;;
> ;; This is supposed to be achieved by the second mapcar. I don't know
> ;; what's wrong with this, it won't even run. I'm clueless as to why
> ;; this doesn't work.
> (defun inverse-matrix (A)
> (if (null A)
> nil
> (cons (map first A)
> (inverse-matrix
> (list
> (map
> (lambda (x)
> (or
> (and x (list (first (rest x))))
> nil)) A))))))
A couple of problems, one of which is that in Common Lisp (vice Scheme),
the function argument to map needs to be quoted if you are passing the
actual name of the function. Presumably when you try running this, you
get an unbound variable error from the line
(map first A)
Also, MAP in Common Lisp takes a first argument of the type of returned
sequence, since there is a larger set of built-in sequence datatypes.
For what you are doing, you would want to use MAPCAR instead, which maps
a function onto successive list elements and returns a list of the
answers. You can then try out the following fragment and see that it
does what you expect:
[1] (mapcar #'first '((1 2) (3 4))) => (1 3)
The second map call looks horribly complicated. From the comments it
seems you would like to transform
((1 2) (3 4)) into ((2) (4))
so I would suggest a slightly simpler solution, namely recognize that
(2) is the REST of (1 2) and just confirm with
[2] (mapcar #'rest '((1 2) (3 4))) => ((2) (4))
OK, a recursive call would then encounter this simplified list and
proceed via line [1] to transform it into
(2 4)
Now, at this point you would be getting into a bit of trouble, since
applying [2] would give you not nil, but rather a list of nils:
(mapcar #'rest '((2) (4))) => (() ())
and a quick check determines that
(null '(() ())) => NIL
so you would not satisfy the termination test of the recursive code.
If you are willing to assume that you only get well-formed input, then
the test
(null A) could be transformed into (null (first A))
and thus you could have a solution that looked a bit like this
(defun inverse-matrix (A)
(if (null (first A))
nil
(cons (mapcar #'first A)
(inverse-matrix (mapcar #'rest A)))))
> ;; 2nd version
> ;; the problem with this is that when passed something like
> ;;
> ;; '((1 2) (3 4))
> ;;
> ;; it returns '((1 3) (3 4)). I don't understand how that 3 gets
> ;; in the last list. Could someone explain this?
OK, this is where you really get to use the interactive nature of Lisp
to help you figure out the answer.
> (defun inverse-matrix2 (A)
> (if (null A)
> nil
> (cons (first-row-elems A) (rest A))))
Try looking at things in pieces and all should become clear:
1. (first-row-elems '((1 2) (3 4))) => (1 3) ; Good
2. (rest '((1 2) (3 4))) => ((3 4)) ; ?
3. (cons '(1 2) '((3 4))) => ((1 3) (3 4)) ; Aha!
The process of debugging these functions can be aided by taking them in
small pieces and seeing what is actually being done.
(You can achieve some of this by tracing function calls, but since
primitives like FIRST, REST and CONS are used internally by the Lisp
system, if you try tracing them you will often get a lot of trace
information that is not from your own code and it will be confusing)
> (defun first-row-elems (A)
> (if (null A)
> nil
> (cons (first (first A))
> (first-row-elems (rest A)))))
>
>
> ;; 3rd version
> ;; - have a helper function that passes a row and the
> ;; rest of the rows to another function.
> ;; - use the next function to cons the first element
> ;; of the first argument to the first element of the next argument.
> ;; The problem with this is that it loops infinitely. Why?
Applying the techniques above is left as an exercise to the reader. :)
> (defun inverse-matrix3 (row-elems rows-left)
> (if (null row-elems)
> nil
> (cons (first row-elems) (first (first rows-left))))
> (inverse-matrix3 (rest row-elems) (rest rows-left)))
OK, I can't help but comment on the previous function anyway. As
written, the (if ...) clause could be completely eliminated. The value
returned by the IF expression is not used by anything, nor is it
returned by the inverse-matrix3 function.
> ;; note to call the helper -- bad function naming
Yes. Normally one would tend to reverse the names of the two functions.
> (defun inverse-matrix3-helper (A)
> (if (null A)
> nil
> (inverse-matrix3 (first A) (inverse-matrix3-helper (rest A)))))
>
> I appreciate all the help.
>
> Thanks a lot,
> --
> Jordan Katz <····@underlevel.net> | Mind the gap
>
> P.S.: this is for my own, private study of CL. I'm not taking any CS
> classes.
Actually, even if this were homework, posting what you tried and asking
some reasonably specific questions would allow us to guide you without
just giving the answer.
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu