如何在 Haskell 中对这种递归结构进行建模?

Question

我正在尝试通过Haskell类型系统对kdb/q"atoms and lists"进行建模。

在 kdb/q 中，所有数据都是从原子构建的。原子是特定数据类型的不可约值。Int、布尔值和字符是原子的例子。列表是从原子构建的有序集合。由于q是一种向量语言，因此大多数内置操作都是原子的，因此它会递归到参数结构中，直到到达原子。

例如：

(1;2;3( 是整数 1、2、3 的简单列表

(1.0;2;(3;4;5(( 是 1.0(float(、2(int( 和简单 int 列表 (3;4;5(

neg 是一个否定一个数字的函数。例如：

负 1 产生 -1

负 -1.0 产生 1f

负 (1.0;2;(3;4;5(( 产量 (-1f;-2;(-3;-4;-5)).

这就是激发我尝试在Haskell类型中建模这种行为的原因。数据类型应由原子类型和列表组成。

以下是我到目前为止所拥有的简化版本。我还进一步尝试使它成为可折叠和可遍历的实例。

data Atom = I Int
| C Char
| D Double 
deriving Show
data Q a = QAtom a 
| QList [Q a]
deriving Show
instance Functor Q where
fmap f (QAtom a) = QAtom (f a)
fmap f (QList qs) = QList $ fmap (fmap f) qs
instance Foldable Q where
foldMap f (QAtom a) = f a
foldMap f (QList qs) = mconcat $ fmap (foldMap f) qs
instance Traversable Q where
sequenceA (QAtom fa) = fmap QAtom fa
sequenceA (QList []) = pure $ QList []
sequenceA (QList (qfa:qfas)) = concatL <$> (sequenceA qfa) <*> (sequenceA (QList qfas))
where
concatL (QAtom a) (QList qas) = QList ((QAtom a):qas)

这就是我所拥有的，它可以编译，但我不是特别喜欢 concatL 函数，它不会根据类型涵盖所有模式。一旦我开始向Q添加新的值构造函数QDict [(Q Atom，Q a(]，情况就会变得更糟。

我是否正确地对原始数据进行了建模？我甚至应该尝试让它可遍历吗？但是，我认为如果我需要使用带有"可能"或"要么"的数据类型来建模错误，则 Traversable 是必要的。

任何建议不胜感激。

编辑：编辑了q代码格式

Answer 1

编译器知道如何自动为类型派生Traversable实例。如果你做:set -ddump-deriv -dsuppress-all -XDeriveTraversable -XStandaloneDeriving然后deriving instance Traversable Q，你可以看到"正确"的答案。如果您将这些知识应用于您的实例，您将获得以下内容：

instance Traversable Q where
sequenceA (QAtom fa) = fmap QAtom fa
sequenceA (QList qfas) = fmap QList (traverse sequenceA qfas)

或者，如果您想避免traverse而支持sequenceA：

instance Traversable Q where
sequenceA (QAtom fa) = fmap QAtom fa
sequenceA (QList qfas) = fmap QList (sequenceA (fmap sequenceA qfas))

关键是列表本身是Traversable的，因此您可以调用sequenceA，而无需将列表的各个部分重新包装在您自己的类型中。

---

旁注，在您的Foldable实例中，与其链接mconcat和fmap，只需再次使用foldMap，因为列表也是Foldable：

instance Foldable Q where
foldMap f (QAtom a) = f a
foldMap f (QList qs) = foldMap (foldMap f) qs