Help with a lisp program

[gayelle]

hello!
I am new to lisp and I am trying to figure out DO loops. I simply do not understand how to create them, and I must create a Do function which finds the minimum in a list and also use an if function but i am stuck. Can anyone help?

[smithzv]

Hey, gayelle, show an attempt at solving this problem. Use the "Code" button to format your Lisp source.

[gayelle]

Here is how far along I got in the code. I know that I have to take the first number but I don't know how to compare it to each other value in the list individually...

Code: Select all

(defun minimum (lst)
  "(lst)
return the minimum of a list"
  (do (x lst (cdr x))
      (result 0 (car x))

[gayelle]

I thought of maybe using set f to define two variables and compare them, but i don't know if im on the right track...

Code: Select all

(defun minimum (lst)
  "(lst)
return the minimum of a list"
  (do (x lst (cdr x))
      (setf 'a (car x))
    (setf 'b (car (cdr x))
     

[smithzv]

Okay, it's a start. Let's step back. Describe in plain English what Lisp should do just so we're on the same page.

Here is how far along I got in the code. I know that I have to take the first number but I don't know how to compare it to each other value in the list individually...

Code: Select all

(defun minimum (lst)
  "(lst)
return the minimum of a list"
  (do (x lst (cdr x))
      (result 0 (car x))

As far as your code goes, it isn't actually a well formed expression as the parentheses don't match. That aside, remember that DO has the form

Code: Select all

(do bindings
     stuff-that-determines-when-the-loop-exits-and-what-it-returns
  forms-that-get-run-every-iteration )

The bindings are kind of like a LET form, so in your bindings you are actually setting X to NIL, LST to NIL, and CDR to X. I believe that you also wanted RESULT to get a binding as well. I think you want something more like...

Code: Select all

(do ((x lst (cdr x)) (result 0 (car x))) ...)

Note the placement of parentheses. The "(x lst (cdr x))" bit is a basic idiom for iterating over a list, so good job there.

Code: Select all

(defun minimum (lst)
  "(lst)
return the minimum of a list"
  (do (x lst (cdr x))
      (setf 'a (car x))
    (setf 'b (car (cdr x))

I feel like this is a small step forward. You recognize that you are interested in the relationship between A and B. Think of it this way, how would you write a function that determines if there is an element in the list that is less than a given number (given as an argument). Once you can write that, you are 80% there.

Also, I suspect that you are not working in from of a Lisp system REPL. I suspect this because nothing you have shown can actually be read by a Lisp system. You should be working in front of a REPL.

[smithzv]

Okay, it's a start. Let's step back. Describe in plain English what Lisp should do just so we're on the same page.

Just so I don't seem obnoxious, let me rephrase. Explain it in a more step by step fashion. That is the starting point for any programming. Like if I wanted to find if a particular value was in a list, I would say:

1. Look at the first value in the list.
2. If it equals the item I was looking for, return true, otherwise remove that item and loop back to 1.
3. If the list is ever empty, return false

(Sorry this sounds so recursive, it's just how my brain works)

Also, take a look at the examples at the bottom of the hyperspec DO page. Those things are great for getting a feel of how things work.

[gayelle]

Well for my function I was thinking of it this way,
1. Take the inputted list
2. Assign the first number to the a list and assign the second variable to the b list
3. if a is smaller than b store it in a list, otherwise store b in the list
4. Take the next number and compare it to the list and do the same as step 2 and 3

if that makes any sense

[smithzv]

It makes a some sense. I will give you a few hints, but I have a lot of work to do tonight, so no more posts from me until tomorrow at least.

One thing that is weird about your post, you use the word "list" and I'm not sure why and it's confusing. For instance, a list can never be smaller than another list, unless you are talking about length. Are you talking about the length of each element of the inputted list? I thought we we're talking about numerical value, but it isn't a big deal if we're not, we just need to decide that. I just want to make sure you (and I) have a complete understanding of what you are trying to do.

If we are talking about numerical values, I would rewrite what you said as:

1. Take the inputted list
2. Assign the first element of the list to A and assign the second element of the list to B
3. If A is smaller than B store, store A, otherwise store B (where should you store it?)
4. Take first element out for the list (aka take the CDR of the list) and loop back to 2.
5. If the list is empty, return the minimum you have found (always remember the exit criterion)

This actually will error, but it is nearly correct. There is a bug because we exit when the list is empty, but on the iteration before the list is empty, we get the second value in the list, which doesn't exist (well, technically, it arguably does in Common Lisp, but it has a value of NIL).

STOP HERE until you have decided 100% on what you are attempting to do.

Once you have decided on the process, all you have to do is convert it to Lisp code. Start by copying an example from the spec or class so you at least have something that runs. Then slowly modify it until it performs the algorithm above. You already have figured out how to iterate over a list. Now you have to figure out how to grab the first and second element of the list, compare them (however you need to, perhaps with the < function), store the lesser, then loop back. Then you should make sure your termination clause is setup correctly. For the second form in your DO construct, you need to define an exit criterion and a return value.

STOP HERE until you have something that runs and produces a correct output.

Then, although it might not be necessary for class, you should look at what you have written and see what you could have written more clearly or cleanly. Of course, as others have noted, DO loops are not known for their clarity and thus there are limited gains here.

[wvxvw]

I'm sorry to maybe spoil the didactic effect but you could try looking into reduce function, it takes a function reference and a list as it's parameters and applies the function to every two consequent elements of the list (very much like you intended to do that in the do loop) and returns the result returned by the function provided in arguments. So, since you've minimized your problem to only finding the smallest number of the two numbers in the list, the function will break the longer list into these smaller samples - voila

[gayelle]

i finally got it. I defined a seperate function that compare x and y and plugged it into the minimum function! thanks so much for all the help