标签: free-monad

考虑以下示例。

newtype TooBig = TooBig Int deriving Show

choose :: MonadPlus m => [a] -> m a
choose = msum . map return

ex1 :: (MonadPlus m, MonadError TooBig m) => m Int
ex1 = do
    x <- choose [5,7,1]
    if x > 5
        then throwError (TooBig x)
        else return x

ex2 :: (MonadPlus m, MonadError TooBig m) => m Int
ex2 = ex1 `catchError` handler
  where
    handler (TooBig x) = if x > 7
        then throwError (TooBig x)
        else …

这个伟大的免费套餐中有一个很好的免费替代品,它将Functor提升为左派分配.

也就是说,声称是:

runAlt :: Alternative g => (forall x. f x -> g x) -> Alt f a -> g a

是一种替代同态,有liftAlt.事实上,它只是一个,但仅适用于左派分配的替代实例.

当然,实际上,很少有替代实例实际上是左分配的.大多数实际上重要的替代实例(解析器,对于大多数Monad f来说,MaybeT f等)都不是左分配的.这个事实可以通过一个例子来表示,其中runAlt和liftAlt不形成一个Alternative同态:

(writeIORef x False <|> writeIORef True) *> (guard =<< readIORef x)
-- is an IO action that throws an exception
runAlt id $ (liftAlt (writeIORef x False) <|> liftAlt (writeIORef True))
               *> liftAlt (guard =<< readIORef x)
-- is …

在尝试找到可以逐步执行/允许线程化的haskell monad时,我发现了自由monad

data Free f a = Return a | Roll (f (Free f a))

用它的monad实例

instance (Functor f) => Monad (Free f) where
  return = Return
  Return x    >>= f = f x
  Roll action >>= f = Roll $ fmap (>>= f) action

和它的仿函数实例

instance (Functor f) => Functor (Free f) where
  fmap f (Return x) = Return (f x)
  fmap f (Roll   x) = Roll $ fmap (fmap f) x

我知道每个monad都是一个带有pure = return和的应用函子(<*>) = …

最近有一个关于< - > 与< - > 之间关系的问题.DList[]CodensityFree

这让我想到是否有这样的事情MonadPlus.该Codensity单子只提高了一元操作,而不是为渐近性能mplus.

而且,虽然曾经有过Control.MonadPlus.Free,但它已经被删除了FreeT f [].由于没有明确的免费MonadPlus,我不确定如何表达相应的improve变体.也许是这样的

improvePlus :: Functor f => (forall m. (MonadFree f m, MonadPlus m) => m a) -> FreeT f [] a

？

更新:我尝试使用回溯LogicTmonad 创建这样的monad ,它似乎以类似于以下的方式定义Codensity:

