1

我必须为学校写这个 Pearson Hash，但我从未听说过它，所以很难想象它是如何工作的。这使我很久以前学习haskell的事情变得更加困难，我几乎忘记了它。

事情是这样的：他们告诉我这个函数的语法是这样的：

pearsonHash :: [Int] -> [Int] -> Int

Pearson Hash的算法是：

h := 0
for each c in C loop
    index := h xor c
    h := T[index]
end loop
return h

他们说：让C是字节的输入序列，而h是要计算的值。并且 pearson hash 的第一个参数应该是一个预定义的T列表，其中包含 的排列[0..255]。

有测试用例：

pearsonHash ([0..127] ++ [255,254..128]) [1..10]   ==  11
pearsonHash [255,254..0] [ ord c | c <- "Hello" ]  ==  189

我认为他们应该是True。

这只是工作的一部分（意味着这只是很多功能中的一个），所以我不希望你代替我来解决这个问题，我只需要帮助如何解决这个功能，因为我被这个功能卡住了.

4

1 回答 1

4 
h := 0
for each c in C loop
    index := h xor c
    h := T[index]
end loop
return h

好的，所以这看起来非常必要。当你看到这样的循环时，你可能想做的就是把“循环体”变成一个函数，然后循环本身就是foldror foldl。所以你的代码最终看起来像

hashStep :: [Int] -> Int -> Int -> Int
hashStep ts h c = ...???...

pearsonHash :: [Int] -> [Int] -> Int
pearsonHash ts cs = foldr (hash_step ts) 0 cs

现在，你能弄清楚hashStep应该怎么做吗？

于 2015-03-16T10:59:27.413 回答