[Haskell-cafe] Longest increasing subsequence

Jacques Carette carette at mcmaster.ca
Thu Apr 10 17:48:57 EDT 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.


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)}
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
            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:

More information about the Haskell-Cafe mailing list