Hi Everyone,
I have only been writing in Lisp for a week or two. I am in a
multilanguage class at school.
I had a question about muli-tsets. An unordered collection of objects
that may include duplicate entries.... example (a a b c c c d)
Seems like all the book examples deal only with sets, and assume non of
the elements will be repeated.
Well, what if they are.
How would you go about converting these.
The user would need to see the external format '(a b b c d d d e)
while I need something more like '((a 1) (b 2) (c1) (d 3) (e 1)) to work
with.
I would like to try and write some funtion for the following:
insert(obj Lst)
union(Lst1 Lst2)
count(boj Lst) return number of times the obj is in the list.
We have not talked about this in class, nor do I think we will since we
only spend 2 weeks on each language, but I would sure like to know how
to go about doing this.
Any help would be greatly appreciated.
Thanks T
········@home.com writes:
>
> Hi Everyone,
> I have only been writing in Lisp for a week or two. I am in a
> multilanguage class at school.
> I had a question about muli-tsets. An unordered collection of objects
> that may include duplicate entries.... example (a a b c c c d)
> Seems like all the book examples deal only with sets, and assume non of
> the elements will be repeated.
> Well, what if they are.
> How would you go about converting these.
> The user would need to see the external format '(a b b c d d d e)
> while I need something more like '((a 1) (b 2) (c1) (d 3) (e 1)) to work
> with.
>
> I would like to try and write some funtion for the following:
> insert(obj Lst)
> union(Lst1 Lst2)
> count(boj Lst) return number of times the obj is in the list.
>
> We have not talked about this in class, nor do I think we will since we
> only spend 2 weeks on each language, but I would sure like to know how
> to go about doing this.
> Any help would be greatly appreciated.
>
> Thanks T
You can iterate down a list with dolist.
(dolist (elem '(a b b c d d d e))
(print elem))
will cause you to visit each elem.
The list ((a 1) (b 2) ....) is called an a-list or association list.
You can start with an empty one which is just an empty list, '().
You can do (push (list sym 1) my-alist) to add an element.
You can find the entry (b 2) in ((a 1) (b 2) ...) by doing
(assoc 'b '((a 1) (b 2) (c 3))) ;or whatver
Having an (a 1) in your hand, you can increment the value in the
second position with (incf (second elem)). INCF is like ++ in C;
the value returned is the updated value.
I'm not going to write the program for you, but you now have enough
information to write it.
Of course, the solution I've advocated uses side-effects, not recursion
and pure-functional stuff. But that's what real programmers would do,
and you did say it wasn't for a problem set.
Have fun!
--Kent
Thanks for the input.
The only problems I forsee, is that are instructor was very picky about which
already defined functions we could use. For instance we were not allowed to
use the "union" funtion, we had to write our own along with intersection and
insert. We had to do these recursively. It was not too bad, but of course that
was when there was only one of each element. I am still having trouble
figuring out how to do these without the standard functions.
Like I'm not sure he would allow "dolist" or push, if he were to have us do
this. I was just wondering if there was a round about way to accomplish this.
for instance some of my funtions were
union:
(defun myunion (Lst1 Lst2)
(cond
((null Lst1) Lst2)
((memberp (car Lst1) Lst2) (myunion (cdr Lst1) Lst2))
(t (cons (car Lst1)(myunion (cdr Lst1) Lst2)))
)
)
We had t do i t all from scratch.
So now that this is longer winded than intended. I guess I was still wondering
how to change (a a a b b) to ((a3) (b2)) and back again ....the hard way.
Thanks T
Kent M Pitman wrote:
> ········@home.com writes:
>
> >
> > Hi Everyone,
> > I have only been writing in Lisp for a week or two. I am in a
> > multilanguage class at school.
> > I had a question about muli-tsets. An unordered collection of objects
> > that may include duplicate entries.... example (a a b c c c d)
> > Seems like all the book examples deal only with sets, and assume non of
> > the elements will be repeated.
> > Well, what if they are.
> > How would you go about converting these.
> > The user would need to see the external format '(a b b c d d d e)
> > while I need something more like '((a 1) (b 2) (c1) (d 3) (e 1)) to work
> > with.
> >
> > I would like to try and write some funtion for the following:
> > insert(obj Lst)
> > union(Lst1 Lst2)
> > count(boj Lst) return number of times the obj is in the list.
> >
> > We have not talked about this in class, nor do I think we will since we
> > only spend 2 weeks on each language, but I would sure like to know how
> > to go about doing this.
> > Any help would be greatly appreciated.
> >
> > Thanks T
>
> You can iterate down a list with dolist.
> (dolist (elem '(a b b c d d d e))
> (print elem))
> will cause you to visit each elem.
>
> The list ((a 1) (b 2) ....) is called an a-list or association list.
> You can start with an empty one which is just an empty list, '().
> You can do (push (list sym 1) my-alist) to add an element.
> You can find the entry (b 2) in ((a 1) (b 2) ...) by doing
> (assoc 'b '((a 1) (b 2) (c 3))) ;or whatver
> Having an (a 1) in your hand, you can increment the value in the
> second position with (incf (second elem)). INCF is like ++ in C;
> the value returned is the updated value.
>
> I'm not going to write the program for you, but you now have enough
> information to write it.
>
> Of course, the solution I've advocated uses side-effects, not recursion
> and pure-functional stuff. But that's what real programmers would do,
> and you did say it wasn't for a problem set.
>
> Have fun!
> --Kent
········@home.com writes:
> The only problems I forsee, is that are instructor was very
> picky about which already defined functions we could use.
Well, you did identify the problem as something that was for yourself
and not for the instructor.
If you want to know for yourself, then you can use the extra functions.
If you want to know for an instructor, you should identify that fact
clearly so that people don't misunderstand and end up doing your homework
for you.
> Like I'm not sure he would allow "dolist" or push, if he were to have us do
> this. I was just wondering if there was a round about way to accomplish this.
DOLIST is just an abstraction for visiting every element of a list.
It is conceptually the same as a recursive function, but it doesn't
have a problem with stack. (In Scheme, tail recursion is guaranteed
as part of the language definition to get optimized so that you can
use it for control in the way teachers often want you to, but in Lisp
you do NOT have that guarantee and except in toy examples, it is a BAD
PLAN to be using tail recursion in Common Lisp code when trying to
traverse a data structure that might be unbounded in size, since you
will almost certainly blow out of stack.)
The following two functions are essentially equivalent except that
(in Common Lisp), the first will be much more likely to still work for long
lists. Both functions will probably work for short lists.
(defun foo (x)
(dolist (elem x) (print x)))
(defun foo (x)
(cond ((null x) nil)
(t (print (car x))
(foo (cdr x)))))
There are two things your teacher might be trying to teach you.
One is that tail recursion offers a useful way to think about things.
That's a good thing to learn. The other is that tail recursion is
the right thing to use in Common Lisp to traverse lists, and my
personal advice would be to be doubtful of any such claim if you
hear it being made.
You can think about things however you want, but when it comes down
to applying tools, you must apply them with a knowledge of both their
power AND their limitation. To use tail recursion without understanding
that it is limited in CL is not to use the tool correctly.
> for instance some of my funtions were
> union:
> (defun myunion (Lst1 Lst2)
> (cond
> ((null Lst1) Lst2)
> ((memberp (car Lst1) Lst2) (myunion (cdr Lst1) Lst2))
> (t (cons (car Lst1)(myunion (cdr Lst1) Lst2)))
> )
> )
> We had t do it all from scratch.
With dolist, you'd write the following. Incidentally, it's worth
putting those vowels back. Call your variables things that are
easy to pronounce so you can talk to people about your programs and
they will know how to spell what you are talking about.
(defun myunion (list1 list2)
(let ((result list2))
(dolist (element list1)
(unless (member element result)
(push element result)))
result))
> So now that this is longer winded than intended. I guess I was still
> wondering how to change (a a a b b) to ((a3) (b2)) and back again
> ....the hard way.
I'm not sure what "the hard way" is... is that using the real lisp
tools or using the things your instructor wants you to use?