language-ext 的 `Alternative<F>` 特质:失败传播、选择语义与 law 验证实战指南

原创2026-10-14 13:41:411,419 阅读
文章标签:后端

language-ext 的 Alternative<F> 特质:失败传播、选择语义与 law 验证实战指南

导读

Alternative<F> 是 language-ext 高阶类型特质体系中的一个关键抽象,它在 Applicative 的基础上补充了"失败传播"与"选择"能力,并提供了一个表示"空/单位"的 Empty 值。本文围绕 LanguageExt.Core/Traits/Alternative/README.md 展开,结合仓库源码深入讲解 Alternative 与 Choice、MonoidK、SemigroupK 的继承关系,澄清 Choose(| 运算符)与 Combine(+ 运算符)两种截然不同的语义,并演示如何利用 AlternativeLaw 以数学定律的形式验证自定义实现。读完本文,你将能够为自定义类型实现 Alternative 特质,并掌握 oneOf、option、many、sepBy 等组合子的用法与底层原理。

一、Alternative<F>:在 Applicative 之上叠加"失败与选择"

从类型声明看,Alternative<F> 是一个组合特质。其定义位于 Alternative.Trait.cs:

public interface Alternative<F> : Choice<F>, Applicative<F>
    where F : Alternative<F>
{
    /// <summary>
    /// Identity
    /// </summary>
    [Pure]
    public static abstract K<F, A> Empty<A>();

    // ... 其余默认组合子
}

这意味着,任何实现 Alternative<F> 的类型,同时必须是 Choice<F> 与 Applicative<F>。整个 trait 体系呈现出一条清晰的继承链:

Alternative<F> ─┬─ Choice<F> ─── SemigroupK<F>
                └─ Applicative<F> ─── Functor<F>

从源码可以进一步确认(见 Choice.Trait.cs 与 SemigroupK.cs):Choice<F> 本身继承 SemigroupK<F>,并定义了抽象的 Choose 方法;而 SemigroupK<F> 提供了抽象的 Combine 方法("半群的更高阶类型等价物",即对高阶类型而言的 semigroup)。README 明确说明:

Alternative is a Choice and MonoidK, which means it has a Choose method, a Combine method (which defaults to calling the Choose method), and an Empty method.

也就是说,Alternative 由三块能力拼合而成:

能力来源 成员 作用
Choice<F> Choose 二选一:前一个成功则取前一个,否则取后一个
SemigroupK<F> Combine 组合/拼接两个结构(默认实现为调用 Choose)
Alternative<F> 自身 Empty 提供单位值(identity),即"失败/空"状态

Empty 是一个静态抽象方法,要求每个实现类型针对任意值类型 A 都能构造出一个"空"结构,例如 Option<A>.None、Fin<A>.Fail(...)、空列表等。

二、核心语义:Choose 是 |,Combine 是 +

README 用一个非常直观的心智模型来区分 Alternative 中的两个二元运算:

  • Choose:失败/选择传播运算符 |——"第一个成功者胜出";
  • Combine:拼接/组合/加法运算符 +——"把两者结合起来"。

这种区分是有意为之的。Combine 从 SemigroupK 继承而来,语义外延较宽(可以表示拼接、合并、累积等);而 Alternative 通过让 Combine 默认调用 Choose,把 Choose 赋予"选择传播"这一精确含义,同时允许特定类型为 Choose 和 Combine 提供彼此独立的实现。这样既保持了语义的纯粹性,又为像 Validation 这类"失败累积"类型保留了在 Combine 中叠加错误的自由度。

README 同时给出了一个实现约定:

任何支持 Alternative 特质的类型都应该实现 | 运算符,以启用便捷的失败/选择传播;如果该类型对 Combine 有不同于默认的实现,则还应该实现 + 运算符。

language-ext 中确实提供了对应的运算符基础设施:在 SemigroupK.Operators.cs 中,+ 被定义为调用 Combine;而 | 运算符则由 Choice 的运算符扩展提供,直接映射到 Choose。

从 Fin 实现看语义差异

Fin 是一个很好的"语义分离"例子。在 Fin.TraitImpl.cs 中:

static K<Fin, A> Alternative<Fin>.Empty<A>() =>
    Fail<A>(Errors.None);

static K<Fin, A> Choice<Fin>.Choose<A>(K<Fin, A> ma, K<Fin, A> mb) =>
    ma switch
    {
        Fin<A>.Succ => ma,
        _           => mb
    };
  • Empty 被实现为 Fail<A>(Errors.None)——一个不带错误信息的失败值;
  • Choose 采用"短路选择":ma 成功(Succ)就直接返回 ma,否则返回 mb。

