4

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

1 回答 1

6

我在这里基本上回答了这个问题：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-06T18:45:17.167 回答