You can translate the following algorithm (written in Maple 11), which
can be made purely functional. [For the cognoscenti: attributes are
implemented in-place in Maple, but that is really just an instance of
the Decorator pattern which can be just as easily implemented with a
functional Map]. Note that all the assignments below are really just
let bindings.
Jacques
longestIncreasingSequence := proc(L::list)
local n,i,j,G;
uses GraphTheory;
n := nops(L);
G := Digraph(n
, {seq(seq(`if`(L[i]<L[j]
, [i,j]
, NULL
)
, j = i+1..n)
, i = 1..n-1)}
);
map(op,LongestPathOfDAG(G),L);
end proc:
#
LongestPathOfDAG := proc(G)
local len, sources, v;
uses GraphTheory;
len := proc(v)
option cache;
local j,dep,longest;
uses GraphTheory;
dep := Departures(G,v);
if dep = [] then
setattribute(Float(1),v);
else
longest := max(seq(procname(j), j in dep));
setattribute(1 + longest, v, attributes(longest));
end if;
end proc;
sources := select(v -> Arrivals(G,v)=[], Vertices(G));
[attributes(max(seq(len(v), v in sources)))];
end proc:
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
