什么是免费monad？

6 回答

• 53

  Edward Kmett的回答显然很棒 . 但是，它有点技术性 . 这是一个可能更容易理解的解释 .

  免费monad只是将仿函数转换为monad的一般方法 . 也就是说，给定任何仿函数 f Free f 是monad . 除非你得到一对函数，否则这不会很有用

  liftFree :: Functor f => f a -> Free f a
  foldFree :: Functor f => (f r -> r) -> Free f r -> r
  

  第一个让你“进入”你的monad，第二个给你一个“走出去”它的方法 .

  更一般地说，如果X是带有一些额外东西P的Y，那么“自由X”是一种从Y到X而不获得额外收益的方式 .

  示例：monoid（X）是具有额外结构（P）的集合（Y），基本上表示它具有操作（您可以想到添加）和某些标识（如零） .

  所以

  class Monoid m where
     mempty  :: m
     mappend :: m -> m -> m
  

  现在，我们都知道名单

  data [a] = [] | a : [a]
  

  好吧，给定任何类型 t 我们知道 [t] 是一个幺半群

  instance Monoid [t] where
    mempty   = []
    mappend = (++)
  

  所以列表是集合（或Haskell类型）中的“免费幺半群” .

  好吧，所以免费的monad是一样的想法 . 我们带一个仿函数，然后给一个monad . 事实上，由于monad可以被视为endo仿函数类别中的monoids，因此定义了一个列表

  data [a] = [] | a : [a]
  

  看起来很像免费monads的定义

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

  并且Monad实例与列表的Monoid实例具有相似性

  --it needs to be a functor
  instance Functor f => Functor (Free f) where
    fmap f (Pure a) = Pure (f a)
    fmap f (Roll x) = Roll (fmap (fmap f) x)
  
  --this is the same thing as (++) basically
  concatFree :: Functor f => Free f (Free f a) -> Free f a
  concatFree (Pure x) = x
  concatFree (Roll y) = Roll (fmap concatFree y)
  
  instance Functor f => Monad (Free f) where
    return = Pure -- just like []
    x >>= f = concatFree (fmap f x)  --this is the standard concatMap definition of bind
  

  现在，我们得到了两个操作

  -- this is essentially the same as \x -> [x]
  liftFree :: Functor f => f a -> Free f a
  liftFree x = Roll (fmap Pure x)
  
  -- this is essentially the same as folding a list
  foldFree :: Functor f => (f r -> r) -> Free f r -> r
  foldFree _ (Pure a) = a
  foldFree f (Roll x) = f (fmap (foldFree f) x)
  

  回复于 2024-04-19T00:03:19+08:00
• 352

  这是一个更简单的答案：Monad是"computes"当monadic上下文被 join :: m (m a) -> m a 折叠时（回想 >>= 可以定义为 (join .) . flip fmap ） . 这就是Monads如何通过顺序计算链来传递上下文：因为在序列中的每个点，前一个调用的上下文都会与下一个调用一起折叠 .

  free monad 满足所有Monad定律，但不进行任何折叠（即计算） . 它只是构建了一系列嵌套的上下文 . 创建这样一个自由monadic值的用户负责使用那些嵌套的上下文做某事，这样这个组合的含义可以推迟到创建monadic值之后 .

  回复于 2024-04-19T00:03:19+08:00
