强制重新计算列表

Question

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])

Answer 1

我在这里基本回答了这个问题: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函数来使用已有的列表函数.