다중 배열과리스트를 반환하는 재귀 함수

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 인스턴스를 사용한다 : 변화 ff의 재귀 호출의 모양을 의미

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

에의 유형을

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

및 h의 완료 후 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의 선택에 의존하지 않도록.