LinuxQuestions.org
Register a domain and help support LQ
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices



Reply
 
Search this Thread
Old 06-25-2010, 09:29 AM   #1
steve296
LQ Newbie
 
Registered: Jun 2010
Location: Hungary
Distribution: ubuntu
Posts: 9

Rep: Reputation: 1
Anyone know Prolog? Need halp


Hello,

I just registered into this forum, been using linux (ubuntu) for over a year now - am happy with it too! -, and I'm trying to spend this summer to learn more* on programming right before I go to uni, where they would teach it anyways ...

*more than the basics of Pascal, which I was taught in secondary

So, my problem is that I've been reading a prolog introductory book, and in it was an exercise which I have failed to solve thus far - which continued for days, now.

Here's the riddle:

Quote:
Binary trees are trees where all internal nodes have exactly two childres. The smalles binary trees consist of only one leaf node. We will represent leaf nodes as leaf(Label). For instance, leaf(3) and leaf(7) are leaf nodes, and therefore small binary trees. Given two binary trees B1 and B2 we can combine them into one binary tree using the predicate tree: tree(B1,B2). So, from the leaves leaf(1) and leaf(2) we can build the binary tree tree(leaf(1), leaf(2)). And from the binary trees tree(leaf(1), leaf(2)) and leaf(4) we can build the binary tree tree(tree(leaf(1), leaf(2)), leaf(4)).

Now, define a predicate swap/2, which produces a mirror image of the binary tree that is its first argument. For example:
Code:
?- swap(tree(tree(leaf(1), leaf(2)), leaf(4)),T).
T = tree(leaf(4), tree(leaf(2), leaf(1))).
yes
What I could achieve, is building the rules of a binary tree in a most complicated way; but prolog cannot follow those rules to generate binary trees by querying him like this:
Code:
?- tree(X, Y).
Instead it only writes 'yes' (or 'true', for I use SWI-Prolog). If I to do the swap/2 part, it would switch the leaf(4) with tree(leaf(2), leaf(1)), but not within tree(leaf(2), leaf(1)).

If there's a resident Prolog guru lurking around here, I'd appreciate his/her help. Thanks in advance.

steve296

EDIT: my problem, more specifically said, is that I cannot make the predicate for binary trees with 2 nodes and the predicate for the single leaf node, which still counts as a tree, count as equal. Namely, tree/2 and tree/1 are two different things for prolog. Which means that I can only represent complex trees using these specific rules:
Code:
tree(leaf(Label)).
tree(B1, B2) :-
	tree(B1),
	tree(B2).
tree(B1, B2) :-
	tree(B1),
	B2 = tree(B3, B4).
tree(B1, B2) :-
	B1 = tree(B3, B4).
	tree(B2).
tree(B1, B2) :-
	B1 = tree(B3, B4),
	B2 = tree(B3, B4).
But for some reason I believe there must be a better way to describe this.

Last edited by steve296; 06-25-2010 at 12:41 PM. Reason: specificism
 
Old 06-26-2010, 03:07 AM   #2
paulsm4
Guru
 
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Blog Entries: 1

Rep: Reputation: Disabled
Wow - AFAIK, Prolog isn't exactly a great language for data structures and algorithms...


ANYWAY, a Google search of "prolog data structures trees queues" turned up this:

http://www.ece.uc.edu/~annexste/Cour...lognotes1.html

and this:

http://download.pdc.dk/vip/72/books/...gBeginners.pdf

'Hope that helps .. PSM

Last edited by paulsm4; 06-26-2010 at 03:09 AM.
 
Old 06-26-2010, 11:45 AM   #3
ArthurSittler
Member
 
Registered: Jul 2008
Distribution: Slackware
Posts: 124

Rep: Reputation: 30
It was a long time ago

