3

让我调用函数 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
4

3 回答 3

7

好奇怪……我前几天给别人写了这个函数。该函数首先出现在 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可以解决它，但可能有更好的方法。

于 2011-01-14T20:13:40.883 回答
2

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

于 2011-01-14T16:48:28.627 回答
0

我会争辩说

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

确实是最好的解决方案（归功于 sclv 的回答）。

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

但是，既然accumArray是严格的，l就永远不可能是无限的，否则程序就会不正确。它永远不会终止。

因此，foldl (flip f)与foldr.

于 2020-10-15T21:17:03.537 回答