State Monad, содержащий случайные и список в Haskell

Question

Как я учусь для своего экзамена Функциональное программирование, я все еще пытаюсь на самом деле понять Monads. Какой лучший способ, чем определить сам? Я определил это:

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, который упростит ситуацию.

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

Теперь у нас есть 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). Мы можем получить b s, используя f. У нас есть список a ы так давайте попробуем отображение

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

Хм, это не так полезно, давайте попробуем применять состояние мы приходя в тоже:

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

Может быть, мы можем работать с этим , У нас есть список списков b и некоторые другие вещи. Давайте назовем это rs (для «результаты»):

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

Теперь мы можем получить список b с помощью конкатенации всех результатов BS:

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

Так что, вероятно, что мы хотим, чтобы вернуться , Теперь, когда мы хотим пойти с ним? У нас есть проблема, потому что у нас есть много разных State s на выбор. Выберем последний из списка или первый? Если список пуст, возможно, мы просто вернем 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) 

(не проверено).