<edit> Please see following post </edit>
I have not used Prolog professionally. I had a brief encounter with it in school. That was a long time ago.
I have not tested this, but I think you could implement swap something like this:
Code:
swap( leaf(Leaf), leaf(Leaf) ).
swap( tree(Left,Right), tree( swap(Right), swap(Left) ).

Last edited by ArthurSittler; 06-26-2010 at 02:54 PM. Reason: Suggestion was way off base.
 
Old 06-26-2010, 12:02 PM   #4
steve296
LQ Newbie
 
Registered: Jun 2010
Location: Hungary
Distribution: ubuntu
Posts: 9

Original Poster
Rep: Reputation: 1
Right...

Quote:
Originally Posted by paulsm4 View Post
Wow - AFAIK, Prolog isn't exactly a great language for data structures and algorithms...


ANYWAY, a Google search of "prolog data structures trees queues" turned up this:

http://www.ece.uc.edu/~annexste/Cour...lognotes1.html

and this:

http://download.pdc.dk/vip/72/books/...gBeginners.pdf

'Hope that helps .. PSM
Ummm... the thing I posted here isn't something specific, like classes, polimorphism and other stuff I read when I skimmed through a C++ book; they are just predicates. Rules, facts, clauses. They're as fundamental as variables in imperative languages. What I'm trying to say, is that by searching for something like 'data structures', or 'trees', won't help me much, because these are just labels. One could name their predicates and their arguments anything, like cat(tom, bob), or tree(leaf(1), leaf(2)); they don't mean anything, even the logical link is only in your head (in the sense that mother(caroline, ryan) and mother(ryan, caroline) may mean the same in different programs, if used consistently). But thanks anyway .

Sorry for going overboard about prolog, oh, and if a more adept initiated is reading this, feel free to smack me in the head for being so sloppy .

I'll be thinking about this more later, and post the solution for those who may be reading the same (free&online) book and stumble onto the same problem.

Last edited by steve296; 06-26-2010 at 12:03 PM. Reason: forgot quoting
 
Old 06-26-2010, 01:56 PM   #5
paulsm4
Guru
 
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Blog Entries: 1

Rep: Reputation: Disabled
Hi, steve296 -
Quote:
the thing I posted here isn't something specific,
That's for sure
Quote:
stuff I read when I skimmed through a C++ book ... like classes ... variables ...
You're absolutely correct:

* "Imperative, object-oriented languages" like C++, Java and C# have classes, variables, operations, control structures and other fundamental "building blocks" from which you can build higher-level constructs like trees, queues and, ultimately, applications and systems.

* "Declarative languages" like Prolog, on the other hand, have predicates, variables, lists, etc as their "fundamental building blocks". From which you can ALSO build higher-level constructs like trees, queues and, ultimately, applications and - who knows - maybe even full-blown systems.

The point is that Googling for something like "prolog data structures trees queues" CAN give you concrete examples for how to use Prolog syntax to build a logical "tree" data structure.

Just like the examples I cited, or the example ArthurSittler gave you.

Good luck - and have fun!

Sincerely .. PSM
 
Old 06-26-2010, 02:51 PM   #6
ArthurSittler
Member
 
Registered: Jul 2008
Distribution: Slackware
Posts: 124

Rep: Reputation: 30
Oops

I looked at Clocksin & Mellish.
I think the swap should look a bit more like
Code:
swap( L, R ) :-
    L = leaf( X ),
    R = leaf( Y ),
    Y = X.
swap( L, R ) :-
    L = tree( LL, LR ),
    R = tree( RL, RR ),
    RL = swap( LR ),
    RR = swap( LL ).
This is also untested. I do not have Prolog installed on this machine.
I do have Prolog (gprolog) installed on another machine. I have never used it. I may need your help learning how to use it.

I do not remember if Prolog permits defining two different functors with the same name but different arity, as in the following:
tree( Leaf )
tree( LTree, RTree )

Last edited by ArthurSittler; 06-26-2010 at 08:35 PM. Reason: a bit more care
 
Old 06-27-2010, 06:45 AM   #7
steve296
LQ Newbie
 
Registered: Jun 2010
Location: Hungary
Distribution: ubuntu
Posts: 9

Original Poster
Rep: Reputation: 1
Sorry...

Quote:
Originally Posted by paulsm4
The point is that Googling for something like "prolog data structures trees queues" CAN give you concrete examples for how to use Prolog syntax to build a logical "tree" data structure.

Just like the examples I cited, or the example ArthurSittler gave you.
Oh... sorry for being mean, then. I'll read through them thoroughly this time...

@ArthurSittler

Prolog does permit functors with the same name but with different arities, it's just that they count as different functors. I've tested the swap you posted, and after giving
Code:
    RL = swap( LR ),
    RR = swap( LL ).
one more variable as argument (prolog didn't have rules for swap/1):
Code:
    RL = swap( LR, LR2 ),
    RR = swap( LL, LL2 ).
it replied like this:
Code:
?- swap(tree(tree(leaf(1), leaf(2)), leaf(4)),T).
T = tree(swap(leaf(4), _G305), swap(tree(leaf(1), leaf(2)), _G308)).
Btw, I'm trying to advance your idea of recursion (that's the whole purpose of this exercise in the book - I just couldn't find a way to make it recursive). I'll post my results shortly.

[1-2 hrs after I forgot to send this post:]

I found it, finally. It's not pretty, because it covers all possibilities of how could a tree look like (e.g. tree(leaf(1)) or tree(leaf(1), leaf(2))). Anyways, the source code is in the attachment. What the swap part does is that it first checks whether the tree() has any nodes which have even more nodes (first predicate becomes true when it's a simple tree, with no internal nodes; second and third predicate becomes true when either the first or the second node of the main tree has nodes; fourth when both nodes of main tree() have nodes of their own). Then it tries t swap the internal nodes (if any), and finally swaps the two nodes of the main tree(). And this is recursive.

Thanks for both of your help, I was taught a small lesson in both programming and ethics

EDIT: I made a slight change to the file, found a small error in it (size is 1.2KB now).
Attached Files
File Type: txt binarytree.txt (1.2 KB, 21 views)

Last edited by steve296; 06-27-2010 at 07:28 AM.
 
1 members found this post helpful.
Old 06-27-2010, 03:35 PM   #8
ArthurSittler
Member
 
Registered: Jul 2008
Distribution: Slackware
Posts: 124

Rep: Reputation: 30
If it isn't verified, it does not work.

Thank you, steve296.
After I installed Prolog, I was unable to get my proposed solution to work. In my defense, my brush with Prolog was very brief, and it was a long time ago. You have inspired me to refresh my Prolog skills. Do not be surprised if you get a question or two from me about Prolog in the near future.
 
Old 06-27-2010, 03:57 PM   #9
paulsm4
Guru
 
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Blog Entries: 1

Rep: Reputation: Disabled
Steve296 -

As ArthurSittler already mentioned, "Programming in Prolog", by Clocksin and Mellish is *the* resource for learning Prolog:

http://www.amazon.com/Programming-Pr...dp/3540006788/

IMHO .. PSM
 
Old 06-27-2010, 06:00 PM   #10
steve296
LQ Newbie
 
Registered: Jun 2010
Location: Hungary
Distribution: ubuntu
Posts: 9

Original Poster
Rep: Reputation: 1
Quote:
Originally Posted by ArthurSittler
Thank you, steve296.
After I installed Prolog, I was unable to get my proposed solution to work. In my defense, my brush with Prolog was very brief, and it was a long time ago. You have inspired me to refresh my Prolog skills. Do not be surprised if you get a question or two from me about Prolog in the near future.
Cool . I'm glad you found something to rediscover and cherish. Just don't let the notion vanish, though . And I'll be welcoming any question or thought about prolog, or anything for that matter.

Quote:
Originally Posted by paulsm4
Steve296 -

As ArthurSittler already mentioned, "Programming in Prolog", by Clocksin and Mellish is *the* resource for learning Prolog:

http://www.amazon.com/Programming-Pr...dp/3540006788/

IMHO .. PSM
Thank you for the references, now I'll be sure to have more books on the list than I can read this summer . Lets see.. C/C++, bash, python, prolog.....
 
Old 07-21-2010, 03:47 PM   #11
Innar Made
LQ Newbie
 
Registered: Jul 2010
Location: Estonia, Tallinn
Distribution: Debian Lenny
Posts: 1

Rep: Reputation: 1
I know this question is already solved, but I paste my solution too as I think it would be good for future reference.

Code:
swap(leaf(X),Y) :- Y = leaf(X).
swap(tree(X,Y),Z) :- swap(X,Xs), swap(Y,Ys), Z = tree(Ys,Xs).
Regards,
Innar
 
1 members found this post helpful.
  


Reply

Tags
beginner, help, recursive


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Need halp with rpmbuild command Monkey Man Fedora 3 10-06-2006 09:10 PM
Please halp I can't compile c++ file malb Linux - Newbie 9 07-25-2005 07:52 PM
Prolog Help with if-then-else-else if?? magicvash Programming 1 05-27-2005 10:31 AM
font problems, halp mrb Linux - Newbie 1 05-15-2004 02:12 PM


All times are GMT -5. The time now is 09:41 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration