Generic type transformations in Haskell

Question

I'm trying to write an arrow transformer that takes regular functions, and turns them into computations on abstract values. If we have a "source" arrow,

f :: Int -> Int
f x = x + 1

then the goal would be to have f work on lifted [sic?] abstract value types, in this example

f' :: AV Int -> AV Int
f' (Const x) = Const (f x)
-- pass along errors, since AV computation isn't always defined
-- or computable in the case of errors
f' (Error s) = Error s
-- avRep = "abstract representation". Think of symbolic math manipulation or ASTs.
f' (Abstract avRep) = AVRepPlus avRep (AVRepConst 1)

However, in order to implement this arrow successfully, one needs to lift a few types, so that one has heterogeneous data structures with some concrete and some abstract values, at arbitrary depth. What I've ended up doing is adding special types for regular haskell constructors, e.g. if

g = uncurry (+) -- i.e. g (x, y) = x + y

then I add an abstract representation for (,), the tuple constructor,

AVTuple :: AV a -> AV b -> AV (a, b)

and the code for g is lifted to [unrolled a little],

g' (AVTuple (AVConst a) (AVConst b)) = (AVConst (g (a, b)))
g' (AVTuple (AVError e) _) = (AVError e)
-- symmetric case here, i.e. AVTuple _ (AVError e)
g' (AVTuple a@(AVTuple _ _) b) = -- recursive code here

The same needs to be done with AVEither. This is going to end up being a lot of cases. Is there a nice way around this?

I am a Haskell newbie, so please send me references or semi-detailed explanation; probably the closest thing I've read is the SYBR paper (scrap your boilerplate revolutions) sections 1-3.

Thank you very very much!

Answer 1

Let me see if I understand what you're after here. You have a type AV a that describes a computation producing something of type a, where the structure of that computation may be preserved in a way that permits inspection. You want a way to lift arbitrary functions into operations on AV, preserving the structure, without having to create special cases for every operation.

Normally, for lifting functions into some structure one would use Functor and Applicative. However, the straightforward way of doing this involves transforming the structure and applying the lifted function directly, not preserving the function application as part of the structure.

What you want is much more awkward, and here's why:

Let's say we have some function we want to lift, and two abstract values of appropriate type to apply it to:

x :: AV A
x = ...

y :: AV B
y = ...

f :: A -> B -> C
f = ...

Suppose there exists a function liftAV2 that does what you want. We would expect that the type of lift2 f to be AV A -> AV B -> AV C, just like liftA for Applicative.

Later, we want to inspect a computation produced by using lift2 f, by recovering the values of f, x, and y. Let's say that for now we just want to extract the first argument. Suppose there exists a function extractArg1 that does this, such that extractArg1 (liftAV2 f x y) = x. What is the type of extractArg1? Here, in context, we know it should have type AV C -> AV A. But what type would it have in general? Something like AV c -> AV a? That's wrong, because the result isn't just any type a, it's whatever type was used to construct the AV c value. Assuming the value we're operating on was constructed using the result of liftAV2 f, we know that the type in question exists, but we have no way of finding it in general.

This is where we enter the land of, appropriately enough, existential types. Honestly using them, no less, not just misusing them with type classes as is often the case.

You can probably accomplish what you're after with some effort, but this is getting into rather advanced territory. You'll want to use GADTs for starters, though I think you might already be doing so. It also tends to be extremely clumsy working with existential types, because you're constrained to only knowing what they are in limited contexts.

In your specific case, it might be easier to give AV two type parameters: One representing the final type of the computation, and one representing the structure of the computation, e.g.:

data f :$ x = ...

data AV structure result where
    ...
    AVApply :: AV f (a -> b) -> AV x a -> AV (f :$ x) b

Then, for inspecting the computation you can look at the first type to know what you have; for building the computation you can look at the second to ensure the types match. An evaluation function would have a type like AV t a -> a, throwing away the structure. You could also "unpack" the computation using the structure type, throwing away the result type, if you need to take apart the structure in order to, say, pretty print it.

Answer 2

The way I like to think about it, I would use a Functor instance when I want to talk about some "data with a little extra" (depending on what the "little extra" is, I might in fact be talking about Applicative or Monad).

On the other hand I use an Arrow instance to talk about "functions with a little less": arrows let you define things that can be composed together in the same way as functions, but you get to add extra structure or restrictions to disallow certain constructions (for example arrows without ArrowChoice or ArrowLoop).

It is not entirely clear what you wish to accomplish, but it sounds like you are in fact wrapping your data in AV type constructors. In that case you will probably want to make AV an instance of Functor, and to add Functor instances for (AV a, AV b) => AV (a, b) and similarly for AV wrapped around Either.