language-ext 的 `Alternative<F>` 特质:失败传播、选择语义与 law 验证实战指南
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 明确说明:
Alternativeis aChoiceandMonoidK, which means it has aChoosemethod, aCombinemethod (which defaults to calling theChoosemethod), and anEmptymethod.
也就是说,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> 需要完成以下最小集合:
- 声明继承:
class MyType : Alternative<MyType>(同时也就要求实现Choice、Applicative、Functor的抽象成员); - 实现
Alternative<F>.Empty<A>(),给出"失败/空"代表值; - 实现
Choice<F>.Choose<A>(fa, fb),定义选择规则; - 按 README 约定提供
|运算符(映射到Choose),若Combine有特殊语义则再提供+运算符; - 可选:实现
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# 落地。它的设计要点可以概括为四条:
- 组合而非发明:
Alternative = Choice + MonoidK + Applicative,Empty提供零元素,Combine默认退化为Choose,但允许类型各自重载; - 语义精确分离:
Choose(|)管"选择/失败传播",Combine(+)管"拼接/累积",两种心智模型不可混淆; - 开箱即用的组合子:
Choice、Some/Many、SepBy族、ManyUntil族、Option/Either、Skip*族让Alternative直接可用作通用解析器组合子基础设施; - 定律驱动验证:
AlternativeLaw通过leftCatch、leftZero、rightZero三条定律(外加ApplicativeLaw与Functor定律)把代数正确性变成可执行测试,仓库的 AlternativeLawTests.cs 即为最佳范例。
对于任何需要"失败时换一条路继续尝试"的 C# 场景——配置解析、输入校验、备选数据源、分支逻辑抽象——Alternative<F> 都提供了一套类型安全、可组合、可验证的统一方案。