如何在 Haskell 中对这种递归结构进行建模?
How to model this recurisve structure in Haskell?
我正在尝试通过 Haskell 类型系统对 kdb/q "atoms and lists" 进行建模。
在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
neg -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 代码格式
编译器知道如何为您的类型自动派生一个 Traversable
实例。如果您执行 :set -ddump-deriv -dsuppress-all -XDeriveTraversable -XStandaloneDeriving
然后 deriving instance Traversable Q
,您可以看到 "right" 答案。如果您掌握这些知识并将其应用到您的实例中,您将得到:
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
我正在尝试通过 Haskell 类型系统对 kdb/q "atoms and lists" 进行建模。
在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
neg -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 代码格式
编译器知道如何为您的类型自动派生一个 Traversable
实例。如果您执行 :set -ddump-deriv -dsuppress-all -XDeriveTraversable -XStandaloneDeriving
然后 deriving instance Traversable Q
,您可以看到 "right" 答案。如果您掌握这些知识并将其应用到您的实例中,您将得到:
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