而 Fin 的 Combine(继承自 SemigroupK)则走的是累积路线:当两边都是 Fail 时,用 e1 + e2 把两个 Error 合并成一个(见同文件第 106–117 行)。这正是 README 所说的"Choose 与 Combine 可以有各自独立的实现"的典型体现——对 Fin 而言,| 是"失败就换一条路",+ 是"失败信息合并"。

从 Option 实现看 Choose 的短路特性

Option 同样实现了 Alternative<Option>(见 Option.TraitImpl.cs):

static K<Option, A> Alternative<Option>.Empty<A>() =>
    Option<A>.None;

static K<Option, A> Choice<Option>.Choose<A>(K<Option, A> ma, K<Option, A> mb) =>
    ma.As() switch
    {
        { IsSome: true } => ma,
        _                => mb
    };

Some(x) | 任何值 的结果恒为 Some(x);None | m 的结果为 m。注意 Choose 还提供了一个接受 Memo<F, A>(惰性记忆化参数)的重载,允许第二个备选延迟求值——这在构造递归组合子时至关重要。

三、Alternative<F> 内建的组合子家族

Alternative<F> 接口并非只有一个 Empty 抽象成员,它还在 Alternative.Trait.cs 中提供了一整套基于 Empty 与 Choose 的默认组合子,覆盖了典型的解析器组合子(parser combinator)场景。所有方法都以 K<F, A> 这一高阶类型为参数与返回值,因此可以作用于任何 Alternative 实例。

3.1 批量选择:Choice

Choice 从一组 applicative functor 中返回第一个成功者;如果全部失败,则返回最后一个:

public static virtual K<F, A> Choice<A>(in Seq<K<F, A>> ms)
{
    if(ms.IsEmpty) return F.Empty<A>();
    var r = ms[0];
    foreach (var m in ms.Tail)
    {
        r |= m;
    }
    return r;
}

注意两个细节:

  • 空集合直接返回 Empty<A>(),体现了 Empty 作为单位值/零元素的作用;
  • 非空集合用 |= 逐个折叠,即把 Choice 递归展开为一系列二元的 Choose。

Choice 还有一个 ReadOnlySpan<K<F, A>> 重载,避免在参数传递时产生额外分配。对应的 Prelude 便捷函数是 oneOf(见 Alternative.Prelude.cs),支持 params 数组与 Seq 两种形式:

public static K<F, A> oneOf<F, A>(params K<F, A>[] ms)
    where F : Alternative<F> =>
    Alternative.choice(ms);

同时,Alternative.Extensions.cs 还为 Seq<K<F, A>> 提供了扩展方法 OneOf,于是可以写出 seq1.OneOf() 这种流式风格。

3.2 重复执行:Some / Many

  • Some(fa):重复执行 fa 直到失败,收集所有结果,至少成功一次;
  • Many(fa):零次或多次,总是成功。

两者的实现相互递归,且借助 Memo(memoK)延迟递归调用:

public static virtual K<F, Seq<A>> Some<A>(K<F, A> fa)
{
    return some();

    K<F, Seq<A>> many() =>
        F.Choose(some(), F.Pure(Seq<A>()));

    K<F, Seq<A>> some() =>
        Cached<A>.cons * fa * memoK(many);
}

Some/Many 对应的 Prelude 函数为 some<F, A> 与 many<F, A>(同样定义在 Alternative.Module.cs 中)。文档注释里特别提醒:F 的 applicative 实现必须重写带 Func 惰性的 Apply 重载(ApplyLazy),否则 Some/Many 的递归组合很容易栈溢出。

3.3 分隔解析族:SepBy / EndBy

这套组合子源自解析器领域,用于处理"用分隔符隔开的元素序列":

组合子 语义
SepBy(fa, sep) 零个或多个 fa,由 sep 分隔
SepBy1(fa, sep) 一个或多个 fa,由 sep 分隔
SepByEnd(fa, sep) 零个或多个 fa,可由 sep 结尾
SepByEnd1(fa, sep) 一个或多个 fa,可由 sep 结尾
EndBy(p, sep) 零个或多个 p,每个都以 sep 结尾
EndBy1(p, sep) 一个或多个 p,每个都以 sep 结尾

以 SepBy1 为例:

public static virtual K<F, Seq<A>> SepBy1<A, SEP>(K<F, A> fa, K<F, SEP> sep) =>
    Applicative.lift(Seq.cons, fa, F.Many(sep >>> fa));

它先把 sep 与 fa 用 >>>(顺序组合)拼成"分隔符后跟元素",再交给 Many 重复执行,最后用 Seq.cons 把首元素与后续序列接起来。sepBy、sepBy1、endBy、endBy1 等均有同名的 Prelude/Module 函数入口。

