[mercury-users] A thought on state variables and the library
doug.auclair at logicaltypes.com
doug.auclair at logicaltypes.com
Thu Feb 15 15:25:14 AEDT 2007
Dear all,
A few of the previous posts have stated the preference of using
state variables over DCGs. This brings to my mind an unrelated
issue: many of the modules in the standard library have redundant
sv<foo> module equivalents.
In my day-to-day usage, I prefer using the sv<foo> module over
its (Prolog-y?) <foo> version; so I'm thinking, with the current
emphasis on sv usage, that now is a good time to "cut the chord"
of Prolog "compatibility" and consolidate all sv<foo> and <foo>
module pairs into just one module per type with the predicates
in the sv style.
I think this will help the new user, as it reduces the bewildering
number of module options for a data type (bewildering == "more
than one", and sometimes the standard library has more than three
such options) as well as reinforce the sv style and usage.
-----
On that note, I'd like to submit svgraph -- graph has the Prolog-y
foo(XIn, arg, arg, Xout) style, and also has a very naive (read: inefficient)
pathing algorithm. svgraph is in the sv style and adds some alternate
pathing options. Under my proprosal above svgraph, svmap, sv<foo>
would replace graph, map, <foo>, slimming down and unifying the
standard library under the sv style.
-----
Here I would also like to note that the refman has, as the Melbourne
team views it, inappropriate DCG usage (e.g.: sect 8.1, 10.2, 10.7), the
(Prolog) transition guide (e.g.: sect 3), and the compiler sources use
DCGs in 28 modules in compiler/ (some is of course appropriate for
parsing tasks ... but not all), and these uses in manuals and sources
may mislead some to use DCGs in ways that the Melbourne Mercury
team dislikes ... which makes it rather confusing receiving criticism for
DCG usage from a group that publishes manuals using the same DCG
style in the same situations ... HTH.
svgraph follows below.
Sincerely,
Doug Auclair
%---------------------------------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
%---------------------------------------------------------------------------%
% Copyright (C) 1994-1999, 2003, 2005-2006 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%---------------------------------------------------------------------------%
%
% File: svgraph.m.
% Main author: conway.
% Stability: low.
%
% This module defines a directed graph data type. The type graph(N, A)
% stores information of type N in the nodes, and information of type A
% in the arcs.
%
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%
:- module svgraph.
:- interface.
:- import_module list.
:- import_module map.
:- import_module set.
:- import_module unit.
% graph(Node, Arc) represents a directed graph with information of
% type Node associated with each node, and information of type Arc
% associated with each arc.
%
:- type graph(N, A).
:- type node(N).
:- type arc(A).
% Lots of graphs don't need to store anything in the arcs so here's
% a type equivalence that only has `real' information in the nodes.
%
:- type graph(N) == graph(N, unit).
:- type arc == arc(unit).
% svgraph.init = Graph binds Graph to an empty graph containing no nodes
% and no arcs. (The graph contains a counter of the number of nodes
% allocated in it, so it is possible for a graph to contain no nodes
% or arcs and still fail to unify with the binding of Graph from
% svgraph.init.)
%
:- func svgraph.init = graph(N, A).
% svgraph.set_node(NodeInfo, Node, !Graph) takes
% !.Graph and NodeInfo which is the information to be stored
% in a new node, and returns a key "Node" which refers to that
% node, and the new graph !:Graph containing all of the nodes
% and arcs in !.Graph as well as the new node.
% It is possible to have two nodes in the graph with the
% same information stored in them.
%
% This operation is O(lgN) for a graph containing N nodes.
%
:- pred svgraph.set_node(N::in, node(N)::out,
graph(N, A)::in, graph(N, A)::out) is det.
% svgraph.insert_node/4 is the same as svgraph.set_node/4 except
% that if the information to be stored in the node is stored
% in another node, then the svgraph.insert_node/4 fails.
%
% This operation is O(N) for a graph containing N nodes since
% this predicate has to check that the node data isn't in an
% existing node.
%
:- pred svgraph.insert_node(N::in, node(N)::out,
graph(N, A)::in, graph(N, A)::out) is semidet.
% svgraph.det_insert_node/4 is like svgraph.insert_node, except
% that if the insertion would fail, it calls error/1.
%
:- pred svgraph.det_insert_node(N::in, node(N)::out,
graph(N, A)::in, graph(N, A)::out) is det.
% svgraph.search_node(Graph, NodeInfo, Node) nondeterministically
% produces bindings of Node such that Node is a node in Graph
% that has the information NodeInfo attatched to it.
%
% This operation is O(lgN) for the first solution for a graph
% containing N nodes.
%
:- pred svgraph.search_node(graph(N, A)::in, N::in, node(N)::out) is nondet.
% svgraph.find_matching_nodes(Graph, NodeInfo, Nodes) takes a graph
% Graph and the information NodeInfo and returns the set of nodes
% Nodes which have the information NodeInfo stored in them. (The set
% Nodes will of course be empty if there are no matching nodes.)
%
% This operation is O(NlgN) for a graph containing N nodes.
%
:- func svgraph.find_matching_nodes(graph(N, A), N) = set(node(N)).
% svgraph.node_contents(Graph, Node, NodeInfo) takes Graph and
% Node and returns the information NodeInfo stored in Node.
%
% This operation is O(lgN) for a graph containing N nodes.
%
:- func svgraph.node_contents(graph(N, A), node(N)) = N.
% svgraph.successors(Graph, Node, Nodes) takes a graph Graph and
% a node Node and returns the set of nodes Nodes that are reachable
% (directly - not transitively) from Node.
%
% This operation is O(NlgN) for a graph containing N nodes.
%
:- func svgraph.successors(graph(N, A), node(N)) = set(node(N)).
:- func svgraph.successors_with_arcs(graph(N, A), node(N))
= map(arc(A), node(N)).
% svgraph.nodes(Graph, Nodes) binds Nodes to the set of nodes in Svgraph.
%
:- func svgraph.nodes(graph(N, A)) = set(node(N)).
% svgraph.set_edge(OldGraph, Start, End, ArcInfo, Arc, NewGraph)
% takes a graph OldGraph and adds an arc from Start to End with
% the information ArcInfo stored in it, and returns a key for
% that arc Arc, and the new graph NewSvgraph.
% If an identical arc already exists then this operation has
% no effect.
%
% This operation is O(lgN+lgM) for a graph with N nodes and M arcs.
%
:- pred svgraph.set_edge(node(N)::in, node(N)::in, A::in, arc(A)::out,
graph(N, A)::in, graph(N, A)::out) is det.
% svgraph.insert_edge/6 is the same as svgraph.set_edge/6 except that
% if an identical arc already exists in the graph the operation fails.
% This is O(N) for a graph with N edges between the two nodes.
%
:- pred svgraph.insert_edge(node(N)::in, node(N)::in, A::in, arc(A)::out,
graph(N, A)::in, graph(N, A)::out) is semidet.
% svgraph.det_insert_edge/6 is like svgraph.insert_edge except
% than instead of failing, it calls error/1.
%
:- pred svgraph.det_insert_edge(node(N)::in, node(N)::in, A::in, arc(A)::out,
graph(N, A)::in, graph(N, A)::out) is det.
% svgraph.arc_contents(Graph, Arc, Start, End, ArcInfo) takes a
% graph Graph and an arc Arc and returns the start and end nodes
% and the information stored in that arc.
%
:- pred svgraph.arc_contents(graph(N, A)::in, arc(A)::in,
node(N)::out, node(N)::out, A::out) is det.
% svgraph.path(Graph, Start, End, Path) is true iff there is a path
% from the node Start to the node End in Graph that goes through
% the sequence of arcs Arcs.
% The algorithm will return paths containing at most one cycle.
:- pred svgraph.path(graph(N, A), node(N), node(N), list(arc(A))).
:- mode svgraph.path(in, in, in, out) is nondet.
:- mode svgraph.path(in, in, out, out) is nondet.
% provides a facade to different search strategies (cyclical
% verses noncyclical; breath-first verses depth-first)
:- pred svgraph.path(search_strategy, graph(N, A), node(N),
node(N), list(arc(A))).
:- mode svgraph.path(in, in, in, in, out) is nondet.
:- mode svgraph.path(in, in, in, out, out) is nondet.
:- type svgraph.search_strategy
---> aggressive; passive(cycling).
:- type svgraph.cycling ---> no_cycles; at_most_one_cycle.
% '"best"_path'/5 currently takes the brute-force approach --
% it arbitrarily picks the first path, and then uses its
% associated cost as a starting point to find, eventually, the
% least expensive path. The default is unit cost per arc.
% It should be noted in passing that, operationally, this
% '"best"_path'/5 is more than 100 times faster than a naive
% approach on a graph of 63 nodes and 174 arcs because it
% prunes away failing paths inline (as opposed to eliminating
% a failing path after it's fully realized).
:- pred best_path(search_heuristic(N, A), graph(N, A), node(N),
node(N), list(arc(A))).
:- mode best_path(in, in, in, in, out) is nondet.
:- mode best_path(in, in, in, out, out) is nondet.
% :- type cost_fn == some [N, A] (func(graph(N, A), arc(A)) = int).
:- mode cost_fn_in == in(func(in, in) = out is det).
% The search_heuristic gives a way to look for the best path
% (aggressive or one of the passive approaches) and a function
% that computes the cost of traversing each arc of the path
% (the default cost function is that each arc has unit cost).
:- type search_heuristic(N, A)
---> search_heuristic(search_strategy, (func(graph(N, A), arc(A)) = int))
; default_cost_search_heuristic(search_strategy).
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%
:- implementation.
:- import_module assoc_list.
:- import_module counter.
:- import_module int.
:- import_module list.
:- import_module pair.
:- import_module require.
:- import_module string.
:- use_module solutions.
%---------------------------------------------------------------------------%
:- type graph(N, A)
---> graph(
node_supply :: counter,
arc_supply :: counter,
node_map :: map(node(N), N),
arc_map :: map(arc(A), arc_info(N, A)),
edge_map :: map(node(N), map(arc(A), node(N)))
).
:- type node(N)
---> node(int).
:- type arc(A)
---> arc(int).
:- type arc_info(N, A)
---> arc_info(node(N), node(N), A).
%---------------------------------------------------------------------------%
svgraph.init = graph(counter.init(0), counter.init(0), Nodes, Arcs, Edges) :-
map.init(Nodes),
map.init(Arcs),
map.init(Edges).
%---------------------------------------------------------------------------%
svgraph.set_node(NInfo, node(N), !G) :-
NS0 = !.G ^ node_supply,
counter.allocate(N, NS0, NS),
!:G = !.G ^ node_supply := NS,
Nodes0 = !.G ^ node_map,
map.set(Nodes0, node(N), NInfo, Nodes),
!:G = !.G ^ node_map := Nodes,
Edges0 = !.G ^ edge_map,
map.init(EdgeMap),
map.set(Edges0, node(N), EdgeMap, Edges),
!:G = !.G ^ edge_map := Edges.
svgraph.det_insert_node(NInfo, N, !G) :-
( svgraph.insert_node(!.G, NInfo, NPrime, !:G) ->
N = NPrime
;
error("svgraph.det_insert_node: node already exists.")
).
svgraph.insert_node(NInfo, node(N), !G) :-
% Make sure that the graph doesn't contain NInfo already.
\+ map.member(!.G ^ node_map, _, NInfo),
NS0 = !.G ^ node_supply,
counter.allocate(N, NS0, NS),
!:G = !.G ^ node_supply := NS,
Nodes0 = !.G ^ node_map,
map.set(Nodes0, node(N), NInfo, Nodes),
!:G = !.G ^ node_map := Nodes,
Edges0 = !.G ^ edge_map,
map.init(EdgeSet),
map.set(Edges0, node(N), EdgeSet, Edges),
!:G = !.G ^ edge_map := Edges.
%---------------------------------------------------------------------------%
svgraph.search_node(Graph, NodeInfo, Node) :-
NodeTable = Graph ^ node_map,
map.member(NodeTable, Node, NodeInfo).
%---------------------------------------------------------------------------%
svgraph.find_matching_nodes(Graph, NodeInfo) = NodeSet :-
NodeTable = Graph ^ node_map,
solutions.solutions(svgraph.select_node(NodeTable, NodeInfo), NodeList),
set.sorted_list_to_set(NodeList, NodeSet).
:- pred svgraph.select_node(map(node(N), N)::in, N::in, node(N)::out) is nondet.
svgraph.select_node(NodeTable, NodeInfo, Node) :-
map.member(NodeTable, Node, NodeInfo).
%---------------------------------------------------------------------------%
svgraph.node_contents(G, N) = I :-
map.lookup(G ^ node_map, N, I).
%---------------------------------------------------------------------------%
svgraph.successors(G, N) = Ss :-
map.values(successors_with_arcs(G, N), SsList),
set.list_to_set(SsList, Ss).
svgraph.successors_with_arcs(G, N) = SnAs :-
map.lookup(G ^ edge_map, N, SnAs).
%---------------------------------------------------------------------------%
svgraph.nodes(G) = Ns :-
map.keys(G ^ node_map, Ns1),
set.list_to_set(Ns1, Ns).
%---------------------------------------------------------------------------%
svgraph.set_edge(Start, End, Info, Arc, !G) :-
AS0 = !.G ^ arc_supply,
counter.allocate(A, AS0, AS),
Arc = arc(A),
!:G = !.G ^ arc_supply := AS,
Arcs0 = !.G ^ arc_map,
map.set(Arcs0, Arc, arc_info(Start, End, Info), Arcs),
!:G = !.G ^ arc_map := Arcs,
Es0 = !.G ^ edge_map,
map.lookup(Es0, Start, EdgeMap0),
map.set(EdgeMap0, Arc, End, EdgeMap),
map.set(Es0, Start, EdgeMap, Es),
!:G = !.G ^ edge_map := Es.
%---------------------------------------------------------------------------%
svgraph.det_insert_edge(Start, End, Info, Arc, !G) :-
( svgraph.insert_edge(Start, End, Info, ArcPrime, !G) ->
Arc = ArcPrime
;
error("svgraph.det_insert_edge: this edge is already in "
++ "the svgraph.")
).
svgraph.insert_edge(Start, End, Info, Arc, !G) :-
AS0 = !.G ^ arc_supply,
counter.allocate(A, AS0, AS),
Arc = arc(A),
!:G = !.G ^ arc_supply := AS,
Arcs0 = !.G ^ arc_map,
map.insert(Arcs0, Arc, arc_info(Start, End, Info), Arcs),
!:G = !.G ^ arc_map := Arcs,
Es0 = !.G ^ edge_map,
map.lookup(Es0, Start, EdgeMap0),
map.set(EdgeMap0, Arc, End, EdgeMap),
map.set(Es0, Start, EdgeMap, Es),
!:G = !.G ^ edge_map := Es.
%---------------------------------------------------------------------------%
svgraph.arc_contents(G, N, S, E, A) :-
map.lookup(G ^ arc_map, N, I),
I = arc_info(S, E, A).
%---------------------------------------------------------------------------%
% passive_search/5 takes the purely declarative approach to
% locating a path from some (ground) Start to an eventual
% (ground or free) End. It ignores any operational realities,
% so it can take a bit of time to discover a path for anything
% other than simple graphs ... on the other hand, the
% algorithm is straightforward and easy to comprehend.
:- pred passive_search(map(node(N), map(arc(A), node(N))), node(N), node(N),
list(node(N)), list(arc(A))).
:- mode passive_search(in, in, in, in, out) is nondet.
:- mode passive_search(in, in, out, in, out) is nondet.
passive_search(Map, S, E, Nodes0, Path) :-
map.lookup(Map, S, Arcs),
(map.member(Arcs, A, E),
% \+ list.member(E, Nodes0), % DMA: superfluous
Path = [A]
;
map.member(Arcs, A, N),
\+ list.member(N, Nodes0),
passive_search(Map, N, E, [N | Nodes0], Path0),
Path = [A | Path0]).
% aggressive_search/4 takes a more directed approach to
% finding a path from Start to End (actually, back from End to
% Start): instead of picking any arbitrary next node, it
% (aggressively) attempts to link to Start at every turn.
:- pred aggressive_search(graph(N, A), node(N), list(node(N)), list(arc(A))).
:- mode aggressive_search(in, in, in(non_empty_list), out) is nondet.
aggressive_search(Graph, From, Nodes@[Node|_Nodes], Path) :-
From = Node ->
cons_path(Graph, Nodes, [], Path)
;
(member(From, successors(Graph, Node)) ->
cons_path(Graph, [From|Nodes], [], Path)
;
member(Pre, successors(Graph, Node)),
not member(Pre, Nodes),
aggressive_search(Graph, From, [Pre|Nodes], Path)).
:- pred cons_path(graph(N, A), list(node(N)), list(arc(A)), list(arc(A))).
:- mode cons_path(in, in(non_empty_list), in, out) is det.
cons_path(Graph, [A|Nodes], !Arcs) :-
[B|Rest] = Nodes,
successors_with_arcs(Graph, A) = Map,
search(reverse_members(to_assoc_list(Map)), B, Arc) ->
cons(Arc, !Arcs),
(Rest = [] -> reverse(!Arcs); cons_path(Graph, Nodes, !Arcs))
;
error("Cannot reconstruct path from nodes collected!\n"
++ string([A|Nodes])).
svgraph.path(G, S, E, Path) :-
passive_search(G ^ edge_map, S, E, [], Path).
svgraph.path(passive(at_most_one_cycle), Graph, From, To, Ans) :-
passive_search(Graph ^ edge_map, From, To, [], Ans).
svgraph.path(passive(no_cycles), Graph, From, To, Ans) :-
passive_search(Graph ^ edge_map, From, To, [From], Ans).
svgraph.path(aggressive, Graph, From, To, Ans) :-
freeze(From, To, Graph),
aggressive_search(Graph, From, [To], Ans).
best_path(Huey, Graph, From, To, Ans) :-
Searcher = heuristic_strategy(Huey),
path(Searcher, Graph, From, To, Guess),
CostFn = transit_cost_fn(Huey),
TotalCost
= foldl((func(X, Y) = Z :- Z = CostFn(Graph, X) + Y), Guess, 0),
get_shortest_path(Searcher, CostFn, Graph, From, To,
TotalCost, Guess, Ans).
:- func heuristic_strategy(search_heuristic(N, A)) = search_strategy.
heuristic_strategy(search_heuristic(Strat, _)) = Strat.
heuristic_strategy(default_cost_search_heuristic(Strat)) = Strat.
:- func transit_cost_fn(search_heuristic(N, A)) = (func(graph(N, A),
arc(A)) = int).
transit_cost_fn(search_heuristic(_, Fn)) = Fn.
transit_cost_fn(default_cost_search_heuristic(_)) = (func(_, _) = 1).
:- pred get_shortest_path(search_strategy,
(func(graph(N, A), arc(A)) = int), graph(N, A),
node(N), node(N), int, list(arc(A)), list(arc(A))).
:- mode get_shortest_path(in, cost_fn_in, in, in, in, in, in, out) is nondet.
get_shortest_path(Searcher, CostFn, Map, From, To, Cost, Guess, Ans) :-
path(Searcher, CostFn, Map, From, dying_at(Cost),
[To], NewGuess, 0, NewCost) ->
get_shortest_path(Searcher, CostFn, Map, From, To,
NewCost, NewGuess, Ans)
;
Ans = Guess.
:- type swan ---> dying_at(int).
:- pred path(search_strategy, (func(graph(N, A), arc(A)) = int),
graph(N, A), node(N), swan, list(node(N)), list(arc(A)),
int, int).
:- mode path(in, cost_fn_in, in, in, in, in(non_empty_list),
out, in, out) is nondet.
path(Search, CostFn, Graph, From, dying_at(Max),
Nodes@[Mid|_], Ans, CostIn, CostOut) :-
CostIn < Max - 1,
(From = Mid ->
cons_path(Graph, Nodes, [], Ans),
CostIn = CostOut
;
a_successor(Search, successors_with_arcs(Graph, Mid),
From, Node, Arc),
not member(Node, Nodes),
CostTmp = CostIn + CostFn(Graph, Arc),
path(Search, CostFn, Graph, From, dying_at(Max),
[Node|Nodes], Ans, CostTmp, CostOut)).
:- pred a_successor(search_strategy::in, map(arc(A), node(N))::in,
node(N)::in, node(N)::out, arc(A)::out) is nondet.
a_successor(aggressive, Map, From, Next, Arc) :-
Nodelist = reverse_members(to_assoc_list(Map)),
(search(Nodelist, From, McDo) ->
Next = From,
Arc = McDo
;
member(Next - Arc, Nodelist)).
a_successor(passive(_), Map, _From, Next, Arc) :-
member(Map, Arc, Next).
:- pred freeze(node(N), node(N), graph(N, A)).
:- mode freeze(in, in, in) is semidet.
:- mode freeze(in, out, in) is nondet.
freeze(From::in, To::in, _::in) :- not From = To.
freeze(From::in, To::out, Graph::in) :-
delete(nodes(Graph), From, RestNodes),
member(To, RestNodes).
:- pragma promise_equivalent_clauses(freeze/3).
%--------------------------------------------------------------------------%
%--------------------------------------------------------------------------%
% Ralph Becket <rwab1 at cl.cam.ac.uk> 29/04/99
% Functional forms added.
%
% Douglas M. Auclair <doug.dot.auclair.at.logicaltypes.dot.com> 31/01/07
% Eliminated predicate redundancies, rolled functional forms in
--------------------------------------------------------------------------
mercury-users mailing list
Post messages to: mercury-users at csse.unimelb.edu.au
Administrative Queries: owner-mercury-users at csse.unimelb.edu.au
Subscriptions: mercury-users-request at csse.unimelb.edu.au
--------------------------------------------------------------------------
More information about the users
mailing list