newtype LogicT r m a = LogicT { unLogicT :: forall r. (a -> m r -> m …

Run Code Online (Sandbox Code Playgroud)

为了说清楚,我不是在谈论自由monad看起来很像一个应用于仿函数的固定点组合器,即Free f基本上是一个固定点f.(不是说这不好玩!)

我正在谈论的是固定点Free, Cofree :: (*->*) -> (*->*),即仿函数f,使得Free f同构于f自身.

背景:今天,坚定了我对自由的单子,而缺乏把握,我决定只写了他们的出来不同的简单仿函数,既为Free与对Cofree,看看有什么更好的知名[合作]单子他们会在同构.是什么吸引了我特别的是发现那Cofree Empty是同构的Empty(意思是,Const Void的任何类型映射到无人居住的仿函数).好吧,也许这只是愚蠢 - 我发现如果你把空垃圾放进去,你就会把空垃圾拿出来,是的! - 但是,嘿,这是类别理论,整个宇宙从看似琐碎的事物中崛起......对吧？

当前的问题是,如果Cofree有这样一个固定点,那又怎么样Free？嗯,它当然不能是Empty那不是一个单子.快速嫌疑人将附近的东西像Const ()或者Identity,但没有:

Free (Const ()) ~~ Either () ~~ Maybe
Free Identity   ~~ (Nat,)    ~~ Writer Nat

实际上,Free总是添加额外构造函数的事实表明,任何一个固定点的仿函数的结构必须已经是无限的.但似乎奇怪的是,如果Cofree有这样一个简单的定点,Free应该只有一个更复杂的定义点(就像FixFree a = …

在这个答案中"Monad可以成为一个comonad吗？" 我们看到了

每个Cofree Comonad对一个Alternative functor都会产生一个Monad.

什么是双重的？是否有一类函子可以自动为它们创建一个免费的monad？

几个星期前,Dragisa Krsmanovic 在这里问了一个关于如何在Scalaz 7中使用免费monad来避免堆栈溢出的问题(我已经调整了他的代码):

import scalaz._, Scalaz._

def setS(i: Int): State[List[Int], Unit] = modify(i :: _)

val s = (1 to 100000).foldLeft(state[List[Int], Unit](())) {
  case (st, i) => st.flatMap(_ => setS(i))
}

s(Nil)

我认为只是举起一个蹦床StateT应该工作:

import Free.Trampoline

val s = (1 to 100000).foldLeft(state[List[Int], Unit](()).lift[Trampoline]) {
  case (st, i) => st.flatMap(_ => setS(i).lift[Trampoline])
}

s(Nil).run

但它仍然打击堆栈,所以我只是将其作为评论发布.

Dave Stevens刚刚指出用应用程序*>而不是monadic 进行排序flatMap实际上运行得很好:

val s = (1 to 100000).foldLeft(state[List[Int], Unit](()).lift[Trampoline]) {
  case …

我试图根据我在网上阅读的一些有用的文献,使用Free monad构建AST.

我有一些关于在实践中使用这些AST的问题,我已经归结为以下示例.

假设我的语言允许以下命令:

{-# LANGUAGE DeriveFunctor #-}

data Command next
  = DisplayChar Char next
  | DisplayString String next
  | Repeat Int (Free Command ()) next
  | Done
  deriving (Eq, Show, Functor)

我手动定义了Free monad样板:

displayChar :: Char -> Free Command ()
displayChar ch = liftF (DisplayChar ch ())

displayString :: String -> Free Command ()
displayString str = liftF (DisplayString str ())

repeat :: Int -> Free Command () -> Free Command ()
repeat times block = liftF (Repeat times …

所以我正在努力做一些小说(我想),但是我对Haskell类型级编程没有足够的经验来自己解决这个问题.

我有一个免费的monad描述了一些要执行的效果(AST,如果这就是你滚动的方式),我想根据预期效果的某些描述来解释它.

到目前为止这是我的代码::

{-# LANGUAGE DeriveFunctor, FlexibleInstances, GADTs, FlexibleContexts #-}
import Control.Monad.Free -- from package 'free'

data DSL next
    = Prompt String (String -> next)
    | Display String next
    deriving (Show, Functor)

prompt p = liftF (Prompt p id)
display o = liftF (Display o ())

-- |Just to make sure my stuff works interactively
runIO :: (Free DSL a) -> IO a
runIO (Free (Prompt p cont)) = do
    putStr p
    line <- getLine
    runIO (cont line)
runIO (Free …

在"数据类型单点"中,Swierstra写出给定的Free(他称之为Term)并且Zero您可以实现Identity monad:

data Term f a = Pure a
              | Impure (f (Term f a))
data Zero a

Term Zero现在是身份monad.我明白为什么会这样.问题在于,Term Zero由于令人讨厌的Functor f =>约束,我永远不能用作Monad :

instance Functor f => Monad (Term f) where
    return x = Pure x
    (Pure x) >>= f = f x 
    (Impure f) >>= t = Impure (fmap (>>=f) t) 

如何制作ZeroFunctor？

instance Functor Zero where
    fmap f z = ???

好像有一个窍门在这里:由于Zero没有构造,Impure …