I would like to define a data type for encoding reifiable expressions which also instances Functor.

In this case reifiable can simply mean that expressions can be represented as a string such that they can be later parsed back into the same expressions. In this regard it is equivalent to instancing Show.

Example simplified Expression data structure:

data Exp x where
    ConstInt :: Int -> Exp Int
    ConstString :: String -> Exp String
    Product :: Exp a -> Exp b -> Exp (a, b)
    Apply :: String -> (a -> b) -> Exp a -> Exp b

The type variable encodes the type of the value produced when the expression is evaluated. The two Consts constructors are the leaves of the expression. The Product constructor lets us build up higher level types. The Apply constructor is used to "lift" regular functions to operate on expressions with the String field used to identify the lifted function.

Example of lifting a function:

swap :: (b, a) -> (a, b)
swap (a, b) = (b, a)

swapExp :: Exp (b, a) -> Exp (a, b)
swapExp = Apply "swap" swap

Expressions can then be constructed such as:

example :: Exp (String, Int)
example = swapExp $ Product (ConstInt 0) (ConstString "string")

Just for completeness an evaluator could take the following form:

eval :: Exp x -> x
eval (ConstInt a) = a
eval (ConstString a) = a
eval (Product a b) = (eval a, eval b)
eval (Apply _ f a) = f (eval a)

In this case instancing Show is straightforward:

instance Show (Exp x) where
    show (ConstInt x) = show x
    show (ConstString x) = "\""    show x    "\""
    show (Product a b) = "("    show a    ", "    show b    ")"
    show (Apply name f exp) = name    "("    show exp    ")"

But Functor cannot be implemented as there is no way to name the function which is lifted:

instance Functor Exp where
    fmap f exp = Apply "???" f exp

One possible solution might be to externally provide a mapping from functions (e.g. swap) to identifiers (e.g. "swap"), but I'm not sure if/how that can be done.

CodePudding user response：

Conceptually, what you're trying to do is impossible.

fmap needs to work for any function, any function type. So what happens if the function isn't reifiable? e.g. if it's formed by partial application involving an un-reifiable-able value like an open database connection?

You have a few options.

1. You could relax the expectation that the semantics of an Exp x will survive the reification cycle. Anonymous or unreifiable functions will just get "named" "<function>", and will un-pickle as undefined. Be careful: if you ever want an instance Eq Exp a, you'll need to make sure it's compatible with the functor laws for identity and composition.
2. Give up on Functor and define your own expMap. Make it take an Exp (a -> b) as its f argument, and introduce Exp constructors and operators for functions sufficient to enable the functionality you want.
3. Go deep on modern tools for embedded DSLs in Haskell. I suspect Data Types a la Carte could be helpful, but learning how to use DTalC is a project in itself.
4. Steal the work of other people who needed to handle "reifiable" functions. Just yesterday I had to mess around with QuickCheck's Functions module. This would also be hard; your problem is an old one, and any solution (even a partial one) will be "non trivial", meaning it will take work to understand.