Difference lists

Hello,

Okay, I've been trying to work out exercise 8.2 (p194), and eventually checked the answer at the back... The answer to defining the add_at_end relation is:

add_at_end(L1 - [Item|Z2], Item, L1 - Z2).

I've read the relevant bits in the book and I simply don't get where the - (minus) comes from. The last paragraph on p185 mentions that the pair of lists would be referred to as L1-L2 for brevity, but I didn't think it was actually Prolog notation. Does L1-L2 make sense programatically? Can we say the following:

?- L1 = [a,b,c,d,e],
L2 = [d,e],
L3 = L1-L2.

Also, when using add_at_end, we need to add a variable at the end like so:

?- add_at_end([a,b,c|T1]-T1, [d,e], L).

T1 = [[d,e] | H759]
L = [a,b,c,[d,e] | H759] - H759

Is there a way to 'neaten' the answer, or will the output always have this form? Is seams to me that although this makes the program more 'efficient', it is no longer 'correct' in that the answer has more information than it should have.

Hi,
I am stil lstruggling with question 2 but did look at rest of the assignment. Doesn't the add_at_end thing just add elements - so instead of pulling off the last 3, you are also adding otehr stuff?

Because you are so far ahead.... for question 2 - the one with the urnary predicate and list with X's in where X is valid for the predictae - where does the list of X's come from?

and the question on male_genes - do we use a database setup as specified in chpt 4 - with the whole family(person (((( ... ))) etc bits or in what format is the "data" in the database?

Thanks
Celene

Hi Celene,

We obviously have 2 different approaches to studying. Personally, I go through all the prescribed material and then have a look at the assignment questions. That's why I'm getting stuck on something in chapter 8. Having said that, I'm also on question 2a of the assignment now, and it seems we're missing an argument. The way I see it we can implement the solution in 2 different ways:

1) Add another argument which is a list of terms to test. The successful terms will make it into the output list.

2) Remove an argument, and write the procedure to test random terms for acceptance, and outputting the results.

I think the 1st option makes more sense.

Question 2b looks like it just requires backtracking through all the X's such that father(X,Y) & male(Y). I haven't implemented it yet but it looks like it's gonna require 2 lists (MaleOnly and NotMaleOnly). All fathers are put onto MaleOnly and once a non-male child is found for them, they are moved to NotMaleOnly. Once the database is exhausted, anyone left in MaleOnly qualifies for male_gene.

Hi

thanks, I will relook at my problems with your suggestions and see if I get anywhere Oh.. I have already gone through all the material.. as well as the assignment questions .. couldn't seem to figure any of them out so decided to start all the way from the beginning again Managed question 1 and 3 so far....

Hi Celene,

Ignore my previous comments about the 2 lists (for 2b). That's just overcomplicated the question. I've solved it now, and the main issue is asking a universal question rather than the default existential. We want to find a father which has only male children, but can't simply ask:

father(X,Y), male(Y).

because we need every Y to be male. That's what you've got to work out... Happy hunting

I am using the free version of Amzi! Prolog 7.4.10, and the syntax involving the minus sign (-), while appearing in the Adventures in Prolog text, simply does not seem to work as described.

I have been unable to get any of the difference list sample code snippets to work. It is holding up my submission of the second assignment. I should probably just let it go, but I would really like to see it in action.

Everyone else find this syntax works just fine?

Hi Mark,

I'd just submit the assignment... Difference lists are not well explained in the book (esp compared to other concepts) and I haven't been able to find any satisfactory examples on the internet. There is an example on p185, as quoted earlier in this post. I've also emailed the lecturers about them, and they don't seem willing to give any further examples of how they work... maybe they don't know either.

The only hope I can see is the solution sheet for the assignment. Maybe then we'll be able to go over the model answer and work out how they work. Good luck...

the - syntax seems to work for me under yap on linux, I couldn't figure out how to actually do anything of use with them though.

As maccaroo says the textbook barely mentions them, and my internet searchs failed to trawl up anything of use either.

In the end I just put a note saying that I could not find satisfactory information to use them, or couldn't with the information I do have on them see how they were usable to sovle the problem asked. Hopefully if enough people get the question wrong/leave it out the lecturer will actually make a point of sending us some notes on it or something.(Or is that just wishfull thinking :/)

Thanks guys,

I will submit on the way home today.
It's odd that it seems a standard language feature, yet refuses to work. It doesn't complain, mind you, it just doesn't work in Amzi! Prolog 7.4.10 (Free Edition) as it should. I wonder if purchasing the Student Edition will unlock this functionality? That's reaching, I'm sure, but I can't see why it shouldn't work. It's in the documentation for Amzi!, so it should be fine.

I hope you're right, Malcolm. I would like to find out why it's not working, and I would like to find a solution to question 7, using difference lists. Without it working at all though, it would be pure guess work.

FYI, when I asked the lecturer about Q7 he had this to say:

"The use of difference lists is efficient if you want to add an element to the back of a list. So difference lists are efficient to implement queues, where you add to the back and retrieve from the front.

However, when you want to get the last element, you still have to traverse the list recursively until you reach the last element and then (in the base case) copy it to the return list. (In Question 7, you have to traverse the list until you reach the last three elements.)"

The point is that I was trying to retrieve the last element using the difference list method. As it appears, difference lists can be used to append an element to the end of a list, but not to retrieve it. To get at the last element we need to use the usual method of traversing the entire list. Hope this helps...

Well thats what I thoght the case was.. But the question specifically states we should use difference lists?
Which is where the confusion comes in.
How then are difference lists at all relavant to the question? why does it specifically say we should use them ;/

Just out of intrest who is the actual lecturer of this subject? I can't seem to find it in the tut101 or on myunisa..

I found the lecturer by logging into myUnisa, going to the section for this module, clicking on E-mail and sending them a message through there. I guess that whoever is available will reply (if there is more than one lecturer).

Yeah I know we can email them through the general module email address, that's rather obvious, I want to know who the lecturer is. IE/ his/her actual name?

The lecturer who e-mailed me was Prof K Britz.

Hi, I also got a reply from Prof K Britz. I didn't eventually submit a long answer for the difference list question - more like a "thing" I thought would work.

I found this assignment a bit wishy washy

And the answers and questions are i nthe downloads section - somewhere I saw them