强制重新列表重新计算

下面的函数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

强制重新列表重新计算

回答

相关问题