State是Arrow吗？其ArrowLoop实例正确性存疑求验证

首先需要明确一个根本性的错误：State s 是一元类型构造器（State s a 接收状态类型 s 和结果类型 a），但 Category 和 Arrow 类要求实例是二元类型构造器（即形如 arr a b，表示从输入类型 a 到输出类型 b 的箭头）。你的代码直接将 State s 作为 Category 和 Arrow 的实例，这是类型参数的误用，从根源上不符合类型类的要求。

下面结合你的代码逐一分析：

原代码中的类型混淆 #

你写的 instance Category State 中，Category 要求的 cat 是二元构造器（比如 (->)），但 State 是一元的，这会导致类型不匹配。例如 Category 的 id 应该是 cat a a，对应到你的代码里是 State a a（状态类型和结果类型都是 a），这显然不是通用范畴的态射定义——你错误地把状态类型当作了箭头的输入类型，结果类型当作了箭头的输出类型，而非让箭头支持任意输入输出类型。

各实例的具体问题 #

1. Category 实例 #

你的实现逻辑是：输入状态 x，先执行 g 得到中间结果 y 和新状态 x2，再用 y 作为状态输入执行 f，最后返回 f 的输出和 g 产生的状态。这本质上不是范畴的组合（范畴组合是态射的复合，即输入类型到输出类型的映射），而是把状态的流转错误地当作了态射的复合，不符合 Category 的语义。

2. Arrow 实例 #

arr f 的实现是将函数 f 作用在状态上并返回结果，但 Arrow 中的 arr 应该是将任意纯函数 a -> b 提升为箭头 arr a b，而非只能作用在状态类型上。你的实现限制了输入必须是状态类型，违背了 Arrow 的通用性要求。

3. ArrowChoice 实例 #

同样存在输入类型被固定为状态分支的问题，+++ 操作应该支持任意左右分支类型的箭头组合，而非只能处理状态类型的分支。

4. ArrowApply 实例 #

你的实现中，输入是 (State f, s)（箭头加状态），执行后返回结果并保留原输入作为新状态。但由于类型构造器的错误，这个实现仅能处理特定类型的输入，不符合 ArrowApply 对任意箭头和输入的要求。

5. ArrowLoop 实例 #

除了上述类型问题外，你的 loop 实现还有递归逻辑的错误：

((x, d), (s2, _)) = f (s, d)

这里的 d 是递归引用的循环变量，但你丢弃了 f 返回的状态对中的第二个元素，同时状态的更新完全不依赖循环变量，这既不符合 ArrowLoop 的定律（比如循环融合、交换律），也无法正确实现循环语义——正确的 ArrowLoop 需要让循环变量参与状态的流转，而非孤立存在。

正确的实现方向 #

要让状态计算成为 Arrow，需要定义二元类型构造器，比如：

import Control.Arrow
import Control.Category
import Control.Monad.State

-- 二元构造器：StateArrow s a b 表示输入a、输出b、状态s的箭头
newtype StateArrow s a b = StateArrow { runStateArrow :: a -> State s b }

-- 等价于：runStateArrow :: a -> s -> (b, s)

instance Category (StateArrow s) where
    id = StateArrow return
    StateArrow f . StateArrow g = StateArrow $ \a -> g a >>= f

instance Arrow (StateArrow s) where
    arr f = StateArrow $ \a -> return (f a)
    StateArrow f *** StateArrow g = StateArrow $ \(a, b) ->
        (,) <$> f a <*> g b

instance ArrowChoice (StateArrow s) where
    StateArrow f +++ StateArrow g = StateArrow $ \case
        Left a -> Left <$> f a
        Right b -> Right <$> g b

instance ArrowApply (StateArrow s) where
    app = StateArrow $ \(StateArrow f, a) -> f a

instance ArrowLoop (StateArrow s) where
    loop (StateArrow f) = StateArrow $ \a -> do
        let recLoop d = f (a, d) >>= \(c, d') -> return (c, d')
        (c, _) <- recLoop undefined  -- 利用惰性求值实现循环
        return c

这个实现中，StateArrow s 是合法的二元类型构造器，完全符合 Category 和 Arrow 系列类的语义，所有实例都满足对应的定律。

内容的提问来源于stack exchange，提问作者Dannyu NDos