複数の配列とリストを返す再帰関数

Question

私は再帰関数を作成しようとしていますが、簡単にするためにリストとリストを作成してビルドしています。配列の作成と読み込みの両方を行う必要があるので、私は可変配列を使用しているので、一定の時間の読み書きができます。だから、署名と機能次のように次のようになります。

f :: [a] -> ST s ([a], STArray s Int a) -> ST s ([a], STArray s Int a) 
f (x:xs) curr_arr = 
    case blah of 
    ... -> f xs new_arr 
f [] curr_arr = curr_arr 

私は次のシグネチャを持つ関数hをしたい：

h :: Int -> Int -> a -> [a] -> (Array Int a, [a]) 

そして、私はそれが大体次の実装を持つようにしたい：

h lbound ubound default_a xs = g (f xs (newArray lbound ubound default_a)) 

問題は、このシグネチャを持つg関数が必要です。

ST s ([a], STArray s Int a) -> (Array Int a, [a]) 

しかし、私はこれを達成するためにrunSTとrunSTArrayを一緒にハックするように見えることはできません。

とにかくgを実装する必要がありますか、最初にfの署名を完全に違うものにする必要がありますか？

Answer 1

あなたはfへの再帰呼び出し（およびその結果の組成物）を実装するためST sのMonadインスタンスを使用する必要があります。fで再帰呼び出しを意味

f :: [a] -> ([a], STArray s Int a) -> ST s ([a], STArray s Int a) 

に変更fのタイプが検索されますhで完了まで

f xs curr = do 
    xs' <- ... 
    curr' <- ... 
    next <- f xs' curr' 
    combine curr next 

のようなものと、その後runSTそれは（runSTArrayが動作しません。直接ここに、あなたも持っているので、あなたの[a]側）：

h lo hi x0 xs = runST $ do 
    curr <- newArray lo hi x0 
    (ys, mArr) <- f xs (xs, curr) 
    arr <- freeze mArr 
    return (ys, arr) 

これは、そのせいで最後の式で動作し、ys :: [a]とarr :: Array Int a、どちらがsの選択に依存しないようにします。