Haskell中的功能像累积和折叠的混合物一样工作吗？

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

Answer 1

多么奇怪...几天前我为别人写了这个功能。该功能首先出现在LML（我相信）中，但从未进入Haskell Array库。

干得好：

{-# 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 可以解决它，但可能会有更好的方法。

Answer 2

不是最有效的，而是...accumrArray f x b l = accumArray (flip f) x b (reverse l)