用.NET实现全文搜索的理想函数式语言

Question

在我学习计算机科学的过程中，我学习了一些像Prolog这样的功能语言，但现在我只做了一些命令式的事情，比如C#、和Java。目前，我正在为一个网上商店创建一个全文搜索引擎，我已经走了相当远的“势在必行的方式”。但是，在偶然发现了一些功能语言之后，比如Clojure的Haskell，很明显，函数范式更适合于这个工作，而命令式的方式并不是适合这项工作的工具。

因此，我们有一个大约1000万条记录的全文索引。每个记录基本上都包含一个单词的出现，以及它起源的记录中的id和文本位置。

当用户输入搜索字符串时，它将被解析为表达式树。例如，搜索字符串“Transfer100W”的结果如下

AND('transformer%', OR(NEAR('100', 'W'), NEAR('100', 'watts'), '100W', '0.1kW'))

这里有一些额外的“情报”，但这与这个问题无关。

然后递归地计算表达式树，并生成几个sql查询，这些查询可能以.NET-DataTables的形式返回多达100,000行。然后将它们读入集合或字典，并根据谓词、交叉和联合应用，以查找与整个搜索表达式匹配的所有结果。对于近评价，还比较了已发现矿点的位置指标。但这一切都是必不可少的，需要大量的for-循环。

此外，还有一个排序函数，它将发现的单词出现的分数相加。仅作为前缀或与模糊匹配(由数据库服务器完成)的单词获得的分数低于精确匹配。

对于每个结果项，我还需要获得匹配的所有单词的列表，以便在结果页面中突出显示这些单词。

因此，粗略地说，评估算法是一个函数，类似

expression tree, full text index -> 
resulting items that match the expressin tree, 
each with a ranking sum 
and a list of all found word occurrences for this item

我只是在这里作一个粗略的概述，但我希望你能得到足够的图片。

现在，“现实世界”的制约因素：

• 整个应用程序(到目前为止)都是用C#编写的，因此与.NET的轻松集成至关重要。
• 将大量数据读入.NET-DataTable中，然后需要对其进行评估和转换。结果应该包含在.NET类型中(字典、集合、数组等等)。
• 表演是非常重要的。目前，我的算法通常需要两秒钟的时间来进行搜索(不包括sql)，这是可以的，但需要改进。我们的服务器有16个处理器，所以欢迎并行处理。由于我们每秒得到一个搜索请求，并且当前的实现是单线程的，所以处理器时间仍然可用。
• 语言(和编译器)应该是成熟的。

因为我需要继续使用.NET，所以我研究了.NET的Clojure、F#和Scala。

我非常喜欢Clojure的概念，但现在我无法评估它是否适合这项工作。阅读关于F#的文章给了我复杂的感觉，因为它似乎希望能够做任何事情，而我则倾向于对给定的任务采用一种更“纯粹”的数学方法。但也许F#也能做到这一点，但我还没有意识到。我还没有深入研究Scala，但它似乎已经很成熟了。

任何见解都是欢迎的！

Answer 1

我很好奇你为什么不把LINQ当作一种选择。它似乎满足了你所有的标准。注意，我对Scala没有经验，所以我不能对此发表评论。

• 整个应用程序(到目前为止)都是用C#编写的，因此与.NET的轻松集成至关重要。
• 将大量数据读入.NET-DataTable中，然后需要对其进行评估和转换。结果应该包含在.NET类型中(字典、集合、数组等等)。

在这里，LINQ > F# >Clojure。如果一切都在C#中，LINQ将是最容易集成的。Visual对智能感知和函数定义导航的支持在C#专用程序中似乎要好得多。从C#调用Clojure可能是可怕的--从理论上讲，它应该可以正常工作，但在实践中，要准备花费数周的时间来弄清楚为什么事情没有按您预期的方式工作。它确实被设计成顶级的东西；您从Clojure调用C#，向相反的方向走，在Clojure-CLR开发人员的优先级列表中并不是很高；这里有基本的支持，但是您得到了所得到的东西。

• 表演是非常重要的。目前，我的算法通常需要两秒钟的时间来进行搜索(不包括sql)，这是可以的，但需要改进。我们的服务器有16个处理器，所以欢迎并行处理。由于我们每秒得到一个搜索请求，并且当前的实现是单线程的，所以处理器时间仍然可用。

