haskell - 数组索引触发元素的重复评估？

Question

我正在编写一个程序来生成以下形式的前 k 个数字

,

其中a和b是非负整数。

我使用的算法利用了这样一个事实:该系列中的每个数字都是通过将 1 或 sqrt(2) 添加到该系列中的前一个数字而生成的，该系列从 0 开始。我们将收集以下中的数字数组中的系列，其中每个元素预计将根据需要进行延迟评估。系列中的第一个数字是 0，因此我们将用 0 初始化数组的第一个元素。我们将维护两个指针 i 和 j，两者都从索引 0 开始(系列中的第一个数字)。系列中的下一个数字是 min(A[i]+1, A[j]+sqrt(2))。如果系列中的下一个数字来自指针 i，则指针 i 将递增(因为我们不想添加1 到 A[i])，类似地，如果系列中的下一个数字来自指针 j，则 j 将递增以指向下一个索引，即 j +1。如果 A[i] + 1 = A[j] + sqrt(2)，i 和 j 都会递增。

我认为下面的代码片段捕获了上述算法，但是，在 ghci 中运行代码时，它看起来像函数 f使用参数 1 0 0 重复调用，并且程序永远不会完成。我不明白这个调用是如何进行的，尽管调用似乎是由 v A.! i 触发的。

import qualified Data.Array as A 
import Debug.Trace 

compute :: Int -> Int -> Double
compute x y = (fromIntegral x) + (fromIntegral y) * (sqrt 2)

firstK :: Int -> [(Int,Int)]
firstK k = A.elems v where 
    v = A.listArray (0,k-1) $ (0,0):f 1 0 0
    f c i j 
        | c == k = [] 
        | otherwise = traceShow (c,i,j) $
            let (ix,iy) = v A.! i 
                (jx,jy) = v A.! j 
                iv      = compute (ix+1) iy 
                jv      = compute jx (jy+1)
            in  if iv < jv 
                    then (ix+1,iy):f (c+1) (i+1) j 
                else if iv > jv 
                    then (jx,jy+1):f (c+1) i (j+1)
                    else (ix+1,iy):f (c+1) (i+1) (j+1)

输出 -

λ> firstK 50
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
(1,0,0)
...
...

Answer 1

chi 的答案详细讨论了代码的确切问题，以及可以让您保留实现想法但获得您希望的答案的修复。但我认为看看本地 Haskell 使用者如何处理相同的算法也很有趣:我将只使用本地列表，而不是指向数组的指针，我将使用列表的指针本身来跟踪我们所在的位置。它看起来像这样:

vs :: [(Int,Int)]
vs = (0,0) : merge [(a+1, b) | (a, b) <- vs] [(a, b+1) | (a, b) <- vs] where
    compute (a,b) = fromIntegral a + fromIntegral b * sqrt 2
    merge xs@(xh:xt) ys@(yh:yt) = case compare (compute xh) (compute yh) of
        LT -> xh:merge xt ys
        EQ -> xh:merge xt yt
        GT -> yh:merge xs yt

在对 merge 的递归调用中，使用 xt (而不是 xs)类似于递增您的 i > 指针；使用 yt(而不是 ys)类似于递增 j 指针。

关于 vs 的一个好处是，你不必提前声明你想要多少对——你只需得到一个惰性的无限列表(直到使用使用的舍入问题)当然，Double 用于计算!)。代码也显着缩短。这是在 ghci 中运行的示例:

> take 10 vs
[(0,0),(1,0),(0,1),(2,0),(1,1),(0,2),(3,0),(2,1),(1,2),(4,0)]