如何防止此循环多项式哈希函数使用类型约束？

Question

我正在尝试在 f# 中实现 Cyclic polynomial hash function。它使用按位运算符 ^^^ 和 <<<。下面是一个散列数组的函数示例：

let createBuzhash (pattern : array<'a>)  =
let n = pattern.Length
let rec loop index pow acc =
    if index < n then
        loop (index+1) (pow-1) (acc ^^^ ((int pattern.[index]) <<< pow))
    else
        acc
loop 0 (n-1) 0

我的问题是 'a 的类型将被限制为 int，而我希望此函数适用于任何使用位运算符的类型，例如一个char。我尝试使用 inline，但这会在我的库中产生一些问题。有没有办法不使用 inline 来解决这个问题？

为清楚起见编辑：该函数将成为库的一部分，并且为不支持按位运算符的类型提供了另一个哈希函数。我希望这个函数可以处理数字类型的数组 and/or 个字符。

编辑 2（问题已解决）：内联的问题是我从库中加载函数的方式。而不是

let hashedPattern = library.createBuzhash targetPattern

我使用了这个绑定：

let myFunction = library.createBuzhash
let hashedPattern = myFunction targetPattern

将 myFunction 的输入类型限制为 int，尽管 createBuzhash 函数是库中的一个 inline 函数。改变我调用函数的方式解决了类型约束问题，inline 工作得很好，正如下面的答案所暗示的那样。

Answer 1

在实现中，您使用 int 函数将数组中的值转换为整数，如下所示：int pattern.[index]

这对要求它们是 "something that can be converted to int" 的数组元素类型创建了一个约束。如果您将该函数标记为 inline，它实际上适用于 char 这样的类型，您将能够编写：

createBuzhash [|'a'; 'b'|]

但是还有很多其他类型无法使用int函数转换为整数。

要使其适用于任何类型，您必须决定要如何处理非数字类型。你想:

为所有值提供您自己的哈希函数？
使用内置的 .NET GetHashCode 操作？
只使您的函数适用于数值类型和数值类型数组？

一个选项是添加指定如何进行转换的参数：

let inline createBuzhash conv (pattern : array<'a>)  =
  let n = pattern.Length
  let rec loop index pow acc =
      if index < pattern.Length then
          loop (index+1) (pow-1) (acc ^^^ ((conv pattern.[index]) <<< pow))
      else
          acc
  loop 0 (n-1) 0

当调用 createBuzhash 时，您现在需要给它一个函数来散列元素。这适用于使用 int 函数的原始类型：

createBuzhash int [| 0 .. 10 |]
createBuzhash int [|'a'; 'b'|]

但您也可以使用内置的 F# 哈希机制：

createBuzhash hash [| (1,"foo"); (2,"bar") |]

您甚至可以通过将函数传递给自身来处理嵌套数组：

createBuzhash (createBuzhash int) [| [| 1 |]; [| 2 |] |]

如何防止此循环多项式哈希函数使用类型约束？

How to prevent this Cyclic polynomial hash function from using a type constraint?

hash

f#

constraints

type-conversion

rabin-karp