LINQ ~= F# > Clojure.我在其他地方读到过，LINQ的性能在大多数惯用的算法上比F#稍微好一点，但是它们已经足够接近了，所以这并不重要。PLINQ使并行化变得容易。Clojure-CLR的启动时间非常慢，运行时开销也会减慢速度。

• 语言(和编译器)应该是成熟的。

LINQ >= F# > Clojure.并不是说F#是不成熟的，但是Visual支持滞后了一点，世界上基于LINQ的生产代码(以及更多的堆栈溢出答案)要比F#多得多。

阅读关于F#的文章给了我复杂的感觉，因为它似乎希望能够做任何事情，而我则倾向于对给定的任务采用一种更“纯粹”的数学方法。但也许F#也能做到这一点，但我还没有意识到。

没有一种语言像Haskell那样纯粹，但就编写非纯代码的难度而言，我将其排序为: LINQ > Clojure > F# > Scala。只有通过调用不纯的方法才能使LINQ变得不纯。Clojure有引用和原子，F#任何东西都可以被指定为可变的，而Scala (据我理解)实际上只是一个函数特性。

不过，F#和Scala所具有的功能特性是对模式匹配的语言支持。在C#中，您需要某种继承层次结构或b?x:y操作符的链来进行功能操作(或者如果/如果您对非功能方法很满意的话)，模式匹配使对原始数据类型的不同变体的条件操作更加简洁。在计算精确的vs前缀和模糊匹配排名时，这可能是有用的，但是在这个简单的例子中，C#中的b?x:y链C#是非常清晰的--当匹配变得更加复杂时，语言集成模式匹配就变得更有价值了。

有趣的是，我认为您工具包中F#比LINQ更有用的一个方面不是查询，它的名称应该表明它可以处理，但是将搜索字符串解析成表达式树。是一个功能语言和模式匹配非常擅长的领域，添加FsLex和FsYacc之类的工具可以给您一个很大的优势。

尽管如此，我认为这个决定取决于你想要去的地方。如果你只想清理你的搜索算法并完成它，我会建议LINQ方法。但是，如果你想一件一件地进入一个更注重功能的整体程序风格(而且你的公司愿意为你投入的时间付费)，那么不妨考虑一下F#选项。无论是哪种方式，我都会首先使用LINQ选项，因为这对您来说可能更简单，并且帮助您在开始使用LINQ之后，指导您的变得更加实用。

简单地说，这里是您想要的，只需填写您的函数，为您的接近和相等的获取器，以及您的GetRank和GetStrings函数，并使用下面的

static IEnumerable<Record> FetchRecords(this Tree tree) {
    return tree.Op == "OR"    ? tree.Args.SelectMany(FetchRecords).Distinct() :
           tree.Op == "AND"   ? tree.Args.Select(FetchRecords).Aggregate((intersect, current) => intersect.Intersect(current)) :
           tree.Op == "NEAR"  ? FetchValsNear(tree.Args[0].Op, tree.Args[1].Op) :
                                FetchValsEqual(tree.Op);
}

static IEnumerable<Record> FetchValsEqual(string s) {
    throw new NotImplementedException();
}

static IEnumerable<Record> FetchValsNear(string s1, string s2) {
    throw new NotImplementedException();
}

static IEnumerable<Tuple<Record, double, string[]>> OrderByRank(this IEnumerable<Record> vals) {
    return from val in vals
           let rank = GetRank(val)
           orderby rank
           let strings = GetStringsIn(val)
           select Tuple.Create(val, rank, strings);
}

static string[] GetStringsIn(Record val) {
    throw new NotImplementedException();
}

static double GetRank(Record val) {
    throw new NotImplementedException();
}

class Tree {
    public string Op;
    public Tree[] Args;
}

struct Record {/*your record here--use struct so Distinct and Intersect above work naturally (or use class and override Equals)*/}

就像这样：

foreach (var tuple in myTree.FetchRecords().AsParallel().OrderByRank().Take(30)) {
    // add to datagrid or whatever
}

