StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
15104401
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
4
CommunityOwnedDate
CreationDate
2013-02-27T04:46:00.633
FavoriteCount
0
LastActivityDate
2013-02-27T06:51:49.043
LastEditDate
2013-02-27T06:51:49.043
LastEditorUserId
812818
OwnerUserId
812818
ParentId
15101123
PostTypeId
2
Score
3
ViewCount
0
LastEditorDisplayName
text
Body
The problem with a naive solution is that there are an infinite number of ways to get from point A to point B if you don't eliminate cycles. Suppose I want to go from Seattle to San Francisco. Without handling cycles, we're going to get each of these as a unique solution: <pre><code>seattle -> portland -> seattle -> portland -> sanfrancisco seattle -> portland -> seattle -> portland -> seattle -> portland -> sanfrancisco seattle -> (portland -> seattle) x N -> sanfrancisco </code></pre> There's no limit to the number of times you can double back on yourself, so there's effectively an infinite number of solutions once you have as little as three nodes connected. In practice you don't want any solutions where you double back on yourself, but Prolog doesn't know that and there's no intuitive and naive way to prevent it. One of the better ways forward is to simply keep track of where you've been. To do that we're going to need to make the predicate take an extra argument. First I've also introduced a helper predicate. <pre><code>connectedDirectly(From, To) :- nonStopTrain(From, To) ; nonStopTrain(To, From). </code></pre> Having this separated out will reduce the desire to call <code>canTravel</code> recursively when we really just want to attach one more leg to the journey. Now for <code>canTravel</code>: <pre><code>canTravel(From, To) :- canTravel(From, To, []). </code></pre> This is an arity 2 rule that maps onto our new arity 3 rule. The list of places we've been is always empty initially. Now we need a base case: <pre><code>canTravel(From, To, _) :- connectedDirectly(From, To). </code></pre> This should be obvious. Now the inductive case is a little different, because we need to do two things: find a new leg to attach to the journey, make sure we haven't been through that leg before, and then recur, adding the new leg to the list of places we've been. Finally, we want to ensure we don't get large cycles where we end up where we started, so we add a rule to the end to make sure we don't. <pre><code>canTravel(From, To, Visited) :- connectedDirectly(From, Through), \+ memberchk(Through, Visited), canTravel(Through, To, [Through|Visited]), From \= To. </code></pre> Now if you run it you'll find you get 98 solutions and all the solutions are symmetric: <pre><code>?- forall(canTravel(X, Y), (write(X-Y), nl)). sandiego-oceanside lasvegas-sandiego sanfrancisco-bakersfield ... etc. </code></pre> So, happily, we were able to avoid going for a breadth-first search solution. Edit I have apparently confused the situation by overloading the name <code>canTravel</code> for two separate predicates. In Prolog, a predicate is uniquely defined by the name and the arity, much like overloading in C++ or Java where the "effective method" is determined by the number of arguments and the name, not just the name. Your intuition is correct—the empty list in <code>canTravel(From, To) :- canTravel(From, To, [])</code> is establishing an initial binding for the list of visited places. It's not exactly allocating storage so much as establishing a base case. There are really two uses of canTravel inside itself. One of them is calling <code>canTravel/3</code> from <code>canTravel/2</code>. In this case, <code>canTravel/3</code> is really sort of like a helper, doing the actual work of <code>canTravel/2</code>, but with an internal variable that we are initializing to the empty list. The other use is <code>canTravel/3</code> from within <code>canTravel/3</code>, and for that we're both using it to achieve the same goal: recursion, Prolog's primary "looping" construction. The third argument in <code>canTravel(From, To, _) :- connectedDirectly(From, To)</code> is what makes this clause part of <code>canTravel/3</code>. This is the base case of the recursion, so it doesn't need to consider the places we've visited so far (although the inductive case will prevent a circular journey). We could also check it here, but it turns out to be more expensive and have no effect on the resultset: <pre><code>canTravel(From, To, Visited) :- connectedDirectly(From, To), \+ memberchk(To, Visited). </code></pre> I concluded that if it was adding expense and complexity without changing the answers we could omit the check, which reduces the base case to the original one with the anonymous third variable. It may make more sense to see this without the overloading, in which case it looks like this: <pre><code>canTravel(From, To) :- canTravel_loop(From, To, []). canTravel_loop(From, To, _) :- connectedDirectly(From, To). canTravel_loop(From, To, Visited) :- connectedDirectly(From, Through), \+ memberchk(Through, Visited), canTravel_loop(Through, To, [Through|Visited]), From \= To. </code></pre> Edit 2 Regarding the "bar operator," your intuition is once again correct. :) I'm using it here to prepend an item to a list. What's confusing you is that in Prolog, with unification, most expressions express relationships rather than procedures. So depending on the context, <code>[X|Xs]</code> might be used to construct a new list (if you have X and XS in hand) or it might be used to break an implicit list into a head <code>X</code> and tail <code>Xs</code>. Look at all the ways I can use it just from the repl: <pre><code>?- X = hello, Xs = [world, new, user], Y = [X|Xs]. Y = [hello, world, new, user]. </code></pre> This is basically how we're using it in <code>canTravel</code>: we have Through and we have Visited, so we're making a new list with Through first and Visited as the tail, and that's the third parameter to the recursive invocation. In procedural terms, we're just adding Through to a variable we're using in our loop. But because this is Prolog, we're not limited to using things in one direction: <pre><code>?- Y = [hello, world, new, user], Y = [X|Xs]. X = hello, Xs = [world, new, user]. ?- Y = [hello, world, new, user], [X|Xs] = Y. X = hello, Xs = [world, new, user]. </code></pre> Notice that Prolog didn't care which direction the assignment happened in, but it managed to "work backwards" to figure out what X and Xs should be using Y. This is one of the magical things about Prolog. (Note that in the examples in this session I'm omitting the variables which are echoed back because they obscure the point.) In general, you want predicates that can solve for different parameters. For instance, <code>member/2</code> can be used to test membership or to enumerate items. <code>append/3</code> can build a new list from two old lists, or it can enumerate all the ways to split a list into two segments, or it can find a prefix or suffix given a list and a suffix or prefix. As you get more used to this functionality you'll stop thinking of Prolog rules as being like functions in other languages and start to see them as relations: logical "truths" that exist between certain constructions. <code>member/2</code> isn't written by trying to enumerate items or by seeking through a list looking for a particular value. It's implemented by saying: the relation <code>member(Item, List)</code> is true when the Item is the first thing in List: <pre><code>member(Item, [Item|_]). </code></pre> or else when Item is in the remainder of the list: <pre><code>member(Item, [_|Tail]) :- member(Item, Tail). </code></pre> This definition is sufficient for all the possible uses. If <code>Item</code> is not instantiated, it will be instantiated to the first item in the list, then the first item in the tail of that list, and so on. If <code>Item</code> is instantiated, it will be true if Item is the first item in the list or if it is the first item in the tail. Surprisingly, <code>member/2</code> can even be used to generate lists that contain a value: <pre><code>?- member(1, X). X = [1|_G274] ; X = [_G8, 1|_G12] ; X = [_G8, _G11, 1|_G15] . </code></pre> You can see what happened there: the <code>_</code> in the second clause is being made into anonymous variables, so it's generating lists with the 1 in the first position, then the second, then the third, etc. A lot of Prolog works like this. This one is also pretty surprising: <pre><code>?- length(X, 3). X = [_G273, _G276, _G279]. </code></pre> Hope this helps clarify things a bit more! :)
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POSeeing if there is a possible train route through Prolog
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USDaniel Lyons
UserOwnerUserId
1. USDaniel Lyons
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.