Re: [Haskell-cafe] Longest increasing subsequence

10 Apr 2008


      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:

Re: [Haskell-cafe] Longest increasing subsequence

Jacques Carette