Stateモナド typeシノニム

Question

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

という記述を見かけたのですが、これをMonadのインスタンスに出来るものでしょうか？
要するにnewtypeを使わずにって事です。
とりあえずコンパイラのバージョンとかはなんでも良いです。
言語拡張とかもいくら使っても良いです。

ちなみに、Stateの仲間であるReaderとかWriterとかはPreludeでは

instance Monad ((->) a) where
    ...
instance Monad ((,) a) where
    ...

みたいな感じで実装されてるみたいです。

Answer 1

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

このシノニムを Monad インスタンスにできません。

Haskell の Monad インスタンスは、

M :: Type -> Type
instance Monad M where
    ...

の形しかできません。

((->) r) と ((,) w) は下記の通りこの形にあっています。

(->) r x :: Type
(->) r   :: Type -> Type
instance Monad ((->) r) where
    ...

(,) w x :: Type
(,) w   :: Type -> Type
instance Monad ((,) w) where
    ...

ですが、s -> (x, s) はその形にあっていません。

(->) s ((,) x s) :: Type
???              :: Type -> Type

s は引数にも戻り値にもあるから、シノニムだけで Type -> Type の形にならないのです。

それができる言語もあるけど、Haskell ではありません。できるのに Kind-level の高階関数が必要です。Coq, Agda, Lean prover みたいな証明支援システムができるかもしれません。が、Lean の monad のソースを読んだら、そちらも新しいコンストラクタを作っています。

newtype を用いて、Type -> Typeの形にできます。

newtype State s x = State { runState :: s -> (x, s) }

State s x :: Type
State s   :: Type -> Type
instance Monad (State s) where
    ...