Haskell에있는 임의 번호와 목록을 포함하는 상태 모나드

Question

내 시험 기능을 배우면서 기능적 프로그래밍, 아직 실제로 시도 중입니다. 모나드. 자신을 정의하는 것보다 더 좋은 방법은 무엇입니까? 나는 이것을 다음과 같이 정의했다 :

newtype ST a = ST (State -> ([a], State)) 
type State = StdGen 

기본적으로 하나의리스트 모나드와 랜덤 모나드. 이 모나드는 임의의 함수와리스트로 작업 할 수 있어야합니다. 이제 return 함수를 정의 할 수 있었기 때문에 문제가 발생하지만 >>=은 그다지 잘하지 못합니다.

instance Monad ST where 
    return a = ST $ \g -> ([a], g) 
    -- M a -> (a -> M b) -> M b 
    st >>= f = ST $ \s -> 
       let (x,s') = st s 
       in (f x) s' 

코드는 This paper p.218

모든 설명은에서 영감을?

Answer 1

모든 유형을 추적하는 데주의를 기울이십시오. (까다로운 코드를 작성할 때는이 방법을 사용하십시오). 먼저 ST 유형에 대한 접근자를 추가하여 작업을 쉽게 만듭니다.

이제 우리는 runST :: ST a -> State -> ([a], State)입니다. 모나드 코드를 정의 할 때 나는 즉시 runST 값을 모두 ST 값에 적용하고 싶습니다. 그래서 실제로 어떤 유형인지 알고 있습니다.

st >>= f = ST $ \s -> 
    -- runST st :: State -> ([a], State) 
    -- f   :: a -> ST b 
    -- runST . f :: a -> State -> ([b], State) 
    -- s   :: State 
    let (as, s') = runST st s in -- I renamed x to as for readability 
    -- as  :: [a] 
    -- s'  :: State 

이제는 ([b], State)이 필요합니다. f을 사용하여 b을 얻을 수 있습니다.

-- map (\a -> runST (f a) s) as :: [([b], State)] 

어쩌면 우리는이 작업 할 수 있습니다 : 우리는 그래서 매핑

-- map (runST . f) as :: [State -> ([b], State)] 

흠을 해보자 s의 a의 목록을 가지고, 그 때문에 유용 아니라, 이제 우리가 너무오고있는 상태를 적용 해보자 . 우리는 b리스트와 다른 것들을 가지고 있습니다.

let rs = map (\a -> runST (f a) s) as in 

이제 우리는 모든 결과 학사 연결하여 b의 목록을 얻을 수 있습니다 : 그래서 아마

let bs = concat (map fst rs) in -- bs :: [b] 

을 우리가 반환 할 것입니다의이은 ("결과"에 대한)이 rs 이름을 보자 . 지금 어느 State 우리는 함께 가고 싶습니까? 선택할 수있는 여러 가지가 많기 때문에 문제가 발생합니다. 우리는 목록에서 마지막 하나를 선택합니까? 목록이 비어 있다면 우리는 단지 State을 반환 할 것입니다. 이들은 임의적 인 선택입니다 - 물리학 교수가 말한 것처럼 : "이제 우리는 선택 사항을 만들어야합니다. 잘못된 것을 만들어라. " 이것은 함수형 프로그래밍에서 매우 사실입니다. 이렇게 임의적으로 선택해야 할 때마다 아마 엉망이 될 것입니다.이 선택 목록을 생성 할의

우리는 단계를 철회하고 ST a 계산이 미래의 계산에 사용하는 상태를 취하고 새로운 상태와 선택의 목록을 반환, 직관적으로 의미에 대해 생각한다면, 각 새로운 상태. concat을 사용하여 모든 목록을 결합 할 수 있지만 모든 상태를 하나로 결합 할 방법이 없습니다. 무작위 API를 사용하면 우리는 이것을 가지지 않습니다 (우리는 아마도 bitxor 모든 상태를 합친 것 같을 것입니다 ...).

상태를 결합하는 방법이 없어도 모나드 바인딩은 데이터의 대부분을 잊어 버릴 수 있습니다. 모나드 바인딩은 법률에 복종하지 않을 것이라는 적절한 신호입니다 (하지만 모나드가 복잡 할 때 나는 복잡성을 두려워합니다. 법을 증명하는 것). 그리고 제가 아는 한이 유형의 모나드는 없습니다. 이

는 이 유형의 모나드입니다 :

newtype ST' a = ST' { runST' :: State -> [(a, State)] } 

그리고 StateT State []에 해당합니다. 이제 계산의 각 가지가 자체 임의의 상태로 제공되므로 많은 상태를 더 이상 하나로 결합 할 필요가 없습니다. 내가 한 것처럼이 모나드를 정의하는 것이 더 좋을 수도 있고, 알고있는 모든 것을 적어두고, 타입 지향적 인 방식으로 필요한 것에 도달하려고 노력할 수도 있습니다. 정보를 "잊어 버리지"않으려 고하고 출력을 구성 할 때 각 입력을 정확히 한 번 사용하도록 노력하십시오.

죄송합니다.이 게시물은 다소 모호하고 멍청했습니다. 저는 모나드를 정의 할 때 많은 직관적 인 원칙을 사용하고 있으며, 내가 공유하려고한다고 생각했습니다. 정의를 얻는 것만으로는 충분하지 않다는 것을 기억하십시오. 그러나 법을 확인하십시오. 그렇지 않으면 do 표기법 등을 사용할 때 이상한 일이 일어납니다.

Answer 2

luqui's lead에 따라, 우리는

st >>= f = ST (g . runST st) 
    -- runST st :: State -> ([a], State) 
    -- f   :: a -> ST b 
    -- runST . f :: a -> State -> ([b], State) 

    where 
     g (a:as,s) = let (bs, s2) = (runST . f) a s 
          (rs, sn) = g (as, s2) 
        in (bs ++ rs, sn) 
     g ([], s) = ([], s) 

를 얻을 수 (테스트하지).