[Haskell-cafe] Type classes vr.s functions

[Brian Hurt]

On Tue, 23 Dec 2008, wren ng thornton wrote:

> In particular, imagine that you have two different and valid ways to convert 
> the same type into Foo; which do you choose? With the 
> continuation/combinator/argument approach this is a non-issue since you can 
> just pass in the one you need. With type-classes it's tricky since they're 
> the same type, which leads to hacks with newtype wrappers or phantom types.
>
> If there is guaranteed to be only one valid transformation from any given 
> type into Foo, then type-classes make your intentions clear and they never 
> run into this issue. If more than one valid transformation could exist for 
> some type, then the extra argument is cleaner.

In this case, there is gaurenteed to be only one valid transformation. 
Basically, I have a number of similar data structures (which enforce 
different constraints, which is why they're not all the same data 
structure), and the function in question converts the specific 
(constraint-enforcing) data structures into a general 
(non-constraint-enforcing) data structure on which I can perform generic 
algorithms.

To be more specific, I'm writing a compiler in Haskell (what a shock), and 
the source data structures are the parse trees after various 
transformations- for example, after the lambda lifting phase, the parse 
tree should not have lambda expressions in them at all (they should have 
all been lifted to top-level functions).  So, while the 
before-lambda-lifting data structure has a Lambda constructor, the 
after-lambda-lifting data structure doesn't, thus enforcing the constraint 
that lambda lifting removes all (non-top-level) lambda expressions.  But I 
want to be able to get all free variables of a given expression, both 
before and after lambda lifting, so I just define a function to convert 
both types into a common generic representation that I can write a "get 
free variables" function to work on.

At this point, I realize that I'm being stupid and way over thinking 
things.  Haskell is a *lazy* language- I'm still wrapping my head around 
the implications of that statement.  My original thinking was that the 
conversion function would be a one-level conversion, i.e. the data 
structure would be like:
data Generic a =
 	UnaryOp uop a
 	| BinaryOp a bop a
 	| If a a a
 	...

i.e. I'd only convert the root node, and the child nodes would still be 
the original data structure.  So I'd need to pass around a function of the
form:
 	a -> Generic a
which is my conversion function.  But what I'm doing here is 
hand-reimplementing a lazy conversion of the data structure- which I get 
for free anyways.  So what I should do is define the data structure like:
data Generic =
 	UnaryOp uop Generic
 	| BinaryOp Generic bop Generic
 	| If Generic Generic Generic
 	...

Then all I need to do is to write the pure conversion function a -> 
Generic, and then run the generic algorithm over the data structure.  That 
gives me the exact behavior I'm looking for, without either (explicitly) 
passing a conversion function around or playing with fancy typeclasses.

Pardon me while I go beat my head against the wall.

Brian