Государственная монада в OCaml - PullRequest
Новая
       27

Государственная монада в OCaml

14 голосов
/ 30 апреля 2011

Я пытался реализовать монаду состояния в OCaml (как упражнение).Моя реализация выглядит следующим образом: 

module type MONAD_BUILDER =
sig
  type 'a t
  val return : 'a -> 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
end;;

module MonadBuilder = functor (M: MONAD_BUILDER) ->
struct
  let ( >>= ) = M.bind
  let return = M.return
end;;

module StateM = 
struct
  type 'a state = { state: 's . 's -> ('a * 's) }
  type 'a t = 'a state
  let return x = { state = fun s -> (x, s) }
  let bind m f = 
    let aux s = 
      let (x, s') = m.state s in
      (f x).state s'
    in { state = aux }
  let run m x = fst (m.state x)
end;;

Я выбрал экзистенциальный тип для поля записи, поскольку мне не нравится идея использования функтора и переноса типа состояния в модуль.Вышеуказанная реализация работает, но я столкнулся с проблемой при реализации getState и setState.Я пытался реализовать их следующим образом: 

let getState = { state = fun s -> (s, s) }

let setState s = { state = fun _ -> ((), s) }

Это не работает, поскольку выведенные типы полей, например 'a -> ('a * 'a) и 'a -> (unit * 'a), являются менее общими, чем объявленный тип 's . 's -> ('a * 's).Я понимаю, почему это происходит, но мне было интересно, есть ли другой способ заставить это работать, используя подход записи?

Спасибо.

Приветствия, Алекс

1 Ответ

13 голосов
/ 01 мая 2011

's. 's -> ('a * 's) - универсальный тип.Вам будет трудно реализовать состояние с универсальными типами ...

Там нет чистого способа инкапсуляции экзистенциального типа без использования модуля (потому что экзистенциальные типы - это то, для чего нужны абстрактные типы).

Конечно, вместо этого вы можете опубликовать тип состояния: 

type ('a,'s) state = { state : 's -> ('a * 's) }

Или даже короче, 

type ('a,'s) state = 's -> 'a * 's

С дополнительным параметром ваш код запускается.Однако вы сталкиваетесь с тем, что ваш параметр должен обрабатываться монадой.Таким образом, вы можете либо скрыть это при построении монады: 

module Monad = MonadBuilder(struct
  include StateM
  type 'a t = ('a,myStateType) state
end)

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

module type MONAD_BUILDER =
sig
  type ('a,'param) t
  val return : 'a -> ('a,'param) t
  val bind : ('a,'param) t -> ('a -> ('b,'param) t) -> ('b,'param) t
end;;
...