list - 强制重新计算列表

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函数来使用您已有的列表函数。