Haskell：使用MapReduce來搜索子串？

Question

我正在嘗試使用現有的MapReduce實現（Real World Haskell）編寫一個簡單的程序。

作爲使用框架的例子，這裏是一些代碼來計算文件中的單詞數：

module Main where 

import Control.Monad (forM_) 
import Data.Int (Int64) 
import qualified Data.ByteString.Lazy.Char8 as LB 
import System.Environment (getArgs) 

import LineChunks (chunkedReadWith) 
import MapReduce (mapReduce, rdeepseq) 

wordCount :: [LB.ByteString] -> Int 
wordCount = mapReduce rdeepseq (length . LB.words) 
         rdeepseq sum 

main :: IO() 
main = do 
    args <- getArgs 
    forM_ args $ \path -> do 
    numWords <- chunkedReadWith wordCount path 
    putStrLn $ "Words: " ++ show numWords 

我需要使用相同的MapReduce框架編寫一個程序，搜索一些字符串（如「il」），並返回找到它們的行號。例如，輸出可能是：

verILy: found on lines 34, 67, 23 
ILlinois: found on lines 1, 2, 56 
vILla: found on lines 4, 5, 6 

（的「IL」的資本不是必需的。）

我是一個Haskell初學者，沒有任何具體的想法呢。我確實注意到Data.ByteString.Lazy.Char8類有一個成員函數findIndices。有沒有可能使用這個？

任何代碼或提示正確的方向將不勝感激。

Answer 1

好吧，讓我們打這個。

---

首先，我們將需要一種方法來查找字符串中的單詞。這可以使用Regex來完成，比如說regex-tdfa包。 Haskell正則表達式包很好，但是非常普遍，起初有點難以閱讀。我們將創建一個函數，它僅僅是匹配運算符(=~)的一個包裝，主要用於製作類型混凝土。現在

wordHere :: LB.ByteString -> LB.ByteString -> Bool 
wordHere word string = string =~ word 
-- a.k.a.   = flip (=~) 

---

，mapReduce擊穿給予了大量平行的，當地「映射」 (a -> b)類型的作業不同的火花，然後在所有結果摺疊在減少像([a] -> c)列表工作爲([b] -> c)。一般不會保證訂單的減少步驟，但RWH的mapReduce實際上確實給了我們這個保證。

RWH的lineChunks函數實際上將文檔（LB.ByteString - > [LB.ByteString]）分割成少量行的塊。我們的地圖作業每個都會得到這些塊中的一個，並且需要本地提供有關線匹配的信息。我們可以通過將大塊拆分爲它們的組成線，本地對這些線編號，將wordHere映射到它們上面，並收集wordHere返回true的本地線路編號。我們會做到這一點通常第一，任何斷言p :: (LB.ByteString -> Bool)

import Control.Arrow 

localLinesTrue :: (LB.ByteString -> Bool) -> [LB.ByteString] -> [Int] 
localLinesTrue p ls = map fst . filter snd . map (second p) . zip [1..] 

更換wordHere現在我們可以像localLinesTrue (wordHere $ LB.pack "foobar") . LB.lines :: LB.ByteString -> [Int]創建本地映射器。

這種類型的映射器也闡明瞭函數其餘部分的類型。我們現在有

>>> :t mapReduce rdeepseq (localLinesTrue (wordHere "foo")) rdeepseq 
... :: ([[Int]] -> c) -> [LB.ByteString] -> c 

所以我們的減速機必須是([[Int]] -> c)類型。很酷，讓我們試着做到這一點。如果我們有一個列表Int s我們可以重建實際的行號......

[[], [], [], [5], [3], [], []] 

等等，其實我們不行。我們需要在映射器中添加更多信息 - 每個塊中發生的行數。幸運的是，由於我們正在謹慎地保留我們的東西，因此很容易添加。我們需要一個更類似於([Int], Int)的返回類型，其中第二個參數是該塊的行數。我們可以用「粉絲」(&&&)來做到這一點。

mapper regex = (localLinesTrue (wordHere regex) &&& length) . LB.lines 

，現在我們的產量將看起來像

[ ([], 3), ([], 5), ([3, 5], 10), ... ] 

，我們可以實現它只是計數使用State單子

reducerStep :: ([Int], Int) -> State Int [Int] 
reducerStep (hits, count) = do pos <- get 
           modify (+count) 
           return (map (+pos) hits) 

reducer :: [([Int], Int)] -> [Int] 
reducer = concat . evalState 0 . mapM reducerStep 

減速，我們已經有了

mapReduce rdeepseq (mapper regex) 
      rdeepseq reducer 
    :: [LB.ByteString] -> [Int] 

哪ou ght讓你的95％的方式到最後。