Рекурсивная функция, которая возвращает массив и список

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

Вы должны использовать Monad экземпляр ST s реализовать рекурсивные вызовы f (и состав их результатов): изменить fтип к

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

что означает рекурсивные вызовы в f будет выглядеть примерно так

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

а потом runST это до завершения в h (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,