有没有不能守法Apply的Functor?
Is there a Functor that cannot be a law-abiding Apply?
A recent question asked generally about boundaries between various Haskell classes. I came up with Handler
as an example of a valid Functor
with no sensible instance of Apply
**,其中
class Functor f => Apply f where
(<.>) :: f (a -> b) -> f a -> f b
-- optional bits omitted.
但是,我还没有找到一个有效 Functor
的例子,它不能成为 有效 (如果毫无意义)实例 Apply
。事实上 Apply
有 有(见更新)但是一个单一的法律,
(.) <$> u <.> v <.> w = u <.> (v <.> w)
这似乎变得相当棘手。
pigworker (Conor McBride) 以前 gave an example 的 Functor
不是 Applicative
,但他依靠 pure
这样做,而这在Apply
.
** 后来我意识到 Handler
实际上可能有一个合理的(虽然有点奇怪)Apply
实例,它在概念上收集同时发生的异常。
更新
Edward Kmett 现在 accepted 我为 Apply
提出的另外两个定律(以验证我对 Apply (Coyoneda f)
实例所做的优化):
x <.> (f <$> y) = (. f) <$> x <.> y
f <$> (x <.> y) = (f .) <$> x <.> y
看看这些添加是否会改变这个问题的答案会很有趣。
两个函子的"sum"(来自transformers
的Data.Functor.Sum
)似乎就是一个例子。
可以很容易地映射到一个分支或另一个分支,但是当函子中的函数和函子中的参数位于不同的分支时如何实现<.>
?
ghci> import Data.Functor.Sum
ghci> import Data.Functor.Identity
ghci> let f = InL (Const ()) :: Sum (Const ()) Identity (Int -> Int)
ghci> let x = InR (Identity 5) :: Sum (Const ()) Identity Int
ghci$ f <.> x = ..... ?
这不是您要找的东西,但它很接近所以我想我会分享它。标准 Writer
monad 对其 Apply
实例有一个额外的约束(即 w
类型是 Monoid
或 Semigroup
的实例),即 Functor
实例不存在,因此如果 Foo
不是 Semigroup
/Monoid
,则 Writer Foo
是 Functor
而不是 Apply
:
data Writer w a = Writer w a
instance Monoid w => Apply (Writer w) where
Writer w1 f <.> Writer w2 x = Writer (mappend w1 w2) (f x)
但是,这并不是您所要求的真正示例,因为实际上可以在没有 Monoid
约束的情况下创建 Apply
的守法实例:
instance Apply (Writer w) where
Writer w1 f <.> Writer w2 x = Writer w1 (f x)
这个实例的问题是它不允许匹配 Applicative
实例,因为没有办法实现 pure
这样你就可以得到左标识,即:
pure id <.> x /= x
这只是为您提供与 Conor 相同的答案的长篇大论:依赖 pure
破坏实例的演示。
是的,有 Functor
个没有 Apply
个实例。考虑两个函数的总和(exponents in algebraic data types):
data EitherExp i j a
= ToTheI (i -> a)
| ToTheJ (j -> a)
所有 i
和 j
都有一个 Functor
实例:
instance Functor (EitherExp i j) where
fmap f (ToTheI g) = ToTheI (f . g)
fmap f (ToTheJ g) = ToTheJ (f . g)
但是所有 i
和 j
都没有 Apply
实例
instance Apply (EitherExp i j) where
...
ToTheI f <.> ToTheJ x = ____
当您只有 f :: i -> a -> b
和 x :: j -> a
时,无法用 i -> b
或 j -> b
填充空白 ____
。为此,我们必须对 i
和 j
有所了解,但无法深入了解 Haskell 中的每个类型 i
或 j
。直觉拒绝这个答案;如果你知道 任何 关于 i
或 j
,就像它们被一个单一的值所占据,那么你可以为 [写一个 Apply
实例=43=]
class Inhabited a where
something :: a
instance (Inhabited i, Inhabited j) => Apply (EitherExp i j) where
...
ToTheI f <.> ToTheJ x = ToTheI (const ((f something) (x something)))
但我们不知道每个 i
和每个 j
都是 Inhabited
。 Void
类型不存在任何东西。我们甚至没有办法知道每种类型是 Inhabited
还是 Void
。
我们的直觉其实很好;当我们可以检查类型的构造方式时,对于代数数据类型,没有 Functor
没有 Apply
实例。以下是两个可能更符合我们直觉的答案。
没有...
... 对于代数数据类型。有3种可能性。结构为空,结构可以为空,或者结构不能为空。如果结构是空的,那么它就是 absurd
一个 Apply
。如果它可以为空,则选择任何空实例并 return 它不断地用于任何应用。如果它不能为空则它是每个都不能为空的结构的总和,可以通过从第一个到来自第二个的值之一,然后 return 将其放入某个常量结构中。
适用法律非常宽松。 Apply 不需要有任何意义。它不需要是 "zip-y"。当与 Applicative
中的 pure
这样可疑的东西结合时,它不需要是 fmap
;没有 pure
的概念来编写要求它有意义的法律。
当结构可以为空时
选择任何空实例并return它不断地应用
u <.> v = empty
证明
(.) <$> u <.> v <.> w = u <.> (v <.> w)
(((.) <$> u) <.> v) <.> w = u <.> (v <.> w) -- by infixl4 <$>, infixl4 <.>
(_ ) <.> w = u <.> (_ ) -- by substitution
empty = empty -- by definition of <.>
当结构不能为空时
如果结构f
不能为空,则存在函数extract :: forall a. f a -> a
。选择另一个函数 c :: forall a. a -> f a
,它始终构造相同的非空结构,并在各处填充参数并定义:
u <.> v = c (extract u $ extract v)
有了自由定理
extract (f <$> u) = f (extract u)
extract . c = id
证明
(.) <$> u <.> v <.> w = u <.> (v <.> w)
(((.) <$> u) <.> v) <.> w = u <.> (v <.> w) -- by infixl4 <$>, infixl4 <.>
(c (extract ((.) <$> u) $ extract v)) <.> w = u <.> (v <.> w) -- by definition
(c ((.) (extract u) $ extract v)) <.> w = u <.> (v <.> w) -- by free theorem
c (extract (c ((.) (extract u) $ extract v)) $ extract w) = u <.> (v <.> w) -- by definition
c ( ((.) (extract u) $ extract v) $ extract w) = u <.> (v <.> w) -- by extract . c = id
c (((.) (extract u) $ extract v) $ extract w) = u <.> c (extract v $ extract w) -- by definition
c (((.) (extract u) $ extract v) $ extract w) = c (extract u $ extract (c (extract v $ extract w))) -- by definition
c (((.) (extract u) $ extract v) $ extract w) = c (extract u $ (extract v $ extract w) ) -- by extract . c = id
let u' = extract u
v' = extract v
w' = extract w
c (((.) u' $ v') $ w') = c (u' $ (v' $ w'))
c ((u' . v') $ w') = c (u' $ (v' $ w')) -- by definition of partial application of operators
c (u' $ (v' $ w')) = c (u' $ (v' $ w')) -- by definition of (.)
关于为指数类型、函数定义 extract
值得多说一点。对于函数 i -> a
有两种可能性。 i
要么有人居住,要么无人居住。如果有人居住,选择一些居民i
†并定义
extract f = f i
如果i
无人居住(它是空的)那么i -> a
是具有单一值absurd
的单位类型。 Void -> a
只是另一种精心设计的空类型,它不包含任何 a
;将其视为可以为空的结构。
当结构为空时
当结构为空时,就没有办法构造它。我们可以从每个可能的构造(有 none 传递给它)编写一个函数到任何其他类型。
absurd :: Void -> a
absurd x = case x of {}
空结构可以 Functor
与 fmap f = absurd
。以同样的方式,他们可以有一个 Apply
实例
(<.>) = absurd
我们可以简单地证明对于所有 u
、v
和 w
(.) <$> u <.> v <.> w = u <.> (v <.> w)
没有u
、v
或w
,声明为vacuously true。
†关于接受选择公理以选择指数类型 a
的一些注意事项 a -> b
是的...
... 对于 Haskell。想象一下,除了 IO
之外,还有另一个基数 Monad
,我们称它为 OI
。那么 Sum IO OI
是 Functor
但永远不可能是 Apply
.
...对于现实世界。如果您有一台可以向其发送函数(或 Hask 以外的类别中的箭头)的机器,但不能将两台机器组合在一起或提取它们的 运行 状态,那么它们是一个没有 Apply 的 Functor。
A recent question asked generally about boundaries between various Haskell classes. I came up with Handler
as an example of a valid Functor
with no sensible instance of Apply
**,其中
class Functor f => Apply f where
(<.>) :: f (a -> b) -> f a -> f b
-- optional bits omitted.
但是,我还没有找到一个有效 Functor
的例子,它不能成为 有效 (如果毫无意义)实例 Apply
。事实上 Apply
有 有(见更新)但是一个单一的法律,
(.) <$> u <.> v <.> w = u <.> (v <.> w)
这似乎变得相当棘手。
pigworker (Conor McBride) 以前 gave an example 的 Functor
不是 Applicative
,但他依靠 pure
这样做,而这在Apply
.
** 后来我意识到 Handler
实际上可能有一个合理的(虽然有点奇怪)Apply
实例,它在概念上收集同时发生的异常。
更新
Edward Kmett 现在 accepted 我为 Apply
提出的另外两个定律(以验证我对 Apply (Coyoneda f)
实例所做的优化):
x <.> (f <$> y) = (. f) <$> x <.> y
f <$> (x <.> y) = (f .) <$> x <.> y
看看这些添加是否会改变这个问题的答案会很有趣。
两个函子的"sum"(来自transformers
的Data.Functor.Sum
)似乎就是一个例子。
可以很容易地映射到一个分支或另一个分支,但是当函子中的函数和函子中的参数位于不同的分支时如何实现<.>
?
ghci> import Data.Functor.Sum
ghci> import Data.Functor.Identity
ghci> let f = InL (Const ()) :: Sum (Const ()) Identity (Int -> Int)
ghci> let x = InR (Identity 5) :: Sum (Const ()) Identity Int
ghci$ f <.> x = ..... ?
这不是您要找的东西,但它很接近所以我想我会分享它。标准 Writer
monad 对其 Apply
实例有一个额外的约束(即 w
类型是 Monoid
或 Semigroup
的实例),即 Functor
实例不存在,因此如果 Foo
不是 Semigroup
/Monoid
,则 Writer Foo
是 Functor
而不是 Apply
:
data Writer w a = Writer w a
instance Monoid w => Apply (Writer w) where
Writer w1 f <.> Writer w2 x = Writer (mappend w1 w2) (f x)
但是,这并不是您所要求的真正示例,因为实际上可以在没有 Monoid
约束的情况下创建 Apply
的守法实例:
instance Apply (Writer w) where
Writer w1 f <.> Writer w2 x = Writer w1 (f x)
这个实例的问题是它不允许匹配 Applicative
实例,因为没有办法实现 pure
这样你就可以得到左标识,即:
pure id <.> x /= x
这只是为您提供与 Conor 相同的答案的长篇大论:依赖 pure
破坏实例的演示。
是的,有 Functor
个没有 Apply
个实例。考虑两个函数的总和(exponents in algebraic data types):
data EitherExp i j a
= ToTheI (i -> a)
| ToTheJ (j -> a)
所有 i
和 j
都有一个 Functor
实例:
instance Functor (EitherExp i j) where
fmap f (ToTheI g) = ToTheI (f . g)
fmap f (ToTheJ g) = ToTheJ (f . g)
但是所有 i
和 j
都没有 Apply
实例
instance Apply (EitherExp i j) where
...
ToTheI f <.> ToTheJ x = ____
当您只有 f :: i -> a -> b
和 x :: j -> a
时,无法用 i -> b
或 j -> b
填充空白 ____
。为此,我们必须对 i
和 j
有所了解,但无法深入了解 Haskell 中的每个类型 i
或 j
。直觉拒绝这个答案;如果你知道 任何 关于 i
或 j
,就像它们被一个单一的值所占据,那么你可以为 [写一个 Apply
实例=43=]
class Inhabited a where
something :: a
instance (Inhabited i, Inhabited j) => Apply (EitherExp i j) where
...
ToTheI f <.> ToTheJ x = ToTheI (const ((f something) (x something)))
但我们不知道每个 i
和每个 j
都是 Inhabited
。 Void
类型不存在任何东西。我们甚至没有办法知道每种类型是 Inhabited
还是 Void
。
我们的直觉其实很好;当我们可以检查类型的构造方式时,对于代数数据类型,没有 Functor
没有 Apply
实例。以下是两个可能更符合我们直觉的答案。
没有...
... 对于代数数据类型。有3种可能性。结构为空,结构可以为空,或者结构不能为空。如果结构是空的,那么它就是 absurd
一个 Apply
。如果它可以为空,则选择任何空实例并 return 它不断地用于任何应用。如果它不能为空则它是每个都不能为空的结构的总和,可以通过从第一个到来自第二个的值之一,然后 return 将其放入某个常量结构中。
适用法律非常宽松。 Apply 不需要有任何意义。它不需要是 "zip-y"。当与 Applicative
中的 pure
这样可疑的东西结合时,它不需要是 fmap
;没有 pure
的概念来编写要求它有意义的法律。
当结构可以为空时
选择任何空实例并return它不断地应用
u <.> v = empty
证明
(.) <$> u <.> v <.> w = u <.> (v <.> w)
(((.) <$> u) <.> v) <.> w = u <.> (v <.> w) -- by infixl4 <$>, infixl4 <.>
(_ ) <.> w = u <.> (_ ) -- by substitution
empty = empty -- by definition of <.>
当结构不能为空时
如果结构f
不能为空,则存在函数extract :: forall a. f a -> a
。选择另一个函数 c :: forall a. a -> f a
,它始终构造相同的非空结构,并在各处填充参数并定义:
u <.> v = c (extract u $ extract v)
有了自由定理
extract (f <$> u) = f (extract u)
extract . c = id
证明
(.) <$> u <.> v <.> w = u <.> (v <.> w)
(((.) <$> u) <.> v) <.> w = u <.> (v <.> w) -- by infixl4 <$>, infixl4 <.>
(c (extract ((.) <$> u) $ extract v)) <.> w = u <.> (v <.> w) -- by definition
(c ((.) (extract u) $ extract v)) <.> w = u <.> (v <.> w) -- by free theorem
c (extract (c ((.) (extract u) $ extract v)) $ extract w) = u <.> (v <.> w) -- by definition
c ( ((.) (extract u) $ extract v) $ extract w) = u <.> (v <.> w) -- by extract . c = id
c (((.) (extract u) $ extract v) $ extract w) = u <.> c (extract v $ extract w) -- by definition
c (((.) (extract u) $ extract v) $ extract w) = c (extract u $ extract (c (extract v $ extract w))) -- by definition
c (((.) (extract u) $ extract v) $ extract w) = c (extract u $ (extract v $ extract w) ) -- by extract . c = id
let u' = extract u
v' = extract v
w' = extract w
c (((.) u' $ v') $ w') = c (u' $ (v' $ w'))
c ((u' . v') $ w') = c (u' $ (v' $ w')) -- by definition of partial application of operators
c (u' $ (v' $ w')) = c (u' $ (v' $ w')) -- by definition of (.)
关于为指数类型、函数定义 extract
值得多说一点。对于函数 i -> a
有两种可能性。 i
要么有人居住,要么无人居住。如果有人居住,选择一些居民i
†并定义
extract f = f i
如果i
无人居住(它是空的)那么i -> a
是具有单一值absurd
的单位类型。 Void -> a
只是另一种精心设计的空类型,它不包含任何 a
;将其视为可以为空的结构。
当结构为空时
当结构为空时,就没有办法构造它。我们可以从每个可能的构造(有 none 传递给它)编写一个函数到任何其他类型。
absurd :: Void -> a
absurd x = case x of {}
空结构可以 Functor
与 fmap f = absurd
。以同样的方式,他们可以有一个 Apply
实例
(<.>) = absurd
我们可以简单地证明对于所有 u
、v
和 w
(.) <$> u <.> v <.> w = u <.> (v <.> w)
没有u
、v
或w
,声明为vacuously true。
†关于接受选择公理以选择指数类型 a
的一些注意事项 a -> b
是的...
... 对于 Haskell。想象一下,除了 IO
之外,还有另一个基数 Monad
,我们称它为 OI
。那么 Sum IO OI
是 Functor
但永远不可能是 Apply
.
...对于现实世界。如果您有一台可以向其发送函数(或 Hask 以外的类别中的箭头)的机器,但不能将两台机器组合在一起或提取它们的 运行 状态,那么它们是一个没有 Apply 的 Functor。