2004-09-02 [長年日記]
λ. Re: Functor と Monad
圏論の普通の定義ではモナドは関手と二つの自然変換からなるので、MonadならばFunctorだというのはその通りです。ちなみに、[haskell-jp:51]によれば、「Goferで型クラスが導入されたとき」には「Monad になるためには、Functor でなければいけなかった」そうです。
で、両者の実装を変える理由ですが、やはり効率があるんじゃないでしょうか。例えばリストの場合、fmap f [a,b,c]
が [f a, f b, f c]
を計算すれば良いのに対して、liftM f [a,b,c]
は [f a] ++ [f b] ++ [f c]
を計算するので、多少効率が悪そうですし。
λ. "Graph Rewriting Semantics for Functional Programming Language", Marko van Eekelen, Sjaak Smetsers, Rinus Plasmeijer
Concurrent Clean とかの意味論で使われてる項グラフ書き換え系(TGRS, Term Graph Rewriting System)の説明と、その上での Uniqueness Typing の定式化。項書き換え系(TRS, Term Rewriting System)ではなく項グラフ書き換え系を用いるのは、共有を明示的に扱えて、関数型言語の実態に近いから。
そういえば、uniquenessの様な性質に関するpolymorphismのアイディアは"Quasi-Linear Types"にもあったな。