3.4 条件终止:ManyUntil / SomeUntil / Skip* 系列

这一族组合子用于"持续消费直到某个终止条件成功":

  • ManyUntil(fa, fend):零次或多次执行 fa,直到 fend 成功;fend 的结果被消费并丢弃(如需保留请用 ManyUntil2);
  • SomeUntil(fa, fend):一次或多次版本;
  • SkipMany(fa):零次或多次执行 fa 但丢弃全部结果,恒成功;
  • SkipSome(fa):一次或多次执行 fa 并丢弃结果;
  • Skip(n, fa):恰好跳过 n 次(n <= 0 时等价于 Pure(unit));
  • SkipManyUntil(fa, fend) / SkipSomeUntil(fa, fend):跳过中间结果、直到 fend 成功并返回 fend 的值。

以 ManyUntil 的递归实现为例,终止分支由 |(Choose)保证:要么 fend 成功返回空序列,要么继续消费 fa 并递归:

K<F, Seq<A>> go() =>
    empty * fend | Applicative.lift(Seq.cons, fa, memoK(go));

3.5 默认值与二选一:Option / Either

  • Option(value, fa):若 fa 失败(且未"消费"任何输入)则回退到默认值 value,实现只有一行:fa | F.Pure(value);
  • Either(fa, fb):把两个备选结构提升为一个装进 Either<A, B> 的结果:
public static virtual K<F, Either<A, B>> Either<A, B>(K<F, A> fa, K<F, B> fb) =>
    (Left<A, B>) * fa | (Right<A, B>) * fb;

对应的 Prelude 入口是 option<F, A>(value, fa) 与 either<F, A, B>(ma, mb)。

四、为自定义类型实现 Alternative

实现 Alternative<F> 需要完成以下最小集合:

  1. 声明继承:class MyType : Alternative<MyType>(同时也就要求实现 Choice、Applicative、Functor 的抽象成员);
  2. 实现 Alternative<F>.Empty<A>(),给出"失败/空"代表值;
  3. 实现 Choice<F>.Choose<A>(fa, fb),定义选择规则;
  4. 按 README 约定提供 | 运算符(映射到 Choose),若 Combine 有特殊语义则再提供 + 运算符;
  5. 可选:实现 Some/Many 所需的 Apply/ApplyLazy 惰性重载,避免递归栈溢出。

仓库还提供了派生支持:在 Deriving/Alternative.cs 中定义了 Deriving.Alternative<Supertype, Subtype> 派生接口,用于在超类型/子类型之间自动派生特质实现,减少样板代码。

仓库内已经实现 Alternative 的类型包括 Option、Fin、Try、Arr、Lst、Seq、Set、HashSet、Iterable、Iterator、Eff、IO 以及 OptionT、FinT、TryT、ValidationT 等变换子(Transformer),可作为实现时的对照范本。例如 Seq.TraitImpl.cs 与 Lst.TraitImpl.cs 展示了集合类型如何以"空集合"为 Empty、以"元素拼接"为 Choose。

五、用 AlternativeLaw 验证实现正确性

纯靠测试用例覆盖组合子行为并不充分,Alternative 还要求满足一组代数定律(laws)。README 给出的定律如下:

choose(Pure(a), Pure(b)) = Pure(a)     // left-catch:左边成功则取左边
choose(Empty  , Pure(b)) = Pure(b)     // left-zero:左边失败则取右边
choose(Pure(a), Empty  ) = Pure(a)     // right-zero:右边失败不影响左边
choose(Empty  , Empty  ) = Empty       // 双重失败仍是失败

注意:AlternativeLaw 中的 choose 是指 | 运算符对应的 Choose,而非 Combine。Alternative 还要求 Applicative 与 Functor 定律成立,因此 AlternativeLaw 在验证时会先调用 ApplicativeLaw<F>.validate,再依次验证三条定律(见 Alternative.Laws.cs):

public static Validation<Error, Unit> validate(Func<K<F, int>, K<F, int>, bool>? equals = null)
{
    equals ??= (fa, fb) => fa.Equals(fb);
    return ApplicativeLaw<F>.validate(equals) >>
           leftCatchLaw(equals)               >>
           leftZeroLaw(equals)                >>
           rightZeroLaw(equals);
}

使用方法有两种:

// 直接断言:若不满足定律则抛出异常
AlternativeLaw<Option>.assert();

// 校验模式:返回 Validation<Error, Unit>,可自行处理
var result = AlternativeLaw<Option>.validate();

