可实现的表达式数据结构，它也实例化Functor

Question

我想定义一个数据类型，用于编码可具体化的表达式，该表达式也实例化Functor。

在这种情况下，可以简单地表示表达式可以表示为字符串，以便稍后可以将它们解析回相同的表达式。在这方面，它相当于实例化Show。

示例简化表达式数据结构:

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

type变量对表达式求值时产生的值的类型进行编码。两个const构造函数是表达式的叶子。Product构造函数允许我们构建更高级的类型。Apply构造函数用于"提升"。使用String字段对表达式进行操作的正则函数

举一个函数的例子:

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

表达式可以这样构造:

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

为了完整起见，求值器可以采用以下形式:

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)

在这个例子中，Show的实例化很简单:

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 ++ ")"

但是Functor不能实现，因为没有办法命名被提升的函数:

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

一个可能的解决方案可能是在外部提供从函数(例如swap)到标识符(例如"swap")的映射，但我不确定是否/如何做到这一点。

Answer 1

从概念上讲，你想做的事情是不可能的。

fmap需要为any函数工作，any函数类型。那么如果函数不可实现会怎样呢?。如果它是由涉及不可重构值(如打开的数据库连接)的部分应用程序形成的?

你有几个选择。

1. 您可以放松期望Exp x的语义将在具体化周期中存活。匿名或不可验证的函数只会得到"named"。"<function>"，并将作为undefined解除酸洗。注意:如果你想要一个instance Eq Exp a，你需要确保它与函子定律的恒等式和组合是兼容的。
2. 放弃Functor，定义自己的expMap让它以Exp (a -> b)作为f参数，并为函数引入Exp构造函数和操作符，足以启用您想要的功能。
3. 深入了解Haskell中嵌入式dsl的现代工具。我怀疑数据类型点菜可能会有所帮助，但学习如何使用DTalC本身就是一个项目。
4. 窃取其他人的工作，他们需要处理"可撤销"的工作;功能。就在昨天，我还得摆弄QuickCheck的Functions模块。这也会很困难;你的问题是一个老问题，任何解决方案(即使是部分解决方案)都将是"不平凡的"，这意味着它需要花时间去理解。