[Haskell-cafe] Type hackery help needed!

[Niklas Broberg]

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