file - 如何让我的 Haskell 代码使用懒惰和垃圾收集器

Question

我写了一个 Haskell 代码，它必须解决以下问题:我们有 n 个文件:f1、f2、f3 .... fn 并且我剪切了这些文件，使每个切片都有 100 行

  f1_1, f1_2, f1_3 .... f1_m

  f2_1, f2_2, .... f2_n
  ...

  fn_1, fn_2, .... fn_k

最后，我按以下方式使用切片构造了一个特殊的数据类型(Dags)

  f1_1, f2_1, f3_1, .... fn_1 => Dag1

  f1_2, f2_2, f3_2, ..... fn_2 => Dag2

  ....

  f1_k, f2_k, f3_k, ..... fn_k => Dagk

我编写的代码首先切割所有文件，然后耦合结果列表的第 i 个元素并使用最终结果列表构建 Dag

它看起来像这样

  -- # take a filename and cut the file in slices of 100 lines

  sliceFile :: FilePath -> [[String]]

  -- # take a list of lists and group the i-th elements into list

  coupleIthElement :: [[String]] -> [[String]]

  -- # take a list of lines and create a DAG

  makeDags :: [String] ->  Dag

  -- # final code look like this

  makeDag_ :: [FilePath] -> [Dag]

  makeDags files = map makeDags $ coupleIthElement (concat (map sliceFile files))

问题是这段代码效率不高，因为:

它需要将所有文件以列表形式存储在内存中

垃圾收集器工作效率不高，因为所有函数都需要前一个函数的结果列表

我怎样才能重写我的程序以利用垃圾收集器的工作和 Haskell 的惰性？

如果不可能或更容易，我该怎么做才能提高效率？

谢谢您的回复

编辑
coupleIthElement ["abc", "123", "xyz"]必须返回 ["a1x","b2y","c3z"]
因为这 100 行是根据行的某些元素使用特定标准任意选择的，但我放弃了这一方面以使问题更容易理解，

另一个版本

data Dag = Dag ([(Int, String)], [((Int, Int), Int)]) deriving Show

test_dag = Dag ([(1, "a"),(2, "b"),(3, "c")],[((1,2),1),((1,3),1)])

test_dag2 = Dag ([],[])

第一个列表是由编号和标签定义的每个顶点，第二个列表是边 ((1,2),3)表示顶点 1 和 2 之间的边，成本为 3

Answer 1

几点:

1) 您是否考虑过使用 fgl ?它可能比你自己的更有效率 Dag执行。如果你真的需要使用Dag ，你可以用 fgl 构建你的图表然后将它们转换为 Dag当它们完成时。

2)在构建图形时，您似乎实际上并未使用切片，而是它们控制您拥有的图形数量。如果是这样，这样的事情怎么样:

dagFromHandles :: [Handle] -> IO Dag
dagFromHandles = fmap makeDags . mapM hGetLine

allDags :: [FilePath] -> IO [Dag]
allDags listOfFiles = do
  handles <- mapM (flip openFile ReadMode) listOfFiles
  replicateM 100 (dagFromHandles handles)

这假设每个文件至少有 100 行，任何多余的行都将被忽略。更好的是，如果您有一个可以使用 Dag 的函数，那么您可以这样做

useDag :: Dag -> IO ()

runDags :: [FilePath] -> IO ()
runDags listOfFiles = do
  handles <- mapM (flip openFile ReadMode) listOfFiles
  replicateM_ 100 (dagFromHandles handles >>= useDag)

这应该更有效地利用垃圾收集。

当然，这假设我正确理解了问题，我不确定我是否理解。请注意 concat (map sliceFile)应该是空操作( sliceFile 需要在 IO 中，因为您已经定义了类型，但现在忽略它)，所以我不明白您为什么要为此烦恼。