# Simulate Prolog backtracking using Scala Stream

It’s a kind of interesting problem. For a bunch of algorithms or data structures,
it is fairly easy and very straight forward using Prolog to solve. And
with backtracking, it is just a matter of `;`

to get next solution and `findall`

to get everything back, or even `findnsols`

to get at most N solutions.

When it comes to Scala (or basically any other non-declarative language), things are a bit of complicated. The fundamental reason is one has to explicitly think about how to compute all solutions.

As an example, let’s take a look at one of the p-99 problems described here, 6.02.

One of the possible Prolog solutions could be:

```
path(G, A, B, P) :-
path(G, A, B, [A], P0),
reverse(P0, P).
path(_, A, A, P, P) :- !.
path(G, A, B, P0, P) :-
neighbour(G, A, N),
\+ memberchk(N, P0),
path(G, N, B, [N|P0], P).
neighbour(graph(_, E), A, N) :-
member(e(A, N), E);
member(e(N, A), E).
```

The above snippet focuses on how to compute one and only one solution and the
backtracking point is generated by `member`

and `;`

.

One can then ask Prolog to compute next, next next solution, …

What would be a Scala simulation of this kind of lazy computation? Naturally
`Stream`

.

```
def neighbours[T](graph: Graph[T], node: T) = {
if (!graph.nodes.contains(node)) Nil
else
graph.edges.collect {
case (x, neighbour) if (x == node) => neighbour
case (neighbour, x) if (x == node) => neighbour
}
}
def path[T](graph: Graph[T], from: T, to: T) = {
def path0[S](graph: Graph[S], from: S, to: S,
visited: List[S]): Stream[List[S]] = {
if (from == to) Stream(List(to))
else
neighbours(graph, from).toStream.filterNot(visited.contains(_)).flatMap { x =>
path0(graph, x, to, from :: visited).map(from :: _)
}
}
path0(graph, from, to, Nil)
}
```

Of course `Stream`

doesn’t ease at all the complexity because one still needs to think
about all solutions explicitly as shown by `flatMap`

. But, it does the lazy computation,
because after computing all neighbours of a node, a `Stream`

is generated and whatever
after that is computed lazily.

As all the other Scala collections, `Stream`

has a lot of functions one can then use to
retrieve solutions.

As I went though p-99 using Scala, this pattern appears over and over again, so it is worth to document.

blog comments powered by Disqus