在Haskell中是否有一种函数，类似于accumArray和foldr的混合功能？

Question

让我调用函数accumrArray。

accumrArray :: 
              (e' -> e -> e) An accumulating function
           -> e              A default element 
           -> (i, i)         The bounds of the array 
           -> [(i, e')]      List of associations 
           -> a i e          The array

accumrArray  (:) [] (1,2) [(1,1),(2,2),(2,3)]  === array [(1,[1]), (2,[2,3])]
head $ (accumrArray (:) [] (1,1) [(1,x)|x<-[4..]]) ! 1 === 4

- Lin Jin

Answer 1

多么奇怪啊……几天前我为别人写了这个函数。我相信这个函数最初出现在LML中，但从未被添加到Haskell数组库中。

这是函数：

{-# LANGUAGE ScopedTypeVariables #-}
import Data.Array
import System.IO.Unsafe
import Data.IORef
import Data.Array.MArray
import Data.Array.Base
import Control.Monad
import Data.Array.IO

accumArrayR :: forall a e i. Ix i => (a -> e -> e) -> e -> (i,i) -> [(i,a)] -> Array i e
accumArrayR f e bounds@(l,u) assocs = unsafePerformIO $ do
  ref <- newIORef assocs
  arr <- newArray_ bounds
  let _ = arr :: IOArray i e
  let n = safeRangeSize (l,u)
  let elem x = unsafePerformIO $ do
                  ass <- readIORef ref
                  let loop [] = writeIORef ref [] >> return e
                      loop ((y,a):rest) = do
                         let ix = safeIndex bounds n y
                         let r = f a (elem x)
                         unsafeWrite arr ix r
                         if (ix == x)
                            then writeIORef ref rest >> return r
                            else loop rest
                  loop ass
  forM_ [0..n] $ \ix -> unsafeWrite arr ix (elem ix)
  unsafeFreeze arr

一个读者的挑战：使用accumArrayR实现线性时间的深度优先搜索图。 编辑 我应该提到，该函数按原样不是线程安全的。将IORef转换为MVar可以解决问题，但可能有更好的方法。

- Simon Marlow

---

通过谷歌搜索lml和accumArray，我找到了这篇来自1993年的邮件列表历史记录：http://www.mail-archive.com/[e-mail]/msg01394.html - sclv

我是唯一一个对“loop ass”感到惊讶的人吗？ - Dan Burton

Answer 2

虽然不是最高效的方法，但是... accumrArray f x b l = accumArray (flip f) x b (reverse l)

- sclv

---

但它无法处理无限列表(l)。 - Lin Jin

Answer 3

我认为

accumrArray f x b l = accumArray (flip f) x b (reverse l)

确实是最好的解决方案（感谢sclv的回答）。

它所谓的“低效性”来自于foldr从右到左应用函数f的事实。

然而，由于accumArray是严格的，l永远不可能是无限的，否则程序将不正确。它永远不会终止。

因此，foldl (flip f)和foldr一样好。

- mentatkgs