validate 接受一个可选参数 equals: Func<K<F, int>, K<F, int>, bool>。其含义在源码注释中说得非常清楚:定律的成立需要依赖 K<F, *> 派生类型实现 Equals;如果你的 Alternative 结构没有实现相等性比较,就必须传入自定义的 equals 函数,否则无法证明定律成立。

定律的实现细节

三个定律分别对应三个方法:

  • leftCatchLaw:choose(F.Pure(100), F.Pure(200)) 必须等于 F.Pure(100);
  • leftZeroLaw:choose(F.Empty<int>(), F.Pure(100)) 必须等于 F.Pure(100);
  • rightZeroLaw:choose(F.Pure(100), F.Empty<int>()) 必须等于 F.Pure(100)。

任何一条不满足,都会得到 Error.New($"... law does not hold for {typeof(F).Name}") 形式的错误。

仓库中的真实验证用例

AlternativeLawTests.cs 为语言核心的每个 Alternative 实现都写了 xUnit 测试。对于像 Eff、IO、Try 这类延迟求值的类型,测试必须显式提供 equals:

[Fact]
public void IO()
{
    bool eq(K<IO, int> vx, K<IO, int> vy) =>
        vx.RunSafe().Equals(vy.RunSafe());

    AlternativeLaw<IO>.assert(eq);
}

而 Option、Fin、Arr、Lst、Seq、Validation<StringM> 等值类型因为实现了结构相等性,直接 AlternativeLaw<T>.assert() 即可:

[Fact]
public void Option() =>
    AlternativeLaw<Option>.assert();

[Fact]
public void Fin() =>
    AlternativeLaw<Fin>.assert();

完整的受测清单包括:Arr、HashSet、Iterable、Lst、Seq、Eff<Unit>、Eff、IO、Fin、FinT<Identity>、Option、OptionT<Identity>、Try、TryT<Identity>、Validation<StringM>、ValidationT<StringM, Identity>,基本覆盖了仓库中所有 Alternative 实例。

六、实战示例:用 Option 串起整条链路

把本文的要点串成一个最小可运行片段。首先确保项目引用 LanguageExt.Core(例如通过 LanguageExt.Core.csproj),然后:

using LanguageExt;
using LanguageExt.Traits;
using static LanguageExt.Prelude;

// 1) 直接使用 | 运算符(Option 的 Choose)
var r1 = Some(1) | Some(2);   // Some(1) —— 左边成功
var r2 = None   | Some(2);    // Some(2) —— 左边失败,取右边
var r3 = None   | None;       // None    —— 双重失败

// 2) oneOf:从一组备选中挑第一个成功者
var r4 = oneOf<Option, int>(None, None, Some(3), Some(4));
//   → Some(3)

// 3) option:失败回退到默认值
var r5 = option(42, None);    // Some(42)

// 4) many:重复执行直到失败,收集结果
var r6 = many(Some(1) | None);  // 逐个执行 Some(1) 直到 None 为止
//   → Seq 中累积了多个 1(取决于实现中的 Apply 惰性)

// 5) 验证定律
AlternativeLaw<Option>.assert();

第 4 行体现的是"在 Option 上运行解析器组合子"的典型姿态:many(fa) 反复尝试 fa,直到某次 fa 返回 None 即停止累积。这也是为什么 README 与源码都强调 Some/Many 依赖惰性 Apply——每一步递归都必须延迟到"前一步已成功"之后才执行。

七、总结

Alternative<F> 是 language-ext 对函数式编程中"失败 + 选择 + 单位值"这一组合抽象的 C# 落地。它的设计要点可以概括为四条:

  1. 组合而非发明:Alternative = Choice + MonoidK + Applicative,Empty 提供零元素,Combine 默认退化为 Choose,但允许类型各自重载;
  2. 语义精确分离:Choose(|)管"选择/失败传播",Combine(+)管"拼接/累积",两种心智模型不可混淆;
  3. 开箱即用的组合子:Choice、Some/Many、SepBy 族、ManyUntil 族、Option/Either、Skip* 族让 Alternative 直接可用作通用解析器组合子基础设施;
  4. 定律驱动验证:AlternativeLaw 通过 leftCatch、leftZero、rightZero 三条定律(外加 ApplicativeLaw 与 Functor 定律)把代数正确性变成可执行测试,仓库的 AlternativeLawTests.cs 即为最佳范例。

对于任何需要"失败时换一条路继续尝试"的 C# 场景——配置解析、输入校验、备选数据源、分支逻辑抽象——Alternative<F> 都提供了一套类型安全、可组合、可验证的统一方案。

登录后查看全文
language-ext