I believe you might be able to use (commutative) anti-unification, also
known as "generalization" for this task.
Jacques
Harry Chesley wrote:
This is more of an algorithm question than a language question, but
any insights would be much appreciated.
The problem is to input a series of programs and find previous
occurrences of the same algorithm.
The programs consist of a set of input parameters (a, b, c, ...), and
a set of side-effect-free functions (f, g, h, ...). Since the
functions are side-effect-free, they can be reordered without changing
the algorithm ("f(a), g(b)" is the same as "g(b), f(a)"). Subsequent
calls of the same function with the same parameters have no effect
("f(a), f(a)" is the same as "f(a)"); in fact, you can assume
duplicates have been removed in earlier processing.
But here's the thing that makes it hard (at least for me): two
programs are considered the same if they can be made to match by
rearranging the order of the input parameters. I.e., "f(a), g(b)" is
the same as "f(b), g(a)". Although parameters can be reordered, they
cannot be substituted ("f(a), g(b)" is _not_ the same as "f(a), g(a)").
Example: "f(a), g(b), h(a, b)" is the same as "f(b), g(a), h(b, a)"
but _not_ the same as "f(a), g(b), h(b, a)".
I need a way to compare the input programs, and preferably to order them.
In Haskell terms, given the programs are represented by a type Prog, I
want Prog to be a member of class Ord, letting me use tools like
Data.Map to look up information about previous instances.
I can do a brute-force compare by trying all the parameter
permutations, but that only gives me Eq, not Ord, and seems terribly
inelegant as well.
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