• 57

  一个免费的foo恰好是满足所有'foo'定律的最简单的东西 . 也就是说它完全满足成为foo所必需的法则，而不是额外的 .

  一个健忘的仿函数是一个“忘记”结构的一部分，因为它从一个类别到另一个类别 .

  给定仿函数 F : D -> C 和 G : C -> D ，我们说 F -| G ， F 左边是 G ，或者 G 右边是 F ，只要forall a，b： F a -> b 与 a -> G b 同构，其中箭头来自相应的类别 .

  在形式上，一个自由的仿函数与一个健忘的仿函数相伴 .

  The Free Monoid

  让我们从一个更简单的例子开始，即免费的幺半群 .

  取一个monoid，由一些载体集 T 定义，一个二元函数将一对元素混合在一起 f :: T → T → T 和一个 unit :: T ，这样你就有了一个关联定律和一个同一性定律： f(unit,x) = x = f(x,unit) .

  你可以从幺半群的类别制作一个算子 U （其中箭头是幺半群同态，也就是说，它们确保它们在另一个幺半群上映射 unit 到 unit ，并且你可以在映射到另一个幺半群之前或之后编写而不改变含义）到集合的类别（箭头只是函数箭头）'forgets'关于操作和 unit ，并且只给你载体集 .

  然后，您可以将一个仿函数 F 从集合类别定义回与该仿函数相邻的monoids类别 . 该仿函数是将集合 a 映射到monoid [a] ，其中 unit = [] 和 mappend = (++) 的仿函数 .

  那么到目前为止，回顾我们的例子，在伪Haskell中：

  U : Mon → Set -- is our forgetful functor
  U (a,mappend,mempty) = a
  
  F : Set → Mon -- is our free functor
  F a = ([a],(++),[])
  

  然后要显示 F 是免费的，需要证明它与 U 是一个遗忘的仿函数，也就是说，正如我们上面提到的，我们需要证明

  F a → b 与 a → U b 同构

  现在，记住 F 的目标是幺半群的类别 Mon ，其中箭头是幺半群同态，所以我们需要一个来表明一个同态的同态 [a] → b 可以通过 a → b 中的函数精确描述 .

  在Haskell中，我们称之为 Set （呃， Hask ，我们假装设置的Haskell类型的类别），只有 foldMap ，从 Data.Foldable 到Lists的专用类型为 Monoid m => (a → m) → [a] → m .

  这是一个附带的后果 . 值得注意的是，如果你忘记然后自由积累，那么再次忘记，它就像你忘了一次，我们可以用它来 Build monadic连接 . 从 UFUF ~ U(FUF) ~ UF ，我们可以通过定义我们的adjunction的同构传递从 [a] 到 [a] 的身份monoid同态，得到 [a] → [a] 的列表同构是 a -> [a] 类型的函数，这只是列表的返回 .

  您可以通过使用以下术语描述列表来直接撰写所有这些内容：

  newtype List a = List (forall b. Monoid b => (a -> b) -> b)
  

  The Free Monad

  什么是免费Monad？

  好吧，我们做了我们之前做过的同样的事情，我们从一个健忘的仿函数U开始，从monad类别中箭头是monad同态到一类endofunctors，其中箭头是自然变换，我们寻找一个左边伴随的仿函数那个 .

  那么，这与通常使用的免费monad的概念有什么关系呢？

  知道某个东西是一个自由的monad， Free f ，告诉你从 Free f -> m 给出一个monad同态，与从 f -> m 给出一个自然变换（一个仿函数同态）是同形的（同构的） . 请记住 F a -> b 必须与 a -> U b 同构，因为F要与U同伴 . 这里将monad映射到仿函数 .

  F至少与我在hackage的 free 包中使用的 Free 类型同构 .

  我们还可以通过定义来构建它，以类似于上面的代码为自由列表

  class Algebra f x where
    phi :: f x -> x
  
  newtype Free f a = Free (forall x. Algebra f x => (a -> x) -> x)
  

  Cofree Comonads

  我们可以构造类似的东西，通过查看正确的伴随假定它存在的健忘函子 . 一个cofree仿函数简单地/正确地伴随着一个健忘的仿函数，并且通过对称性，知道一些cofree comonad就像知道从 w -> Cofree f 给出一个comonad同态是与从 w -> f 给出一个自然变换一样的东西 .

  回复于 2024-04-19T00:03:19+08:00
• 127

  Free Monad（数据结构）是Monad（类），类似于List（数据结构）到Monoid（类）：这是一个简单的实现，您可以在其中决定如何组合内容 .

  ---

  你可能知道Monad是什么，每个Monad需要一个特定的（Monad-law持久）实现 fmap join return 或 bind return .

  我们假设您有一个Functor（ fmap 的实现），但其余的依赖于在运行时进行的值和选择，这意味着您希望能够使用Monad属性但是之后想要选择Monad函数 .

  这可以使用Free Monad（数据结构）来完成，它以这样的方式包装Functor（类型），这样 join 就是这些函子的堆叠而不是简化 .

  您想要使用的真实 return 和 join 现在可以作为参数提供给缩减函数foldFree：

  foldFree :: Functor f => (a -> b) -> (f b -> b) -> Free f a -> b
  foldFree return join :: Monad m => Free m a -> m a
  

  为了解释这些类型，我们可以用 Monad m 和 b 替换 Functor f 和 (m a) ：

  foldFree :: Monad m => (a -> (m a)) -> (m (m a) -> (m a)) -> Free m a -> (m a)
  

  回复于 2024-04-19T00:03:19+08:00
• 258

  Haskell免费monad是一个仿函数列表 . 相比：

  data List a   = Nil    | Cons  a (List a  )
  
  data Free f r = Pure r | Free (f (Free f r))
  

  Pure 类似于 Nil ， Free 类似于 Cons . 免费monad存储一个函子列表而不是值列表 . 从技术上讲，您可以使用不同的数据类型实现免费monad，但任何实现都应该与上面的实现同构 .

  只要需要抽象语法树，就可以使用免费的monad . free monad的基础仿函数是语法树每一步的形状 .

  My post，有人已经链接，提供了几个如何使用免费monad构建抽象语法树的示例

  回复于 2024-04-19T00:03:19+08:00
• 21

  我认为一个简单的具体例子会有所帮助 . 假设我们有一个仿函数

  data F a = One a | Two a a | Two' a a | Three Int a a a
  

  有明显的 fmap . 然后 Free F a 是其叶子类型为 a 并且其节点标记为 One ， Two ， Two' 和 Three 的树的类型 . One -nodes有一个子节点， Two - 和 Two' -nodes有两个子节点， Three -nodes有三个节点，并且还标有 Int .

  Free F 是一个单子 . return 将 x 映射到只是叶子的树值为 x . t >>= f 查看每个叶子并用树替换它们 . 当叶子具有值 y 时，它用树 f y 替换该叶子 .

  图表使这更清楚，但我没有轻松绘制一个的设施！

  回复于 2024-04-19T00:03:19+08:00