F# Bjorklund 算法：将 while 循环转换为递归函数：类型约束问题

Question

我终于深入研究了 f#。长期使用 c 风格命令式的人 - 但所有语言的爱好者。我正在尝试欧几里德节奏的 Bjorklund 算法。 Bjorklund：二进制字符串中 1 的最相等间距直到旋转，例如1111100000000 -> 1001010010100。

https://erikdemaine.org/papers/DeepRhythms_CGTA/paper.pdf

我最初的尝试基于一个不错的 js/lodash 实现。我从头开始尝试，但都被旧概念束缚了。

https://codepen.io/teropa/details/zPEYbY

这是我的 1:1 翻译

let mutable pat = "1111100000000" // more 0 than 1
//let mutable pat = "1111111100000" // more 1 than 0

// 
let compareSequences = Seq.compareWith Operators.compare

let mutable apat = Array.map (fun a -> [a]) ( Seq.toArray  pat )
let mutable cond = true
while cond do
    let (head, rem) = Array.partition (fun v -> (compareSequences v apat.[0]) = 0) apat
    cond <- rem.Length > 1
    match cond with
    | false -> ()
    | true ->
        for i=0 to (min head.Length rem.Length)-1 do
            apat.[i] <-apat.[i] @ apat.[^0]
            apat <- apat.[.. ^1]

let tostring (ac : char list) = (System.String.Concat(Array.ofList(ac)))
let oned = (Array.map (fun a -> tostring a) apat )
let res = Array.reduce (fun a b -> a+b)  oned
printfn "%A" res

这似乎行得通。但是因为我想（学习）发挥作用，而不是 necc。尽可能惯用，我想失去 while 并递归主要算法。

现在我有了这个：

    let apat = Array.map (fun a -> [a]) ( Seq.toArray  pat )

    let rec bjork bpat:list<char> array =
        let (head, rem) = Array.partition (fun v -> (compareSequences v bpat.[0]) = 0) bpat
        match rem.Length > 1 with
        | false -> bpat
        | true ->
            for i=0 to (min head.Length rem.Length)-1 do
                bpat.[i] <-bpat.[i] @ bpat.[^0]
            bjork bpat.[.. ^1]

    let ppat = bjork apat

问题是 compareSequences 的第二个参数：bpat。[0]我收到错误：

运算符 'expr.[idx]' 已根据此程序点之前的信息用于不确定类型的对象。考虑添加更多类型约束

我有点困惑，因为这看起来与 while 循环版本非常相似。我可以看到 compareSequences 的签名不同但不知道为什么。除了可变性之外，apat 在每个版本中都具有相同的类型。第二版中的 bpat 与 apat 类型相同。

while 循环：char list -> char list -> int

记录功能：char list -> seq<char> -> int

我会说我在学习 f# 时遇到了一些奇怪的错误，这些错误最终与代码中其他地方的问题有关，所以希望这不是百灵鸟。

此外，可能还有其他方法可以做到这一点，包括 Bresenham 的线算法，但我正在学习轨道上，这似乎是几个功能概念的好算法。

谁能看到我在这里遗漏了什么？此外，如果精通 functional/f# 范式的人有解决此问题的好方法，我希望看到。

谢谢泰德

编辑：

上面的递归不起作用。只是无法测试。这有效，但仍然有一个可变的。

    let rec bjork (bbpat:list<char> array) =
        let mutable bpat = bbpat
        let (head, rem) = Array.partition (fun v -> (compareSequences v bpat.[0]) = 0) bpat
        match rem.Length > 1 with
        | false -> bpat
        | true ->
            for i=0 to (min head.Length rem.Length)-1 do
                bpat.[i] <-bpat.[i] @ bpat.[^0]
                bpat <- bpat.[.. ^1]
            bjork bpat

Answer 1

您需要在 (bpat:list<char> array) 两边加上括号。否则类型注释适用于 bjork，不适用于 bbpat:

let rec bjork (bbpat:list<char> array) =
  ...

另请注意，计算长度和索引都是 F# 链表上的 O(n) 操作。考虑改为模式匹配。

F# Bjorklund 算法：将 while 循环转换为递归函数：类型约束问题

F# Bjorklund algorithm: convert while-loop to recursive function: type-constraint issue

algorithm

f#

type-constraints