some algorithms are hard to code in O(n) in Haskell
Thu, 25 Apr 2002 11:46:50 +0200

Hi -

does anybody know how to do a term unification in Haskell in O(n), where n
is length of the input terms? I know Montanari-Martelli algorithm for this,
but I'm unable to code it in Haskell (in O(n)). I would need a destructive
update of the directed graph representing terms (to do a substitution) and
checking for cycles in directed graphs (these cycles emerge when unifying
things like x=f(x) -- their detection is also called occurs-check).

I've been trying hard but still have no solution. Maybe I'm not smart
enough, maybe I don't know some trick, maybe it's impossible in Haskell.