Write Lisp functions to do the following.
1.(10) Write a Lisp function new-gcd which takes two integers n and m
as parameters and returns the gcd (n, m). Please do not use the
primitive gcd. Use the standard Euclidean algorithm which says that
given u and v (u and v cannot be 0 at the same time), gcd(u, v) = u if
v=0 else gcd(u, v) = gcd(v, u mod v).
2.(20) Lisp provides a primitive reverse which reverse the top-level
elements of a list. For example, (reverse '((a b) c d (e 1))) returns
((e 1) d c (a b)). (a) Define your own function new-reverse without
using the primitive reverse; (b) Define a function reverse-all which
reverses all the elements. For example, (reverse-all '((a (b (c)))
d (e (f)))) will result in (((F) E) D (((C) B) A)).
3.(30) (1) Write a function ismember that takes an element (symbol,
number, or list) and a list and returns T or Nil depending on whether
the element is a top-level element of the list (please do not use the
primitive member). (2) A list can be considered as a set (provided that
no two elements are the same). Write a Lisp function that takes two
sets and returns their union. (3) Do the same for intersection. Note
that your results should be lists containing no duplicate elements.
4.(15) Write a function rall that take an element (note that the
element could be a list as well) and a list as parameters and removes
all occurrences of the element (not just the top-level element).
5.(10) Write a function f that takes a list and returns a list where
each element (symbol, number, or list) e of the original list is
changed to (e dot). For example, (f '(a (b) c)) return ((a dot)
((b) dot) (c dot)). Note that you only need one statement in f and it
has to use mapcar and lambda (for an anonymous function you have to
define).
6.(15) Write a Lisp function power that for input x and n, it computes
xn. Note that your algorithm should have a running time of O(log n),
rather than O(n), meaning that it uses multiplications O(log n) time.
······@gmail.com writes:
> Write Lisp functions to do the following.
>
> 1.(10) Write a Lisp function new-gcd which takes two integers n and m
> as parameters and returns the gcd (n, m). Please do not use the
> primitive gcd. Use the standard Euclidean algorithm which says that
> given u and v (u and v cannot be 0 at the same time), gcd(u, v) = u if
> v=0 else gcd(u, v) = gcd(v, u mod v).
A quick visit to DADS gives you some info:
http://www.nist.gov/dads/HTML/euclidalgo.html
There you find an implementation in Scheme:
http://www.math.grin.edu/~stone/events/scheme-workshop/gcd.html
Which is something like:
(define gcd
(lambda (m n)
(if (zero? n) m (gcd n (remainder m n)))))
Which can be converted to Common Lisp, such as:
(defun my-gcd (m n)
(if (zerop n) m (my-gcd n (rem m n))))
The problem is that, what am I going to do with 10 points? ;-)
> 6.(15) Write a Lisp function power that for input x and n, it computes
> xn. Note that your algorithm should have a running time of O(log n),
> rather than O(n), meaning that it uses multiplications O(log n) time.
I think you are talking about this algorithm:
http://www.nist.gov/dads/HTML/repeatedSquaring.html
It provides a C implementation:
http://www.cs.ucsd.edu/classes/fa96/cse30/lec4/exp.html
Maybe that can help you a little bit.
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
From: Surendra Singhi
Subject: Re: help me with starting this in files
Date:
Message-ID: <ct20i3$5lo$1@news.asu.edu>
······@gmail.com wrote:
> Write Lisp functions to do the following.
>
> 1.(10) Write a Lisp function new-gcd which takes two integers n and m
> as parameters and returns the gcd (n, m). Please do not use the
> primitive gcd. Use the standard Euclidean algorithm which says that
> given u and v (u and v cannot be 0 at the same time), gcd(u, v) = u if
> v=0 else gcd(u, v) = gcd(v, u mod v).
>
> 2.(20) Lisp provides a primitive reverse which reverse the top-level
> elements of a list. For example, (reverse '((a b) c d (e 1))) returns
> ((e 1) d c (a b)). (a) Define your own function new-reverse without
> using the primitive reverse; (b) Define a function reverse-all which
> reverses all the elements. For example, (reverse-all '((a (b (c)))
> d (e (f)))) will result in (((F) E) D (((C) B) A)).
>
> 3.(30) (1) Write a function ismember that takes an element (symbol,
> number, or list) and a list and returns T or Nil depending on whether
> the element is a top-level element of the list (please do not use the
> primitive member). (2) A list can be considered as a set (provided that
> no two elements are the same). Write a Lisp function that takes two
> sets and returns their union. (3) Do the same for intersection. Note
> that your results should be lists containing no duplicate elements.
>
> 4.(15) Write a function rall that take an element (note that the
> element could be a list as well) and a list as parameters and removes
> all occurrences of the element (not just the top-level element).
>
> 5.(10) Write a function f that takes a list and returns a list where
> each element (symbol, number, or list) e of the original list is
> changed to (e dot). For example, (f '(a (b) c)) return ((a dot)
> ((b) dot) (c dot)). Note that you only need one statement in f and it
> has to use mapcar and lambda (for an anonymous function you have to
> define).
>
> 6.(15) Write a Lisp function power that for input x and n, it computes
> xn. Note that your algorithm should have a running time of O(log n),
> rather than O(n), meaning that it uses multiplications O(log n) time.
>
FAQ for comp.lang.lisp
1.5. Can you help me with my homework?
But of course!
However, we will need the e-mail address of your lecturer or teaching
instructor to best aid you; for it is only fair that if we do the
homework we should get the course credits. Alternatively, should you
wish to hire a consultant from the group, competitive rates can be arranged.
Post the assignment, and your attempt so far; state explicitly that it
is homework. You may find a kind soul on the group to explain some point
that you are missing; this is more likely the more visible your own work
is. Posts of the form "my assignment is due tomorrow please hlep!" are
unlikely to engender much sympathy.
http://www-jcsu.jesus.cam.ac.uk/~csr21/lispfaq.html#AEN49
--
Surendra Singhi
www.public.asu.edu/~sksinghi/
Surendra Singhi <·········@netscape.net> writes:
> FAQ for comp.lang.lisp
> 1.5. Can you help me with my homework?
>
> But of course!
>
> However, we will need the e-mail address of your lecturer or teaching
> instructor to best aid you; for it is only fair that if we do the
> homework we should get the course credits. Alternatively, should you
> wish to hire a consultant from the group, competitive rates can be
> arranged.
>
> Post the assignment, and your attempt so far; state explicitly that it
> is homework. You may find a kind soul on the group to explain some
> point that you are missing; this is more likely the more visible your
> own work is. Posts of the form "my assignment is due tomorrow please
> hlep!" are unlikely to engender much sympathy.
>
> http://www-jcsu.jesus.cam.ac.uk/~csr21/lispfaq.html#AEN49
Maybe the FAQ should just send them to this joker:
<http://www.cshomework.com/>
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
······@gmail.com writes:
> Write Lisp functions to do the following.
;; 1.(10) Write a Lisp function new-gcd which takes two integers n and m
;; as parameters and returns the gcd (n, m). Please do not use the
;; primitive gcd. Use the standard Euclidean algorithm which says that
;; given u and v (u and v cannot be 0 at the same time), gcd(u, v) = u if
;; v=0 else gcd(u, v) = gcd(v, u mod v).
(defun new-gcd (n m)
(labels ((gcd (u v)
(if (= 0 v)
u
(gcd v (mod u v)))))
(gcd n m)))
;; 2.(20) Lisp provides a primitive reverse which reverse the top-level
;; elements of a list. For example, (reverse '((a b) c d (e 1))) returns
;; ((e 1) d c (a b)). (a) Define your own function new-reverse without
;; using the primitive reverse; (b) Define a function reverse-all which
;; reverses all the elements. For example, (reverse-all '((a (b (c)))
;; d (e (f)))) will result in (((F) E) D (((C) B) A)).
;; (a)
(defun new-reverse (l) (nreverse (copy-list l)))
;; (b)
(defun reverse-all (l)
(reverse (mapcar (lambda (x) (if (listp x) (reverse-all x) x)) l)))
;; 3.(30) (1) Write a function ismember that takes an element (symbol,
;; number, or list) and a list and returns T or Nil depending on whether
;; the element is a top-level element of the list (please do not use the
;; primitive member). (2) A list can be considered as a set (provided that
;; no two elements are the same). Write a Lisp function that takes two
;; sets and returns their union. (3) Do the same for intersection. Note
;; that your results should be lists containing no duplicate elements.
;; (1)
(defun ismember (e l) (not (not (find e l))))
;; (2)
(defun uset-union (r s) (remove-duplicates (append r s)))
;; (3)
(defun uset-intersection (r s)
(flet ((uset-complement
(s b) (reduce (lambda (c e) (remove e c)) s :initial-value b)))
(uset-complement (uset-union (uset-complement r (uset-union r s))
(uset-complement s (uset-union r s)))
(uset-union r s))))
;; 4.(15) Write a function rall that take an element (note that the
;; element could be a list as well) and a list as parameters and removes
;; all occurrences of the element (not just the top-level element).
(defun rall (e l)
(loop with p = l
for n = (remove e p)
until (equal p n)
do (setf p n)
finally (return (mapcar (lambda (sl)(if (listp sl) (rall e sl) sl)) n))))
;; 5.(10) Write a function f that takes a list and returns a list where
;; each element (symbol, number, or list) e of the original list is
;; changed to (e dot). For example, (f '(a (b) c)) return ((a dot)
;; ((b) dot) (c dot)). Note that you only need one statement in f and it
;; has to use mapcar and lambda (for an anonymous function you have to
;; define).
(defun f (l)
(loop for e in l collect (list e 'dot) into res
finally (return (mapcar (lambda (x) x) res))))
;; 6.(15) Write a Lisp function power that for input x and n, it computes
;; xn. Note that your algorithm should have a running time of O(log n),
;; rather than O(n), meaning that it uses multiplications O(log n) time.
(defun power (x n)
(loop with j = 1 for i from 0 to (log n) do (setf j (* j j))
finally return (expt x n)))
--
__Pascal Bourguignon__ http://www.informatimago.com/
Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.
From: Surendra Singhi
Subject: Re: help me with starting this in files
Date:
Message-ID: <ct20ou$5lq$1@news.asu.edu>
Pascal Bourguignon wrote:
> ······@gmail.com writes:
>
>>Write Lisp functions to do the following.
>
>
> ;; 1.(10) Write a Lisp function new-gcd which takes two integers n and m
> ;; as parameters and returns the gcd (n, m). Please do not use the
> ;; primitive gcd. Use the standard Euclidean algorithm which says that
> ;; given u and v (u and v cannot be 0 at the same time), gcd(u, v) = u if
> ;; v=0 else gcd(u, v) = gcd(v, u mod v).
>
> (defun new-gcd (n m)
> (labels ((gcd (u v)
> (if (= 0 v)
> u
> (gcd v (mod u v)))))
> (gcd n m)))
>
>
> ;; 2.(20) Lisp provides a primitive reverse which reverse the top-level
> ;; elements of a list. For example, (reverse '((a b) c d (e 1))) returns
> ;; ((e 1) d c (a b)). (a) Define your own function new-reverse without
> ;; using the primitive reverse; (b) Define a function reverse-all which
> ;; reverses all the elements. For example, (reverse-all '((a (b (c)))
> ;; d (e (f)))) will result in (((F) E) D (((C) B) A)).
>
> ;; (a)
> (defun new-reverse (l) (nreverse (copy-list l)))
>
> ;; (b)
> (defun reverse-all (l)
> (reverse (mapcar (lambda (x) (if (listp x) (reverse-all x) x)) l)))
>
>
> ;; 3.(30) (1) Write a function ismember that takes an element (symbol,
> ;; number, or list) and a list and returns T or Nil depending on whether
> ;; the element is a top-level element of the list (please do not use the
> ;; primitive member). (2) A list can be considered as a set (provided that
> ;; no two elements are the same). Write a Lisp function that takes two
> ;; sets and returns their union. (3) Do the same for intersection. Note
> ;; that your results should be lists containing no duplicate elements.
>
> ;; (1)
> (defun ismember (e l) (not (not (find e l))))
>
> ;; (2)
> (defun uset-union (r s) (remove-duplicates (append r s)))
>
> ;; (3)
> (defun uset-intersection (r s)
> (flet ((uset-complement
> (s b) (reduce (lambda (c e) (remove e c)) s :initial-value b)))
> (uset-complement (uset-union (uset-complement r (uset-union r s))
> (uset-complement s (uset-union r s)))
> (uset-union r s))))
>
>
> ;; 4.(15) Write a function rall that take an element (note that the
> ;; element could be a list as well) and a list as parameters and removes
> ;; all occurrences of the element (not just the top-level element).
>
> (defun rall (e l)
> (loop with p = l
> for n = (remove e p)
> until (equal p n)
> do (setf p n)
> finally (return (mapcar (lambda (sl)(if (listp sl) (rall e sl) sl)) n))))
>
>
> ;; 5.(10) Write a function f that takes a list and returns a list where
> ;; each element (symbol, number, or list) e of the original list is
> ;; changed to (e dot). For example, (f '(a (b) c)) return ((a dot)
> ;; ((b) dot) (c dot)). Note that you only need one statement in f and it
> ;; has to use mapcar and lambda (for an anonymous function you have to
> ;; define).
>
> (defun f (l)
> (loop for e in l collect (list e 'dot) into res
> finally (return (mapcar (lambda (x) x) res))))
>
>
> ;; 6.(15) Write a Lisp function power that for input x and n, it computes
> ;; xn. Note that your algorithm should have a running time of O(log n),
> ;; rather than O(n), meaning that it uses multiplications O(log n) time.
>
> (defun power (x n)
> (loop with j = 1 for i from 0 to (log n) do (setf j (* j j))
> finally return (expt x n)))
>
>
Hello Pascal,
I feel people should not be encouraged to post their homework
questions and then expect someone else to solve them without their
putting any effort.
I appreciate your effort to help the OP, but he got the work done(and
possible full credit on the assignment), without I guess even learning
an iota of lisp.
--
Surendra Singhi
www.public.asu.edu/~sksinghi/
Surendra Singhi wrote:
>>
> Hello Pascal,
> I feel people should not be encouraged to post their homework
> questions and then expect someone else to solve them without their
> putting any effort.
> I appreciate your effort to help the OP, but he got the work done(and
> possible full credit on the assignment), without I guess even learning
> an iota of lisp.
>
Surendra,
You have made the same mistake that I made in the past. Take a close
look at the code Pascal wrote. Do you seriously think that an instructor
will believe that the OP wrote it? We all agree with you about doing
homework for free. Pascal is merely seeing whether the OP is foolish
enough to try turning it in.
David Sletten
Pascal Bourguignon wrote:
>
> ;; 6.(15) Write a Lisp function power that for input x and n, it computes
> ;; xn. Note that your algorithm should have a running time of O(log n),
> ;; rather than O(n), meaning that it uses multiplications O(log n) time.
>
> (defun power (x n)
> (loop with j = 1 for i from 0 to (log n) do (setf j (* j j))
> finally return (expt x n)))
>
>
Ouch! That's just plain evil... ;)
"Pascal Bourguignon" <····@mouse-potato.com> schrieb im Newsbeitrag
...
> ;; ((e 1) d c (a b)). (a) Define your own function new-reverse without
> ;; using the primitive reverse; (b) Define a function reverse-all which
> ;; reverses all the elements. For example, (reverse-all '((a (b (c)))
> ;; d (e (f)))) will result in (((F) E) D (((C) B) A)).
>
> ;; (a)
> (defun new-reverse (l) (nreverse (copy-list l)))
...
Well, reverse was forbitten - maybe nreverse is not appreciated?
I'd suggest a somehow non-deterministic tail recursive approach:
(defun is-member (e l)
(labels ((first-rest-of-the-list (l)
(let ((r nil))
(loop for i from 1 to (1- (length l)) do
(setq r (append r (list (nth i l)))))
r))
(another-rest-of-the-list (l)
(let ((r nil))
(mapc #'(lambda (x) (push x r)) (reverse l))
(pop r)
r))
(rest-of-the-list (l)
(if (> (random 9) 4)
(first-rest-of-the-list l)
(another-rest-of-the-list l)))
(first-of-the-list (l)
(nth 0 l)))
(when l
(if (eql e (first-of-the-list l))
t
(is-member e (rest-of-the-list l))))))
Andreas
On 8999 day of my life Pascal Bourguignon wrote:
> ······@gmail.com writes:
>> Write Lisp functions to do the following.
>
> ;; 1.(10) Write a Lisp function new-gcd which takes two integers n and m
> ;; as parameters and returns the gcd (n, m). Please do not use the
> ;; primitive gcd. Use the standard Euclidean algorithm which says that
> ;; given u and v (u and v cannot be 0 at the same time), gcd(u, v) = u if
> ;; v=0 else gcd(u, v) = gcd(v, u mod v).
>
> (defun new-gcd (n m)
> (labels ((gcd (u v)
> (if (= 0 v)
> u
> (gcd v (mod u v)))))
> (gcd n m)))
(defgeneric new-gcd (x y))
; Pattern matching!!! IF suxx
(defmethod new-gcd (x (y (eql 0)))
x)
(defmethod new-gcd (x y)
(new-gcd y (mod x y)))
--
Ivan Boldyrev
Is 'morning' a gerund?