结构强制的自由选择，没有左派分配

本文介绍了结构强制的自由选择，没有左派分配的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 有一个不错的免费替代 a>在伟大的 free 包中，它将一个Functor提升到一个左分配的Alternative。 也就是说， / p> runAlt :: Alternative g => （全部x，f x - > g x） - > Alt f a - > ga 是一个替代同态， liftAlt 。实际上，它是之一，但仅限于 left-distributive 其他实例。 当然，实际上，很少有其他实例实际上是左分配的。实际上很重要的大多数备选实例（解析器，大多数Monad f的MaybeT f等）都不是左派分配。这个事实可以通过一个例子来展示，其中 runAlt 和 liftAlt 不形成替代同态： （writeIORef x False< |> writeIORef True）*> （guard =< readIORef x） - 是抛出异常的IO动作 runAlt id $（liftAlt（writeIORef x False）< |> liftAlt（writeIORef True）） *> liftAlt（guard =<< readIORef x） - 是一个IO动作，它不会抛出异常并成功返回（） 因此， runAlt 只是替代选项的替代同态，但不是全部。这是因为 Alt 的结构规范化了所有要分发到左侧的操作。 Alt 非常棒，因为在结构上 Alt f 是合法的 Applicative $ c>和另类。没有任何可能的方法使用Applicative和Alternative函数来构造类型 Alt fa 的值，这些函数不遵循法律......类型本身的结构是什么使它成为一个免费的选择。 就像列表一样，你不能使用<> 和 mempty ，它不尊重 x<> mempty = x ， mempty<> x = x 和关联性。 我写了一个免费的替代方案，不会执行应用程序和结构上的替代法则，但确实会产生一个有效的替代和应用同态：runB $ >数据Alt ::（* - > *） - > * - > *其中 Pure :: a - > Alt f a Lift :: f a - > Alt f a Empty :: Alt f a Ap :: Alt f（a - > b） - > Alt f a - > Alt f b Plus :: Alt f as - >替换为 - >替换为 实例Functor f => Functor（Alt f）其中 fmap f = \ case Pure x - >纯（f x）提升x - >提升（f< $> x）空 - >>清空 Ap fs xs - > Ap（（f。）< $> fs）xs Plus xs ys - >加（f $ $ xs）（f $ ys） 实例Functor f =>应用（Alt f）其中 pure = Pure （*）= Ap 实例Functor f =>替代方案（Alt f）其中 empty =空（< |>）=加 在结构上， Alt f 不是实际的 Applicative ，因为： 纯f *纯x = Ap（纯f）（纯x​​）纯（fx）=纯（fx） 纯f *纯x 在结构上与 pure（f x）不同。 不是有效的申请人， >和 liftAlt ： liftAlt :: fa - > Alt f a liftAlt =提升 runAlt ::可选g => （全部x，f x - > g x） - > Alt f a - > g a runAlt f = \ case Pure x - >纯x 提升x - > f x 空 - >空 Ap fs xs - > runAlt f fs * runAlt f xs Plus xs ys - > runAlt f xs< |> runAlt f ys 和 runAlt 作为一个有效的应用同态与一个给定的自然转换... 可以说我的新 Alt f 是一个有效的替代方案和适用性，当被以 runAlt 定义的等价关系进行定向时，我想是的。无论如何，这个只是稍微不令人满意。是否有任何方法可以编写一个免费的替代方案，它是结构上一个有效的替代方案和申请方案，没有强制执行左分配方案？ 左派法律感兴趣，并且这是一个独立而有趣的事情，但并非完全必要。） 而且，如果没有办法，为什么不呢？ p> 解决方案 Control.Alternative.Free 的 Alt即使 f 不是，f 会自由生成左分配 Alternative code>替代或 f 是一个非剩余分配替代。我们可以说，除了商定好的替代性法律之外，还有一些其他的法律规定。 x = x x< |> empty = x （x< |> y）< |> z = x< |> （y< |> z）空<> f =空 Alt f - （a< |> b）*< c =（a * c）< |> （b * c） 因为 Alt f 永远是分配的（并且 runAlt。liftAlt = id ） liftAlt 永远不会是非同态的-left-distributive 替代 s。如果 Alternative f 不是分配的，则存在 a ， b 和 c ，这样 （a< ; |> b）< *> c！=（a * c）< |> （b * c） 如果 liftAlt：f - > ; （a< |> b）*>< b>< b> ; c！=（a * c）< |> （b * c）-f不是左分配的 id（（a | b）* c）！= id（（a * c）< |>（b * c）） runAlt。 liftAlt（（a | b）* c）！= runAlt。 liftAlt（（a * c）|（b * c）） - runAlt。 （liftAlt a * liftAlt c）* = runAlt（（liftAlt a * liftAlt c）|（liftAlt）（liftAlt a * liftAlt b） b * liftAlt c）） - 同态 runAlt（（liftAlt a | liftAlt b）* liftAlt c）！= runAlt（（liftAlt a< liftAlt b）* liftAlt c） - 通过左侧分配Alt，这是一个矛盾 为了证明这一点，我们需要一个不是剩余分配的 Alternative 。这是一个 FlipAp [] 。 newtype FlipAp fa = FlipAp { unFlipAp :: fa} 派生显示 实例Functor f => Functor（FlipAp f）其中 fmap f（FlipAp x）= FlipAp（fmap f x） 实例适用f => Applicative（FlipAp f）其中 pure = FlipAp。纯（FlipAp f）* （FlipAp xs）= FlipAp（（flip（$）$ $ xs）* f） 实例可选的f =>替代（FlipAp f）其中 empty = FlipAp空（FlipAp a）< |> （FlipAp b）= FlipAp（a< |> b） 分配和权利分配，以及一些例子 leftDist :: Alternative f => f（x→y）→> f（x→y）→> f x - >示例（f y） leftDist a b c = [（a< |> b）< c，（a * c）< |> （b * c）] rightDist :: Alternative f => f（x→y）→> f x - > f x - >示例（f y） rightDist a b c = [a< *> （b< |> c），（a * b）< |> （a * c）] 类型示例a = [a] ldExample1 :: Alternative f =>示例（f Int） ldExample1 = leftDist（纯（+1））（纯（* 10））（纯2<纯3） rdExample1 :: f =>示例（f Int） rdExample1 = rightDist（纯（+1）< |>纯（* 10））（纯2）（纯3） pre> 我们可以演示列表的一些属性， FlipAp 列表和 runAlt 。 列表是左分配的，但 FlipAp 列表不是 ldExample1 ::示例[Int] ldExample1 ::示例（FlipAp [] Int） [[3,4,20,30]，[3,4,20,30]] [FlipAp {unFlipAp = [3,20,4,30]}，FlipAp {unFlipAp = [3,4， 20,30]}] 列表不是正确的分配，但 FlipAp 列表 rdExample1 ::示例[Int] rdExample1 ::示例FlipAp [] Int） [[3,4,20,30]，[3,20,4,30]] [FlipAp {unFlipAp = [3,20,4， 30]}，FlipAp {unFlipAp = [3,20,4,30]}] Alt 总是左分配的 map（runAlt id）ldExample1 :: Example [Int] map（runAlt id）l dExample1 :: Example（FlipAp [] Int） [[3,4,20,30]，[3,4,20,30]] [FlipAp {unFlipAp = [3 ，4,20,30]}，FlipAp {unFlipAp = [3,4,20,30]}] Alt 永远不会是正确的 - 分配 map（runAlt id ）rdExample1 :: Example [Int] map（runAlt id）rdExample1 ::示例（FlipAp [] Int） [[3,4,20,30]，[3,20 ，4,30]] [FlipAp {unFlipAp = [3,4,20,30]}，FlipAp {unFlipAp = [3,20,4,30]}] FlipAp 和 Alt 。 runFlipAlt :: forall fg a。可选的g => （全部x，f x - > g x） - > FlipAp（Alt f）a - > g a runFlipAlt nt = runAlt nt。 unFlipAp FlipAp $ b map（runFlipAlt id）ldExample1 :: Example [Int] map（runFlipAlt id）ldExample1 :: Example（FlipAp [] Int） [[3,20,4,30]，[3,4,20,30]] [FlipAp {unFlipAp = [3,20,4,30]}，FlipAp {unFlipAp = [3,4,20,30]}] FlipAp Alt 总是正确的分配 map（runFlipAlt id）rdExample1 ::示例[Int] map（runFlipAlt id）rdExample1 ::示例（FlipAp [] Int） [[3,20,4,30]，[3,20,4,30]] [FlipAp {unFlipAp = [3,20,4,30]}，FlipAp {unFlipAp = [3,20,4,30]}] 直到现在我还没有告诉你任何你没有暗示的话： liftAlt：f - > Alt f 是替代同态，但仅限于左分配替代实例。但是我已经向你展示了一个不存在剩余分配的自由选择（它很平凡 - 反而是分配）。 一个结构有效的免费替代 本节回答您的问题的大部分内容，是否存在结构有效的免费替代那不是左派 - 分配？是的。 这不是一个有效的实现;它的目的是证明它存在，并且它的某些版本可以以直接的方式得到。 为了使结构上有效的免费另类我正在做两件事。首先是创建一个不能表示任何 Alternative 定律的数据结构;如果它不能代表法律，那么不能独立于类型类别来构造结构来违反它。这与用于使列表在结构上服从 Alternative 结合律的技巧相同;没有可以表示与左相关的（x< |> y）< |>的列表。 ž。第二部分是确保运营服从法律。列表不能代表左边的关联法则，但< |> 的实现仍然可能违反它，如 x< |> ; y = x ++ reverse y 。 无法构造以下结构来表示任何替代法律。 { - ＃语言GADTs＃ - } { - ＃Language DataKinds ＃ - } { - ＃语言KindSignatures＃ - } 数据Alt ::（* - > *） - > * - > *其中 Alt :: Alt'空纯加f a - > Alt f a - 空纯加数据Alt':: Bool - >布尔 - >布尔 - > （* - > *） - > * - > * where Empty :: Alt'True False f a Pure :: a - > Alt'False True False f a Lift :: f a - > Alt'False False False f a Plus :: Alt'False pure1 False f a - > Alt'False pure2 plus2 f a - > Alt'False False True f a - Empty不能位于Plus - empty< |>的左侧或右侧。 x = x - x< |> empty = x - Plus不能在Plus - （x< |> y）< |>的左边。 z = x< |> （y< |> z） Ap :: Alt'False False plus1 f（a - > b） - > Alt'空False plus2 f a - > Alt'False False False f b - Empty不能在'Ap`左边' - empty *< f =空 - Pure不能在'Ap` - 纯id *的左边或右边。 v = v - 纯（。）* u * v * w = u * （v * w） - 纯f *纯x =纯（f x） - u *纯y =纯（$ y）* u 这是 Functor 实例Functor f => Functor（Alt'empty pure plus f）where fmap _ Empty = Empty fmap f（Pure a）= Pure（fa） fmap f（Plus a as）= Plus（fmap fa ）（fmap f as） fmap f（Lift a）= Lift（fmap fa） fmap f（Ap ga）= Ap（fmap（f。）g）a 实例Functor f => Functor（Alt f）其中 fmap f（Alt a）= Alt（fmap fa） 它是 Applicative 。由于结构不能代表法律，当我们遇到包含一个不可预知表达式的术语时，我们不得不将它转换成其他东西。法律告诉我们该怎么做。 实例Functor f =>应用（Alt f）其中纯a = alt（纯a） 备用空*< _ = Alt空 - 空* f =空 Alt（Pure f）* * （Alt x）= Alt（f map f x） - 纯f * x = fmap f x（自由定理） Alt u * （Alt（Pure y））= Alt（fmap（$ y）u） - u *纯y =纯（$ y）* u Alt f @（Lift _）*< *> Alt x @ Empty = Alt（Ap f x） Alt f @（Lift _）* Alt x @（Lift _）= Alt（Ap f x） Alt f @（Lift _）* Alt x @（Plus _ _）= Alt（Ap f x） Alt f @（Lift _）* Alt x @（Ap _ _）= Alt（Ap f x） Alt f @（Plus _ _）* Alt x @ Empty = Alt（Ap f x） Alt f @（Plus _ _）* Alt x @（Lift _）= Alt（Ap f x） Alt f @（Plus _ _）* Alt x @（Plus _ _）= Alt（Ap f x） Alt f @（Plus _ _）* Alt x @（Ap _ _）= Alt（Ap f x） Alt f @（Ap _）* Alt x @ Empty = Alt（Ap f x） Alt f @（Ap _ _）* Alt x @（Lift _）= Alt（Ap f x） Alt f @（Ap __）* Alt x @（Plus _ _）= Alt（Ap f x） Alt f @（Ap _ _）*所有这些 Ap s可以被一对视图模式所覆盖，但它并不会让它变得更简单。 这也是一个替代。为此，我们将使用视图模式将案例分为空的和非空的案例，并使用额外的类型来存储非空的证明。 { - ＃Language ViewPatterns＃ - } import Control.Applicative data AltEmpty ::（* - > *） - > * - > *其中 Empty_ :: Alt'真假假f a - > AltEmpty f a NonEmpty_ :: AltNE f a - > AltEmpty f a 数据AltNE ::（* - > *） - > * - > *其中 AltNE :: Alt'假纯加f a - > AltNE f a empty_ :: Alt'e1 p1 p2 f a - > AltEmpty fa empty_ x @ Empty = Empty_ x empty_ x @（Pure _）= NonEmpty_（AltNE x） empty_ x @（Lift _）= NonEmpty_（AltNE x） empty_ x @（Plus _ _）= NonEmpty_（AltNE x） empty_ x @（Ap _ _）= NonEmpty_（AltNE x） 实例Functor f =>替代方案（Alt f）其中 empty = Alt空 Alt空< |> x = x - 空< |> x = x x< |> Alt Empty = x - x< |> empty = x Alt（empty_ - > NonEmpty_ a）< |> Alt（empty_ - > NonEmpty_ b）= case a<> b的AltNE c - > Alt c 其中（<>）:: AltNE f a - > AltNE f a - > AltNE f a AltNE（Plus x y）<> AltNE z = AltNE x<> （AltNE y AltNE z） - （x< |> y）< |> x = x< |> （y<> z） AltNE a @（Pure _）<> AltNE b = AltNE（Plus a b） AltNE a @（Lift _）<> AltNE b = AltNE（Plus a b） AltNE a @（Ap __）<> AltNE b = AltNE（Plus ab） liftAlt 和 runAlt { - ＃Language RankNTypes＃ - } { - ＃Language ScopedTypeVariables＃ - } liftAlt :: fa - > Alt f a liftAlt = Alt。提升 runAlt':: forall f g x空纯加a。可选的g => （全部x，f x - > g x） - > Alt'空纯加f a - > g a runAlt'u = go where go :: forall empty pure plus a。 Alt'空纯加f a - > g a 去空=空去（纯a）=纯a 去（提升a）= u a 去（加x x）=去x< |>去y 去（Ap f x）=去f * go x runAlt :: Alternative g => （全部x，f x - > g x） - > Alt f a - > ga runAlt u（Alt x）= runAlt'ux 这个新的 Alt f 不提供免费的左派或右派，因此 runAlt id :: Alt fa - > ga 保留了 g 的分配方式。 列表仍然是分布式的，但 FlipAp 列表不是。 map（runAlt id）ldExample1： ：示例[Int] map（runAlt id）ldExample1 ::示例（FlipAp [] Int） [[3,4,20,30]，[3,4,20， 30]] [FlipAp {unFlipAp = [3,20,4,30]}，FlipAp {unFlipAp = [3,4,20,30]}] List不是正确的分配，但 FlipAp 列表仍然是 map（runAlt id）rdExample1 ::示例[Int] map（runAlt id）rdExample1 ::示例（FlipAp [] Int） [[3,4,20,30]，[3,20,4,30]] [FlipAp {unFlipAp = [3,20,4,30]}，FlipAp {unFlipAp = [3,20,4,30]}] 本节的源代码 结构上有效的left-catch free 替代 继续rol我们需要的法则我们可以将它们添加到我们之前制作的结构上自由的选择中。 要添加左捕捉，我们将修改结构，使其不能表示它。留下的是 （纯a）< /> x =纯a $ c> Alt'代表它，我们会从 Plus 纯 c $ c $> - 空纯加数据Alt':: Bool - >布尔 - >布尔 - > （* - > *） - > * - > * where Empty :: Alt'True False f a Pure :: a - > Alt'False True False f a Lift :: f a - > Alt'False False False f a Plus :: Alt'False False False f a - > Alt'False pure2 plus2 f a - > Alt'False False True f a - Empty不能位于Plus - empty< |>的左侧或右侧。 x = x - x< |> empty = x - Plus不能在Plus - （x< |> y）< |>的左边。 z = x< |> （y< |> z） - Pure不能在Plus - （纯粹的a）< |>的左边。 x =纯a ... 这会导致编译器错误在执行 Alternative Alt 无法匹配类型'' True'with'False'预期类型：Alt''False'False'False f a1 实际类型：Alt''假'pure2 plus2 f a1 'Plus'的第一个参数'，即'a'在'AltNE'的第一个参数中，即'（Plus ab） 我们可以通过吸引我们的新法律来解决这个问题，（纯粹的a）< |> x =纯a 实例Functor f =>替代方案（Alt f）其中 empty = Alt空 Alt空< |> x = x - 空< |> x = x x< |> Alt Empty = x - x< |> empty = x Alt（empty_ - > NonEmpty_ a）< |> Alt（empty_ - > NonEmpty_ b）= case a<> b的AltNE c - > Alt c 其中（<>）:: AltNE f a - > AltNE f a - > AltNE a（纯_）<> _ = AltNE a - （纯a）< |> x =纯a AltNE（Plus x y）<> AltNE z = AltNE x<> （AltNE y AltNE z） - （x< |> y）< |> x = x< |> （y< |> z） AltNE a @（Lift _）<> AltNE b = AltNE（Plus a b） AltNE a @（Ap __）<> AltNE b = AltNE（Plus a b） There is a nice Free Alternative in the great free package, which lifts a Functor to a left-distributive Alternative.That is, the claim is that:runAlt :: Alternative g => (forall x. f x -> g x) -> Alt f a -> g ais an Alternative homomorphism, with liftAlt. And, indeed, it is one, but only for left-distributive Alternative instances.Of course, in reality, very few Alternative instances are actually left-distributive. Most of the alternative instances that actually matter (parsers, MaybeT f for most Monad f, etc.) are not left-distributive. This fact can be shown by an example where runAlt and liftAlt do not form an Alternative homomorphism:(writeIORef x False <|> writeIORef True) *> (guard =<< readIORef x)-- is an IO action that throws an exceptionrunAlt id $ (liftAlt (writeIORef x False) <|> liftAlt (writeIORef True)) *> liftAlt (guard =<< readIORef x)-- is an IO action that throws no exception and returns successfully ()So runAlt is only an Alternative homomorphism for some Alternatives, but not all. This is because the structure of Alt normalizes all actions to distribute over the left.Alt is great because, structurally, Alt f is a lawful Applicative and Alternative. There isn't any possible way to construct a value of type Alt f a using the Applicative and Alternative functions that don't follow the laws...the structure of the type itself is what makes it a free Alternative.Just like, for lists, you can't construct a list using <> and mempty that doesn't respect x <> mempty = x, mempty <> x = x, and associativity.I've written a Free alternative that doesn't enforce the Applicative and Alternative laws, structurally, but does yield a valid Alternative and Applicative homomorphism with runAlt/liftAlt:data Alt :: (* -> *) -> * -> * where Pure :: a -> Alt f a Lift :: f a -> Alt f a Empty :: Alt f a Ap :: Alt f (a -> b) -> Alt f a -> Alt f b Plus :: Alt f as -> Alt f as -> Alt f asinstance Functor f => Functor (Alt f) where fmap f = \case Pure x -> Pure (f x) Lift x -> Lift (f <$> x) Empty -> Empty Ap fs xs -> Ap ((f .) <$> fs) xs Plus xs ys -> Plus (f <$> xs) (f <$> ys)instance Functor f => Applicative (Alt f) where pure = Pure (<*>) = Apinstance Functor f => Alternative (Alt f) where empty = Empty (<|>) = Plusstructurally, Alt f is not an actual Applicative, because:pure f <*> pure x = Ap (Pure f) (Pure x)pure (f x) = Pure (f x)So pure f <*> pure x is not the same as pure (f x), structurally. Not a valid Applicative, right off the bat.But, with the given runAlt and liftAlt:liftAlt :: f a -> Alt f aliftAlt = LiftrunAlt :: Alternative g => (forall x. f x -> g x) -> Alt f a -> g arunAlt f = \case Pure x -> pure x Lift x -> f x Empty -> empty Ap fs xs -> runAlt f fs <*> runAlt f xs Plus xs ys -> runAlt f xs <|> runAlt f ysAnd runAlt here does indeed act as a valid Applicative homomorphism with a given natural transformation...One could say that my new Alt f is a valid Alternative and Applicative when quotiented by the equivalence relationship defined by runAlt, i suppose.Anyway, this is only slightly unsatisfying. Is there any way to write a free Alternative that is structurally a valid Alternative and Applicative, without enforcing left distributivity?(In particular, I'm actually interested in one that follows the left catch law, and enforces it structurally. This would be a separate and also interesting thing, but not completely necessary.)And, if there isn't any way, why not? 解决方案 Control.Alternative.Free's Alt f produces a left-distributive Alternative for free, even if f isn't Alternative or f is a non-left-distributive Alternative. We can say that, in addition to the well-agreed upon alternative lawsempty <|> x = xx <|> empty = x(x <|> y) <|> z = x <|> (y <|> z)empty <*> f = emptyAlt f also gives left-distribution for free.(a <|> b) <*> c = (a <*> c) <|> (b <*> c)Because Alt f is always left distributive (and runAlt . liftAlt = id) liftAlt can never be a homomorphism for non-left-distributive Alternatives. If an Alternative f is not left-distributive, then there exist a, b, and c such that(a <|> b) <*> c != (a <*> c) <|> (b <*> c)If liftAlt : f -> Alt f were a homomorphism then (a <|> b) <*> c != (a <*> c) <|> (b <*> c) -- f is not left-distributiveid ((a <|> b) <*> c) != id ((a <*> c) <|> (b <*> c))runAlt . liftAlt ((a <|> b) <*> c) != runAlt . liftAlt ((a <*> c) <|> (b <*> c)) -- runAlt . liftAlt = idrunAlt ((liftAlt a <|> liftAlt b) <*> liftAlt c) != runAlt ((liftAlt a <*> liftAlt c) <|> (liftAlt b <*> liftAlt c)) -- homomorphismrunAlt ((liftAlt a <|> liftAlt b) <*> liftAlt c) != runAlt ((liftAlt a <|> liftAlt b) <*> liftAlt c) -- by left-distribution of `Alt`, this is a contradictionTo demonstrate this we need an Alternative that isn't left-distributive. Here's one, FlipAp [].newtype FlipAp f a = FlipAp {unFlipAp :: f a} deriving Showinstance Functor f => Functor (FlipAp f) where fmap f (FlipAp x) = FlipAp (fmap f x)instance Applicative f => Applicative (FlipAp f) where pure = FlipAp . pure (FlipAp f) <*> (FlipAp xs) = FlipAp ((flip ($) <$> xs) <*> f)instance Alternative f => Alternative (FlipAp f) where empty = FlipAp empty (FlipAp a) <|> (FlipAp b) = FlipAp (a <|> b)Along with some laws for left distribution and right distribution, and some examplesleftDist :: Alternative f => f (x -> y) -> f (x -> y) -> f x -> Example (f y)leftDist a b c = [(a <|> b) <*> c, (a <*> c) <|> (b <*> c)]rightDist :: Alternative f => f (x -> y) -> f x -> f x -> Example (f y)rightDist a b c = [a <*> (b <|> c), (a <*> b) <|> (a <*> c)]type Example a = [a]ldExample1 :: Alternative f => Example (f Int)ldExample1 = leftDist (pure (+1)) (pure (*10)) (pure 2 <|> pure 3)rdExample1 :: Alternative f => Example (f Int)rdExample1 = rightDist (pure (+1) <|> pure (*10)) (pure 2) (pure 3)We can demonstrate a few properties of lists, FlipAp lists, and runAlt.Lists are left-distributive, but FlipAp lists aren'tldExample1 :: Example [Int]ldExample1 :: Example (FlipAp [] Int)[[3,4,20,30],[3,4,20,30]][FlipAp {unFlipAp = [3,20,4,30]},FlipAp {unFlipAp = [3,4,20,30]}]Lists aren't right-distributive, but FlipAp lists arerdExample1 :: Example [Int]rdExample1 :: Example (FlipAp [] Int)[[3,4,20,30],[3,20,4,30]][FlipAp {unFlipAp = [3,20,4,30]},FlipAp {unFlipAp = [3,20,4,30]}]Alt is always left-distributivemap (runAlt id) ldExample1 :: Example [Int]map (runAlt id) ldExample1 :: Example (FlipAp [] Int)[[3,4,20,30],[3,4,20,30]][FlipAp {unFlipAp = [3,4,20,30]},FlipAp {unFlipAp = [3,4,20,30]}]Alt is never right-distributivemap (runAlt id) rdExample1 :: Example [Int]map (runAlt id) rdExample1 :: Example (FlipAp [] Int)[[3,4,20,30],[3,20,4,30]][FlipAp {unFlipAp = [3,4,20,30]},FlipAp {unFlipAp = [3,20,4,30]}]We can defile a right-distributive free alternative in terms of FlipAp and Alt.runFlipAlt :: forall f g a. Alternative g => (forall x. f x -> g x) -> FlipAp (Alt f) a -> g arunFlipAlt nt = runAlt nt . unFlipApFlipAp Alt is never left-distributive.map (runFlipAlt id) ldExample1 :: Example [Int]map (runFlipAlt id) ldExample1 :: Example (FlipAp [] Int)[[3,20,4,30],[3,4,20,30]][FlipAp {unFlipAp = [3,20,4,30]},FlipAp {unFlipAp = [3,4,20,30]}]FlipAp Alt is always right-distributivemap (runFlipAlt id) rdExample1 :: Example [Int]map (runFlipAlt id) rdExample1 :: Example (FlipAp [] Int)[[3,20,4,30],[3,20,4,30]][FlipAp {unFlipAp = [3,20,4,30]},FlipAp {unFlipAp = [3,20,4,30]}]Up until now I haven't told you anything that you didn't already imply by saying that liftAlt : f -> Alt f is an Alternative homomorphism, but only for left-distributive Alternative instances. But I have shown you a free-alternative that isn't left-distributive (it's trivially right-distributive instead).A structurally valid free AlternativeThis section answers the bulk of your question, is there a structurally valid free Alternative that isn't left-distributive? Yes.This isn't an efficient implementation; it's purpose is to demonstrate that it exists and that some version of it can be arrived at in a straight-forward manner.To make a structurally valid free Alternative I am doing two things. The first is to create a data structure that can't represent any of the Alternative laws; if it can't represent the law then a structure can't be constructed independently of the type class to violate it. This is the same trick used to make lists structurally obey the Alternative associativity law; there's no list that can represent the left-associated (x <|> y) <|> z. The second part is to make sure the operations obey the laws. A list can't represent the left association law, but an implementation of <|> could still violate it, like x <|> y = x ++ reverse y.The following structure can't be constructed to represent any of the Alternative laws.{-# Language GADTs #-}{-# Language DataKinds #-}{-# Language KindSignatures #-}data Alt :: (* -> *) -> * -> * where Alt :: Alt' empty pure plus f a -> Alt f a-- empty pure plusdata Alt' :: Bool -> Bool -> Bool -> (* -> *) -> * -> * where Empty :: Alt' True False False f a Pure :: a -> Alt' False True False f a Lift :: f a -> Alt' False False False f a Plus :: Alt' False pure1 False f a -> Alt' False pure2 plus2 f a -> Alt' False False True f a -- Empty can't be to the left or right of Plus -- empty <|> x = x -- x <|> empty = x -- Plus can't be to the left of Plus -- (x <|> y) <|> z = x <|> (y <|> z) Ap :: Alt' False False plus1 f (a -> b) -> Alt' empty False plus2 f a -> Alt' False False False f b -- Empty can't be to the left of `Ap` -- empty <*> f = empty -- Pure can't be to the left or right of `Ap` -- pure id <*> v = v -- pure (.) <*> u <*> v <*> w = u <*> (v <*> w) -- pure f <*> pure x = pure (f x) -- u <*> pure y = pure ($ y) <*> uIt's a Functorinstance Functor f => Functor (Alt' empty pure plus f) where fmap _ Empty = Empty fmap f (Pure a) = Pure (f a) fmap f (Plus a as) = Plus (fmap f a) (fmap f as) fmap f (Lift a) = Lift (fmap f a) fmap f (Ap g a) = Ap (fmap (f .) g) ainstance Functor f => Functor (Alt f) where fmap f (Alt a) = Alt (fmap f a)And it's Applicative. Because the structure can't represent the laws, when we encounter a term containing one of the unpreventable expressions we're forced to convert it into something else. The laws tell us what to do.instance Functor f => Applicative (Alt f) where pure a = Alt (Pure a) Alt Empty <*> _ = Alt Empty -- empty <*> f = empty Alt (Pure f) <*> (Alt x) = Alt (fmap f x) -- pure f <*> x = fmap f x (free theorem) Alt u <*> (Alt (Pure y)) = Alt (fmap ($ y) u) -- u <*> pure y = pure ($ y) <*> u Alt f@(Lift _) <*> Alt x@Empty = Alt (Ap f x) Alt f@(Lift _) <*> Alt x@(Lift _) = Alt (Ap f x) Alt f@(Lift _) <*> Alt x@(Plus _ _) = Alt (Ap f x) Alt f@(Lift _) <*> Alt x@(Ap _ _) = Alt (Ap f x) Alt f@(Plus _ _) <*> Alt x@Empty = Alt (Ap f x) Alt f@(Plus _ _) <*> Alt x@(Lift _) = Alt (Ap f x) Alt f@(Plus _ _) <*> Alt x@(Plus _ _) = Alt (Ap f x) Alt f@(Plus _ _) <*> Alt x@(Ap _ _) = Alt (Ap f x) Alt f@(Ap _ _) <*> Alt x@Empty = Alt (Ap f x) Alt f@(Ap _ _) <*> Alt x@(Lift _) = Alt (Ap f x) Alt f@(Ap _ _) <*> Alt x@(Plus _ _) = Alt (Ap f x) Alt f@(Ap _ _) <*> Alt x@(Ap _ _) = Alt (Ap f x)All of those Aps could be covered by a pair of view patterns, but it doesn't make it any simpler.It's also an Alternative. For this we'll use a view pattern to divide the cases into the empty and non-empty cases, and an extra type to store the proof that they're non-empty{-# Language ViewPatterns #-}import Control.Applicativedata AltEmpty :: (* -> *) -> * -> * where Empty_ :: Alt' True False False f a -> AltEmpty f a NonEmpty_ :: AltNE f a -> AltEmpty f adata AltNE :: (* -> *) -> * -> * where AltNE :: Alt' False pure plus f a -> AltNE f aempty_ :: Alt' e1 p1 p2 f a -> AltEmpty f aempty_ x@Empty = Empty_ xempty_ x@(Pure _) = NonEmpty_ (AltNE x)empty_ x@(Lift _) = NonEmpty_ (AltNE x)empty_ x@(Plus _ _) = NonEmpty_ (AltNE x)empty_ x@(Ap _ _) = NonEmpty_ (AltNE x)instance Functor f => Alternative (Alt f) where empty = Alt Empty Alt Empty <|> x = x -- empty <|> x = x x <|> Alt Empty = x -- x <|> empty = x Alt (empty_ -> NonEmpty_ a) <|> Alt (empty_ -> NonEmpty_ b) = case a <> b of AltNE c -> Alt c where (<>) :: AltNE f a -> AltNE f a -> AltNE f a AltNE (Plus x y) <> AltNE z = AltNE x <> (AltNE y <> AltNE z) -- (x <|> y) <|> x = x <|> (y <|> z) AltNE a@(Pure _) <> AltNE b = AltNE (Plus a b) AltNE a@(Lift _) <> AltNE b = AltNE (Plus a b) AltNE a@(Ap _ _) <> AltNE b = AltNE (Plus a b)liftAlt and runAlt{-# Language RankNTypes #-}{-# Language ScopedTypeVariables #-}liftAlt :: f a -> Alt f aliftAlt = Alt . LiftrunAlt' :: forall f g x empty pure plus a. Alternative g => (forall x. f x -> g x) -> Alt' empty pure plus f a -> g arunAlt' u = go where go :: forall empty pure plus a. Alt' empty pure plus f a -> g a go Empty = empty go (Pure a) = pure a go (Lift a) = u a go (Plus x y) = go x <|> go y go (Ap f x) = go f <*> go xrunAlt :: Alternative g => (forall x. f x -> g x) -> Alt f a -> g arunAlt u (Alt x) = runAlt' u xThis new Alt f doesn't provide either left-distribution or right-distribution for free, and therefore runAlt id :: Alt f a -> g a preserves how distributive g is.Lists are still left-distributive, but FlipAp lists aren't.map (runAlt id) ldExample1 :: Example [Int]map (runAlt id) ldExample1 :: Example (FlipAp [] Int)[[3,4,20,30],[3,4,20,30]][FlipAp {unFlipAp = [3,20,4,30]},FlipAp {unFlipAp = [3,4,20,30]}]List's aren't right-distributive, but FlipAp lists still aremap (runAlt id) rdExample1 :: Example [Int]map (runAlt id) rdExample1 :: Example (FlipAp [] Int)[[3,4,20,30],[3,20,4,30]][FlipAp {unFlipAp = [3,20,4,30]},FlipAp {unFlipAp = [3,20,4,30]}]Source code for this sectionStructurally valid left-catch free AlternativeTo control which laws we want we can add them to the structurally free alternative we made earlier.To add left-catch we'll modify the structure so it can't represent it. Left catch is(pure a) <|> x = pure aTo keep Alt' from representing it we'll exclude pure from what's allowed to the left of Plus.-- empty pure plusdata Alt' :: Bool -> Bool -> Bool -> (* -> *) -> * -> * where Empty :: Alt' True False False f a Pure :: a -> Alt' False True False f a Lift :: f a -> Alt' False False False f a Plus :: Alt' False False False f a -> Alt' False pure2 plus2 f a -> Alt' False False True f a -- Empty can't be to the left or right of Plus -- empty <|> x = x -- x <|> empty = x -- Plus can't be to the left of Plus -- (x <|> y) <|> z = x <|> (y <|> z) -- Pure can't be to the left of Plus -- (pure a) <|> x = pure a ...This results in a compiler error in the implementation of Alternative AltCouldn't match type ‘'True’ with ‘'False’Expected type: Alt' 'False 'False 'False f a1 Actual type: Alt' 'False pure2 plus2 f a1In the first argument of ‘Plus’, namely ‘a’In the first argument of ‘AltNE’, namely ‘(Plus a b)Which we can fix by appealing to our new law, (pure a) <|> x = pure ainstance Functor f => Alternative (Alt f) where empty = Alt Empty Alt Empty <|> x = x -- empty <|> x = x x <|> Alt Empty = x -- x <|> empty = x Alt (empty_ -> NonEmpty_ a) <|> Alt (empty_ -> NonEmpty_ b) = case a <> b of AltNE c -> Alt c where (<>) :: AltNE f a -> AltNE f a -> AltNE f a AltNE a@(Pure _) <> _ = AltNE a -- (pure a) <|> x = pure a AltNE (Plus x y) <> AltNE z = AltNE x <> (AltNE y <> AltNE z) -- (x <|> y) <|> x = x <|> (y <|> z) AltNE a@(Lift _) <> AltNE b = AltNE (Plus a b) AltNE a@(Ap _ _) <> AltNE b = AltNE (Plus a b) 这篇关于结构强制的自由选择，没有左派分配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！