Haskellには、AccumarrayとFoldrの混合物のように機能する機能はありますか?
質問
関数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
解決
なんて奇妙だ...私は数日前に他の誰かのためにこの機能を書いた。この関数は最初に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
それを修正しますが、より良い方法があるかもしれません。
他のヒント
最も効率的ではありませんが...accumrArray f x b l = accumArray (flip f) x b (reverse l)
所属していません StackOverflow