如何在纯 F# 中实现关系 JOIN？

Question

我正在构建一个在本质上类似于 j/kdb+/tutorialD 的关系 language/library。

这个想法是 end-user 将：加载数据（在内存中，从任何地方），执行查询，执行连接，聚合等。所以，就像到处都有 LINQ，as a first-class citizen 的语言。

关系由以下部分组成：

1- 带有名称 * 类型对列表的标题 2- 带有行列表的 body，其中每一行必须符合标题

所以，就像 table。

像这样：

type ExprC =
    | BoolC of bool
    | DecC of decimal
    | Str16C of string #And others!
and
  ColumnC = {name:string; colType:ExprC}
and
  HeaderC = ColumnC array
and
  RelC = {header:array<string>; data:array<array<ExprC>>}

所以，我需要实现完整的关系运算符。 PROJECTION (select) & RESTRICTION (where) 很简单，但 JOIN 看起来很棘手。这是因为我需要遍历两列（并对它们进行排序？）来计算连接，然后删除用于连接的重复列，然后生成结果。

分别做每一件事很容易，但我认为有很多浪费的可能性。我发现声称 merge-sort-join 是要走的路，但不知道如何适用于我正在解释的这种情况。

我目前可以改变任何东西..我唯一的要求是解决方案不会严重阻碍完整关系模型的实施并且性能是 "ok".

Answer 1

Jon Skeet 使用 C# 重新实现了 LINQ to Objects，它可以启发您。以下是两个序列的 JOIN（内部连接）实现的详细说明：Reimplementing LINQ to Objects: Part 19 – Join.

如何在纯 F# 中实现关系 JOIN？

How implement the relational JOIN in pure F#?

algorithm

f#

join

relational-algebra