State Monad Instance

[chebert]

I implemented a monad instance for a state monad based on: https://wiki.haskell.org/State_Monad
I think it actually went really well so I thought I'd share here as a small success story. I haven't tested it much so it could be wrong in spots. Please let me know and I'll fix it.

(coalton-toplevel
  (define-type (state :state :value)
    ;; The state is represented as a function from old-state to (Tuple new-state value)
    ;; It represents the computation of a value in an environment
    (_state (:state -> (Tuple :state :value))))

  ;; A functor requires a map function  
  (declare map-state ((:a -> :b) -> (state :state :a) -> (state :state :b)))
  (define (map-state fa->b sa)
    (match sa
      ((_state fstate)
       ;; The result will be a new (state :state :b)
       (_state
	(fn (state)
	  ;; With the given state, we can extract the a from sa
	  ;; fstate :: state -> (Tuple state :a)
	  (match (fstate state)
	    ((Tuple state a)
	     ;; Now we need to return the tuple for new (state :state :b)
	     ;; with the computed by and the new env
	     (Tuple state (fa->b a)))))))))

  (define-instance (functor (state :state))
    (define map map-state)))


(coalton-toplevel
  ;; An applicative instance requires pure and liftA2
  (declare pure-state (:a -> (state :state :a)))
  (define (pure-state a)
    (_state
     (fn (state)
       ;; Just return a and the original state.
       (Tuple state a))))

  ;; liftA2 applies (fab a b) to get c in the new state
  (declare lifta2-state ((:a -> :b -> :c) -> (state :state :a) -> (state :state :b) -> (state :state :c)))
  (define (lifta2-state fab sa sb)
    ;; To apply (fab a b), we need access to the a and b values from sa and sb
    (match sa
      ((_state fstate)
       ;; To get the a from fstate we need a state
       (_state ; (state :state :c)
	(fn (state)
	  (match (fstate state)
	    ((Tuple state a)
	     ;; We have a, now we need b
	     (match sb
	       ((_state fstate)
		(match (fstate state)
		  ((Tuple state b)
		   ;; Now we have a and b
		   (Tuple state (fab a b))))))))))))))

(coalton-toplevel
  (define-instance (applicative (state :state))
    (define pure pure-state)
    (define lifta2 lifta2-state)))

(coalton-toplevel
  ;; To finish our implementation of the state monad, we need to implement bind (>>=)
  (declare bind-state ((state :state :a) -> (:a -> (state :state :b)) -> (state :state :b)))
  (define (bind-state sa fa->sb)
    ;; We need to get the a from the (state :state :a)
    (match sa
      ((_state fstate)
       ;; fstate needs a state so we can get a
       (_state ; (state :state :b)
	(fn (state)
	  (match (fstate state)
	    ((Tuple state a)
	     (let ((sb (fa->sb a)))
	       ;; Need an (Tuple state :b) from sb
	       (match sb
		 ((_state fstate)
		  (fstate state))))))))))))

(coalton-toplevel
  (define-instance (monad (state :state))
    (define >>= bind-state)))

[stylewarning]

Could you make it a PR in the standard library?

[chebert]

sure. I'll take some time to test/document it

[chebert]

#328