Haskell数据结构具有优化的访问方法

Question

我想创建用于访问和修改简单音乐库的数据类型,包括由曲目组成的专辑.有关基本想法,请考虑以下事项:

data MusicCollection = MC { albums :: Seq Album }
data Album = Album { albumTitle :: String, tracks :: Seq Track }
data Track = Track { trackTitle :: String, tempo  :: Tempo }

data Tempo = Unknown | BPM Int

除了节奏,还可能有其他属性,如样式或评级.

上述解决方案让我可以快速访问随机相册.另外,我希望能够比指定速度更快地访问所有曲目.再次,对返回的曲目进行快速随机访问会很不错:

fasterThan :: Int -> MusicCollection -> SomeRandomAccessCollection Track

更新集合中的轨道也不应该太慢.

题:

我不知道是否Map Tempo (Seq Track)最好添加一个MusicCollection,或者是否有可能以某种方式模仿关系数据库.也许有完全不同的解决方案？

我目前不想使用数据库,但了解何时在桌面应用程序中使用它们会很有趣.

Answer 1

如果您不想使用数据库,那么您几乎必须为Map您想要快速访问的每个关系创建一个,正如您所描述的那样.

需要注意的是Data.Map.Map在containers包使用命令键,这样你就可以例如用Data.Map.split得到的地图,这是非常有用的发现相当快分区"跟踪超过规定速度更快"(前提是你得到Ord的Tempo).因此,如果您不需要用于关系的有序键,则应该使用Data.HashMap.HashMapfrom unordered-containers,其实现速度更快.

也可以使用没有附加依赖性的内存中关系数据库.例如,您可以使用persistentSqlite作为后端.持久性教程中描述了如何执行此操作.

Answer 2

是的，Map Tempo (Seq Track)这里是一个不错的选择，特别是因为它的Ord基于结构可以让您有效地进行诸如“速度大于n的所有曲目”之类的查询；参见 数据.地图.分割。

这基本上是通过使用索引来模仿关系数据库。

您可能还对IxSet和HiggsSet （不同作者的 IxSet 的预期继承者）感兴趣，它们旨在使用各种索引来增强集合结构，特别是与Acid-state等事务序列化系统结合使用。它们支持方便的比较查询，例如大于、小于等。但是，如果您只有一两个索引，那么最好自己推出。