強制重新列表重新計算

下面的函數search搜索兩個在某些函數下具有相同輸出的輸入。在搜索期間，它重複輸入列表xs兩次，並且這個輸入列表可能非常大，例如， [0..1000000000]。我寧願使用內存來存儲由碰撞創建的HashSet，而不是存儲xs的元素，我的理解是，儘管xs可能會被延遲計算，但它將保留在需要調用find的情況下。強制重新列表重新計算

問題：

是這樣理解是否正確？
如果我把它作爲一個列表有沒有一種方法，我可以xs重新計算，如果它傳遞給find？
是否有替代的數據結構我可以用於xs，它允許我控制使用的空間？ xs僅用於指定要檢查的輸入。

請注意，xs沒有類型限制 - 它可以是任何類型的集合。

import Data.HashSet as Set 
import Data.Hashable 
import Data.List 

search :: (Hashable b, Eq b) => (a->b) -> [a] -> Maybe (a,a) 
search h xs = 
    do x0 <- collision h xs 
    let h0 = h x0 
    x1 <- find (\x -> (h x) == h0) xs 
    return (x0,x1) 

collision :: (Hashable b, Eq b) => (a->b) -> [a] -> Maybe a 
collision h xs = go Set.empty xs 
    where 
    go s [] = Nothing 
    go s (x:xs) = 
     if y `Set.member` s 
     then Just x 
     else go (Set.insert y s) xs 
     where y = h x 

main = print $ search (\x -> x `mod` 21) ([10,20..2100] :: [Int])

來源

2012-06-06 ErikR

你真的是指''x1 < - find（\ x - >（h x）'Set.member' s）xs''而不是'h x == h0'？ –

很好的捕捉 - 這簡單很多 – ErikR

您可以在[美麗摺疊]（http://squing.blogspot.com/2008/11/beautiful-folding.html）中調整想法以產生漂亮的掃描效果。 –

我基本上在這裏回答了這個問題：https://stackoverflow.com/a/6209279/371753

下面是相關的代碼。

import Data.Stream.Branching(Stream(..)) 
import qualified Data.Stream.Branching as S 
import Control.Arrow 
import Control.Applicative 
import Data.List 

data UM s a = UM (s -> Maybe a) deriving Functor 
type UStream s a = Stream (UM s) a 

runUM s (UM f) = f s 
liftUM x = UM $ const (Just x) 
nullUM = UM $ const Nothing 

buildUStream :: Int -> Int -> Stream (UM()) Int 
buildUStream start end = S.unfold (\x -> (x, go x)) start 
    where go x 
      | x < end = liftUM (x + 1) 
      | otherwise = nullUM 

usToList x = unfoldr (\um -> (S.head &&& S.tail) <$> runUM() um) x

長話短說，而不是繞過列表，來傳遞描述如何生成一個列表中的數據類型。現在，您可以直接在流上編寫函數，也可以使用函數usToList來使用您已有的列表函數。

來源

2012-06-06 18:45:17 sclv

強制重新列表重新計算

回答

相關問題