concurrency - 在Haskell中将 “insertions”并行化为二进制特里

我有一个n位“单词”列表

type BitWord = [Bool]

一个从上到下存储单词的特里:

data Tree = Bs Tree Tree  -- Bs (zero_bit) (one_bit)
          | X -- incomplete word
          | B -- final bit of word

我有一个功能:

seenPreviously :: BitWord -> Tree -> (Tree,Bool)

该函数逐步浏览BitWord中的位，同时下降到Tree处的零位处，反之亦然。如果必须在某个点添加子树(即BitWord尚未加入特里树)，则返回带有此BitWord“合并”的新树，以及True，否则返回False。

我将此函数映射到[BitWord]上，将Tree传递为状态。

我的问题是这个:这可以从Control.Parallel提供的并行性中受益吗？如果是这样，我该如何仅对弱头法线形式等进行懒惰和评估？

我的直觉是，我可以在左分支下插入(实际上是在构建子树)，同时在右分支下做相同的事情，就像两个独立的线程一样。就像是:

parallelMapSt :: [ BitWords ] -> Tree -> [Bool]
parallelMapSt [] _ = []
parallelMapSt (w:ws) t = let (b,t') = seenPreviously w t
                             bs     = parralelMapSt ws t'
                          in t' `par` bs `pseq` (b:bs)

评估b的线程依赖于一些先前触发的线程(属于BitWords的线程，它们与w共享一些公共(public)前缀)，但并非全部都如此，因此似乎有机会在此处并行进行工作，但是我真的不确定。

最佳答案

遍历树时看起来很适合使用par ...很像二叉树基准测试。尝试使用这种类型编写一些程序，并测量par的效果。