如何使我的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 

最後我構建使用切片以下列方式

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 

，我通過切割所有文件寫開始的代碼的特殊數據類型（DAG）的，那麼它結合結果列表的第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中，因爲您已經定義了該類型，但現在忽略該類型），所以我不明白爲什麼您一直在困擾它。

Answer 2

如果它是不需要在切片中處理文件，避免這種情況。 Haskell自動完成這個！在Haskell中，您將IO視爲流。只要數據一經需要並被丟棄，數據就會從輸入中讀取，一旦未被使用。因此，舉例來說，這是一個簡單的文件複製PROGRAMM：

main = interact id 

interact有簽名interact :: (String -> String) -> IO()，並供給輸入處理它，併產生一些輸出，被​​寫入到標準輸出的功能。此程序比大多數C實現更高效，因爲運行時會自動緩衝輸入和輸出。

如果你想了解懶惰，你必須忘記你作爲一個必要的程序員學到的所有智慧，並且必須考慮程序作爲描述來修改數據，而不是作爲一組指令 - 數據是只處理需要的時候！

重點，爲什麼你的數據可能被錯誤地處理是列表的多重轉換。您的功能makeDags逐個遍歷切片列表，因此原始列表的元素可能不會被丟棄。你應該嘗試，是寫你的函數在這樣的方式：

sliceFile :: FilePath -> [[String]] 
sliceFile fp = do 
    f <- readFile fp 
    let l = lines fp 
     slice [] = [] 
     slice x = ll : slice ls where (ll,ls) = splitAt 100 x 
    return slice l 

sliceFirstRow :: [[String]] -> ([String],[[String]]) 
sliceFirstRow list = unzip $ map (\(x:xs) -> (x,xs)) list 

makeDags :: [[String]] -> [Dag] 
makeDags [[]] = [] 
makeDags list = makeDag firstRow : makeDags restOfList where 
(firstRow,restOfList) = sliceFirstRow list 

該功能可能是一個解決方案，因爲第一行不再被引用，當它這樣做。但在大多數地方，這是懶惰的結果，因此您可以嘗試使用seq來強制構建Dags並允許IO數據被垃圾收集。 （如果你不強制建造垃圾，數據不能被垃圾回收）。

但無論如何，如果您提供一些關於這些dag是什麼的信息，我可以提供更有幫助的答案。