Category Archives: Mercury

Escape from Zurg

This Lambda the Ultimate post links to a paper which compares writing a search algorithm in Prolog and Haskell, and notes that Haskell’s strong typing makes the task easier. While the paper mentions several embeddings of logic programming into functional languages it doesn’t mention Mercury.

I was able to easily create successor and goal predicates for [...]

A Generic ’solve’ Predicate

The examples of state space searching described previously have all been tailored to a particular problem — the algorithms have been general, but the implementation has included type signatures specific to the problem, e.g.:

:- type block —> a; b; c. :- type stack == list(block). :- type situation == list(stack). :- type solution == list(situation). :- pred solve(situation::in, solution::out) [...]

Breadth First Search

One disadvantage of the depth first search with iterative deepening is that it regenerates all the search paths from the start node every iteration. A true breadth first search, as described by Bratko on pages 250-252 doesn’t need to do that — it can start with a short search path (just the start node in [...]

Depth First Search in Mercury—with Iterative Deepening

Our last algorithm gave us a result much longer than the shortest possible. We can improve that by generating first all paths of length one, then two and so on, until we find one which reaches a goal state.

Bratko describes this on pages 248 and 249.

This version arrives at the optimal solution:

[[[c, a, b], [], [...]

Depth First Search in Mercury—with Cycle Detection

The algorithm implemented in my previous post pays no attention to the nodes in the search space already visited, so if the situation [[c,a,b],[],[]] is used as the starting point an infinite recursion will result, as the successor function starts to traverse a cycle in the state space graph before it finds a goal node.

On [...]

Depth First Search in Mercury

I’m working through Bratko’s “Prolog Programming for Artificial Intelligence” rewriting the examples in Mercury.This series of posts will be my notes on the changes I needed to make to make these programs work.Page 243-244, defining successor states for stacks of blocks and performing a depth first search. Note that it’s a naive depth first search [...]