Как я могу построить монаду недетерминированного состояния в Haskell?

Я хочу построить монаду недетерминированного состояния в Haskell. Это позволит мне сгенерировать все элементы в моем пространстве поиска, используя созданное состояние, чтобы отсечь плохие местоположения. Предположим, у меня есть следующий (псевдо)код:

primitives :: [State Int Element] 
primitives = [... list of primitive stateful elements ...]                                                                                                                      
combine :: Element -> Element -> State Int Element                                                                                                            
expand :: Depth -> [State Int Element]                                                                                                                        
expand 0 = primitives                                                                                                                                         
expand d = do                                                                                                                                                 
  ... do something to the state ...                                                                                                                           
  left <- expand (d-1)                                                                                                                                        
  right <- expand (d-1)                                                                                                                                       
  let out = combine left right                                                                                                                                
  guard ( ... some check on out ... )                                                                                                                         
  return out

Здесь есть несколько вещей, которые не работают: самая основная вещь, которую мне нужно понять, это как сделать что-то, чтобы заявить, а затем передать это каждой из ветвей expand. Я перепробовал множество способов с функциями типа State Int [ State Int Element], но, в конце концов, как только я оборачиваю ветви монады списка в обёртку состояния, я не могу её удалить, верно? Так есть ли способ сделать это?

Спасибо.


haskell state-monad non-deterministic
person Eyal    schedule 12.12.2012    source источник
comment
Монада StateT позволяет вам отслеживать состояние, а также использовать другую монаду, такую ​​как IO или Rand (для случайных значений). Если я правильно понял ваш вопрос, я думаю, что StateT решит вашу проблему. Можете ли вы привести пример того, что вы хотите иметь в массиве primitives?   -  person mhwombat    schedule 12.12.2012
comment
Звучит как преобразователь монады LogicT: hackage.haskell.org/package/logict с вашей монадой недетерминированного состояния будучи LogicT (State Int) Element. Честные союзы, условные предложения и обрезка в качестве бонуса. Более эффективная реализация, чем простой список.   -  person Ed'ka    schedule 13.12.2012
comment
Общее примечание: НЕ создавайте свои собственные комбинированные монады, используйте преобразователи монад.   -  person permeakra    schedule 13.12.2012

Ответы (1)


arrow_upward
14
arrow_downward

Простая монада State определяется как:

data State s a = State (s -> (a, s))

Это представляет собой автономное и детерминированное вычисление с отслеживанием состояния. Рассматривая [] как недетерминированную монаду, вы можете иметь [State s a], представляющий недетерминированный набор детерминированных вычислений, или State s [a], представляющий детерминированное вычисление, производящее недетерминированный набор значений. Ни в том, ни в другом случае в структуре самих вычислений с отслеживанием состояния отсутствует какой-либо недетерминизм.

Чтобы на самом деле объединить поведение состояния и недетерминизма так, как вам кажется, вам нужно объединить их таким образом, который невозможен с использованием только State; это цель преобразователей монад. Тип StateT s [] a эквивалентен:

data NonDetState s a = NonDetState (s -> [(a, s)])

Это дает вам недетерминизм в значении состояния, когда в любой точке вычисления можно наблюдать только отдельные варианты.

Чего это не разрешает, так это любого взаимодействия между ветвями; изменения состояния, сделанные в одной ветви, никогда не будут видны из других ветвей, что обычно требуется при недетерминированных вычислениях.

person C. A. McCann    schedule 12.12.2012