这既提供了简单的并行性，也提供了延迟性，因此GetStringsIn函数只能在您使用的记录上执行(在本例中是前30位)。(注意，AND选择器可以使用任何IntersectAll示例这里进行简化)。

Answer 2

• 整个应用程序(到目前为止)都是用C#编写的，因此与.NET的轻松集成至关重要。
• 将大量数据读入.NET-DataTable中，然后需要对其进行评估和转换。结果应该包含在.NET类型中(字典、集合、数组等等)。

F#应该是一个更好的选择。作为Visual中的一种一流语言，F#与C#的互操作性相当好.

• 表演是非常重要的。目前，我的算法通常需要两秒钟的时间来进行搜索(不包括sql)，这是可以的，但需要改进。我们的服务器有16个处理器，所以欢迎并行处理。由于我们每秒得到一个搜索请求，并且当前的实现是单线程的，所以处理器时间仍然可用。

假设您从一个功能优先且不可变的实现开始，那么您的应用程序应该很容易并行化。此外，对于像您这样的IO绑定应用程序，异步工作流是一种祝福。

• 语言(和编译器)应该是成熟的。

我不把F#比作JVM上的Clojure和Scala，但是F#要比.NET上的Clojure CLR和Scala成熟得多，在选择F#时，您肯定会得到微软的长期承诺和不断增长的F#社区的帮助。

当用户输入搜索字符串时，它将被解析为表达式树。

您可以使用受歧视的工会表示表达式树。通过在SQL3.0中引入查询表达式，您可以轻松地将逻辑转换为F#查询。您甚至可以通过为您的域定义类似的查询语言来进一步推进它。

阅读关于F#的文章给了我复杂的感觉，因为它似乎希望能够做任何事情，而我则倾向于对给定的任务采用一种更“纯粹”的数学方法。但也许F#也能做到这一点，但我还没有意识到。

F# 3.0引入了类型提供者，允许用户以一种类型安全的方式访问非结构化数据；为了获得更多的见解，您可能需要查看这个"F# 3.0 -信息丰富的编程“视频。如果您想使用F#作为数据挖掘的编程语言，我已经问了一个相关的问题，并得到了相当好的响应这里。

也就是说，你对F#的第一次感觉可能是不正确的。根据我的经验，你可以随心所欲地靠近功能和不变的一面。考虑到您已经有了一个有趣的应用程序，我建议您弄懂F#是否适合您的目的。

更新：

下面是一个F#原型，它演示了这个想法：

/// You start by modeling your domain with a set of types.
/// FullText is a sequence of Records, which is processed on demand.
type Word = string
and Freq = int
and Record = {Occurrences: (Word * Freq) list; Id: string}
and FullText = Record seq

/// Model your expression tree by following the grammar closely.
type Expression =
    | Occur of Word
    | Near of Word * Word
    | And of Expression * Expression 
    | Or of Expression * Expression

/// Find wether a word w occurs in the occurrence list.
let occur w {Occurrences = xs} = xs |> Seq.map fst |> Seq.exists ((=) w)

/// Check whether two words are near each other.
/// Note that type annotation is only needed for the stub implementation.
let near (w1: Word) (w2: Word) (r: Record): bool = failwith "Not implemented yet"

/// Evaluate an expression tree.
/// The code is succinct and clear thanks to pattern matching. 
let rec eval expr r = 
    match expr with
    | Occur w -> occur w r
    | Near(w1, w2) -> near w1 w2 r
    | And(e1, e2) -> eval e1 r && eval e2 r
    | Or(e1, e2) -> eval e1 r || eval e2 r

/// Utility function which returns second element in a 3-tuple
let inline snd3 (_, x, _) = x

/// Get the rank of the record by adding up frequencies on the whole database.
let rank (r: Record) (ft: FullText): Freq = failwith "Not implemented yet"

/// Retrieve all records which match the expression tree.
let retrieve expr fullText =
    fullText |> Seq.filter (eval expr)
             |> Seq.map (fun r -> r, rank r fullText, r.Occurrences)
             |> Seq.sortBy snd3

/// An example query
let query = 
    And (Occur "transformer%", 
         Or (Or (Near ("100", "W"), Near ("100", "watts")), 
             Or (Occur "100W", Occur "0.1kW")))