この投稿はリテラシーな Haskell です。「pad.lhs」のようなファイルを入れるだけでghci実行できます。
> {-# LANGUAGE GADTs, Rank2Types #-}
> import Control.Monad
> import Control.Monad.ST
> import Data.STRef
STさて、モナドを純粋なコードで表現する方法を理解することができました。まず、参照型から始めます。その特定の値はそれほど重要ではありません。最も重要なことは、PT s a他の型と同型であってはならないということforall sです。()(特に、どちらとも同形である必要はありませんVoid。)
> newtype PTRef s a = Ref {unref :: s a} -- This is defined liked this to make `toST'` work. It may be given a different definition.
の種類はsですが*->*、現時点ではあまり重要ではありません。それはpolykindである可能性があります。
> data PT s a where
> MkRef :: a -> PT s (PTRef s a)
> GetRef :: PTRef s a -> PT s a
> PutRef :: a -> PTRef s a -> PT s ()
> AndThen :: PT s a -> (a -> PT s b) -> PT s b
かなり簡単です。AndThenこれを として使用できますMonad。returnがどのように実装されているのか疑問に思われるかもしれません。runPF以下はそのモナドのインスタンスです (後で定義されるに関するモナド法則のみを尊重します):
> instance Monad (PT s) where
> (>>=) = AndThen
> return a = AndThen (MkRef a) GetRef --Sorry. I like minimalism.
> instance Functor (PT s) where
> fmap = liftM
> instance Applicative (PT s) where
> pure = return
> (<*>) = ap
fibこれで、テスト ケースとして定義できます。
> fib :: Int -> PT s Integer
> fib n = do
> rold <- MkRef 0
> rnew <- MkRef 1
> replicateM_ n $ do
> old <- GetRef rold
> new <- GetRef rnew
> PutRef new rold
> PutRef (old+new) rnew
> GetRef rold
そして、それはチェックを入力します。万歳！これで、これを に変換できましたST(なぜ でsなければならなかったのかがわかります* -> *)
> toST :: PT (STRef s) a -> ST s a
> toST (MkRef a ) = fmap Ref $ newSTRef a
> toST (GetRef (Ref r)) = readSTRef r
> toST (PutRef a (Ref r)) = writeSTRef r a
> toST (pa `AndThen` apb) = (toST pa) >>= (toST . apb)
これで、まったくPT参照せずに実行する関数を定義できます。ST
> runPF :: (forall s. PT s a) -> a
> runPF p = runST $ toST p
runPF $ fib 7これは13正しいです。
runPF私の質問は、まったく使用せずに参照なしで定義できますSTか?
定義する純粋な方法はありますrunPFか? PTRefの定義はまったく重要ではありません。とにかく、それは単なるプレースホルダー型です。それを機能させるものに再定義できます。
純粋に定義できない場合は、できないrunPFことを証明してください。
パフォーマンスは問題ではありません (もしそうなら、私はすべてreturnに独自の参照を持たせなかったでしょう)。
存在型が役に立つかもしれないと考えています。
a注:が動的か何かであると仮定すると、それは自明です。すべてで機能する答えを探していますa。
注: 実際、答えは とは必ずしも関係ありませんPT。ST魔法を使わないのと同じくらい強力である必要があります。(からの変換(forall s. PT s)は、回答が有効かどうかの一種のテストです。)