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

Question

我正在尝试通过 Haskell 类型系统为 kdb/q“原子和列表”建模。

在 kdb/q 中，所有数据都是从原子构建的。原子是特定数据类型的不可约值。 Int、boolean 和 char 是原子的例子。列表是从原子构建的有序集合。由于 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

neg (1.0;2;(3;4;5)) 产生 (-1f;-2;(-3;-4;-5))。

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

以下是我目前所拥有内容的简化版本。而且我还进一步尝试将其作为 Foldable 和 Traversable 的实例。

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)] ，情况就会变得更糟。

我是否正确地为原始数据建模？我是否应该尝试使其可遍历？但是我认为如果我需要使用带有 Maybe 或 Either 的数据类型来建模错误，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