8

この C コードは、入力配列と同じであるが最初の要素として 1 を持つ新しい配列を作成するものとして概念的に説明できます。

int* retire_and_update(int* arr) {
    arr[0] = 1;
    return arr;
}

これは、入力配列とその要素がさらに参照されない限り、純粋な関数 (wink wink nudge nudge) です。C 型システムはそれを強制しませんが、原則として強制できるようです。

gcc が生成するコードはシンプルで効率的です。

retire_and_update:
    movq    %rdi, %rax
    movl    $1, (%rdi)
    ret

私たちの関数は、まったく新しい配列を一定時間で作成し、追加のメモリを使用しないことで、一見不可能なことを実現します。良い。同様のコードで有効に実装できる、配列のような入力と出力を持つ Haskell 関数を作成できますか? 純粋な関数が舞台裏で変数を共食いできるように、「これがこの変数への最後の参照です」と表現する方法はありますか?

関数がインライン化された場合、ここで興味深いことは何も起こらないので、呼び出し元と関数が別々にコンパイルされると仮定しましょう。

4

1 に答える 1

6

ST monad正確にはあなたが説明したものではありませんが、実際には を使用してそのほとんどを実装できますSTUArray。したがって、コードのモックアップは次のようになります。

import Control.Monad (forM_)
import Control.Monad.ST (ST)
import Data.Array.Unboxed (UArray)
import Data.Array.ST (STUArray, newArray, readArray, writeArray, runSTUArray)

retire_and_update :: STUArray s Int Int -> ST s (STUArray s Int Int)
retire_and_update arr = do
    writeArray arr 0 1
    return arr

次のように、配列をその場で変更する別の関数がある場合:

mutate_inplace :: STUArray s Int Int -> Int -> ST s ()
mutate_inplace arr size = do
    forM_ [2..size - 1] $ \i -> do
        a <- readArray arr (i - 2)
        b <- readArray arr (i - 1)
        writeArray arr i (a + b)

2つの不純な関数を一緒にバインドし、次を使用して純粋な関数内で呼び出すことができますrunSTUArray:

run :: Int -> UArray Int Int
run size = runSTUArray $ do
    arr <- newArray (0, size - 1) 0
    retire_and_update arr
    mutate_inplace arr size
    return arr

run純粋なままであり、返された配列の以前のバージョンがどこにも漏れていないことに注意してください。

\> run 8
array (0,7) [(0,1),(1,0),(2,1),(3,1),(4,2),(5,3),(6,5),(7,8)]
于 2015-11-20T13:28:33.963 に答える