0

我正在尝试构建一个递归函数，为简单起见，假设它需要一个列表并构建一个数组和一个列表。因为我需要在构建数组时读取和写入数组，所以我使用了一个可变数组，所以我可以进行恒定时间的读取和写入。所以签名和函数如下所示：

f :: [a] -> ST s ([a], STArray s Int a) -> ST s ([a], STArray s Int a)
f (x:xs) curr_arr = 
  case blah of
    ... -> f xs new_arr
f [] curr_arr = curr_arr

我想要一个h具有以下签名的函数：

h :: Int -> Int -> a -> [a] -> (Array Int a, [a])

我希望它具有大致以下实现：

h lbound ubound default_a xs = g (f xs (newArray lbound ubound default_a))

问题是，我需要一个g带有这个签名的函数：

ST s ([a], STArray s Int a) -> (Array Int a, [a])

但我似乎无法一起破解runST并runSTArray实现这一目标。

无论如何要实施g，还是我应该f首先制作完全不同的签名？

4

1 回答 1

0

您应该使用 的Monad实例ST s来实现对f（及其结果的组合）的递归调用：将f的类型更改为

f :: [a] -> ([a], STArray s Int a) -> ST s ([a], STArray s Int a)

这意味着递归调用f看起来像

f xs curr = do
    xs' <- ...
    curr' <- ...
    next <- f xs' curr'
    combine curr next

然后runST它完成h（runSTArray在这里不能直接工作，因为你也有你[a]的）：

h lo hi x0 xs = runST $ do
    curr <- newArray lo hi x0
    (ys, mArr) <- f xs (xs, curr)
    arr <- freeze mArr
    return (ys, arr)

这是有效的，因为在最后一个表达式中，ys :: [a]和arr :: Array Int a，所以都不依赖于 的选择s。

于 2016-11-04T02:13:53.107 回答