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:
1
2
3
4
5
6
7
8
9
10
11
12
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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.