Hi fellow Haskelleers, I have a tricky problem that I just can't seem to solve. The problem is one of unresolved overloading, much like the (show . read) issue, but unlike that particular problem I feel there should be a solution to the one I'm wrestling with. I've tried to strip away all the unnecessary bits so the following will be a bit abstract, but it shows the gist of the problem. I have two overloaded functions - one I call 'build' that creates values from subparts, and one I call 'embed' that turns values into a form appropriate to call 'build' on. What they really represent is creating values of some XML tree structure, with embed making sure that the children are of the right type. Conceptually, we could imagine that these two functions to be defined as
class Build x c | x -> c, c -> x where build :: String -> [c] -> x
class Embed a b where embed :: a -> b
They would be used together as in e.g.
p c = build "p" [embed c]
This works pretty well, the fundep x -> c tells me what b should be, assuming I infer a proper type for the result of the composition. The type of p is then p :: (Embed a c, Build x c) => a -> x where the c in the middle is determined by x via the fundep. My problems arise because I want to start nesting these to form tree structures, as in
tree = p (p "foo")
Expanding the definition of p, the argument to the outer call to build is now embed $ build "p" [embed "foo"] :: (Embed String c, Build x c, Embed x x1) => x1 Through the fundep on the outer build I can infer what x1 should be, but there's no way I can infer x (without inserting an explicit type signature which is out of the question). This problem is probably unsolvable in general, but for my particular problem there are some restrictions that makes me feel there should be a clever way of working with classes and fundeps to make this all work out. I just can't seem to find one. These are the rules that the setup must obey: * A value of any type should be embeddable inside a build expression of any result type, i.e. a -> b or b -> a cannot hold on Embed in general. * The exception to the above is that if an expression using 'build' is embedded inside an outer 'build', as in 'tree' above, the inner build should have the same result type as the outer build (in a sense forming b -> a only for types instantiating Build). In other words, children of an xml element must be of the same type as their parent, even before the call to embed. * However, it would be nice, but probably not crucial, if by using explicit type signatures where I want to, I could actually embed values of "other" xml types than the outer one I am embedding them in, and letting embed convert them to xml of the correct type. I suspect this cannot be. The types of build and embed are negotiable, and certainly the type classes, as long as the two can be used together in roughly the same way as indicated above. The calls to build and embed will be autogenerated by a preprocessor from a HSP-style XML syntax, e.g. <p><% c %></p> <==> build "p" [embed c] and for this reason any solution *must* be syntactically expressible as expressions on a form similar to the above, but those expressions can be arbitrarily convoluted. For instance in my failed attempts so far I have used let expressions around build to form self-recursive versions to "pass a type" down through the evaluation, as in p c = let x = build "p" [embed x c] in x This is an ok solution syntactically, if only it solved the problem, I still can't see how to propagate it to the next level of build. :-( Is there anyone out there with the proper type class fu who can see a way out for me? Is this even possible to do at all? If yes, tell me please, and if not, I would be most interested in seeing why it cannot work. Any and all comments are welcome. Thanks for reading this long :-) /Niklas