types - 如何在 F# 中自动执行 map 查找链？

Question

我经常有理由在 map 中查找一些键，然后在另一个 map 中查找结果，依此类推，在任意链中，我正在寻求概括该过程。我还希望能够为此目的预先计算 map 列表，以表示 AI 项目中可重用的关联链。

显而易见的解决方案似乎是对我称之为“maybe_map”的列表的 map 函数的简单扩展。

let rec maybe_map operation initial_value list =
  match list with
  | []          -> Some(initial_value)
  | first::rest ->
    match operation initial_value first with
    | None                   -> None
    | Some(subsequent_value) -> maybe_map operation subsequent_value rest 

以下是它的使用示例。

let employee_department = Map.ofList([("John", "Sales" ); ("Bob",    "IT"    )])
let department_country  = Map.ofList([("IT",   "USA"   ); ("Sales",  "France")])
let country_currency    = Map.ofList([("USA",  "Dollar"); ("France", "Euro"  )])

let result = maybe_map Map.tryFind "John" [employee_department; department_country; country_currency]

这可以正常工作并产生结果 Some(“Euro”)。当我需要使用 map 的域和范围类型不同的数据时，问题就来了。例如，如果我在上面的示例中添加一个汇率映射，即使涉及的单个操作都不会失败，类型检查器也会提示。

let exchange_rate = Map.ofList([("Euro", 1.08); ("Dollar", 1.2)])

let result1 = maybe_map Map.tryFind "John" [employee_department; department_country; country_currency; exchange_rate]

类型检查器提示 exchange_rate 应该是 Map 类型，尽管 Map.tryFind 的以下应用程序都是有效的。

let result2 = Map.tryFind "John" employee_department
let result3 = Map.tryFind "Euro" exchange_rate

如果我在 C# 中执行此操作，似乎在 Dictionary 类型的数据上定义 Maybe_map 会相对简单，并且显然任何“Duck Typed”语言都没有问题，但我看不出如何做到这一点在 F# 中。

解决这种似乎经常出现的问题的引用是 http://codebetter.com/matthewpodwysocki/2009/01/28/much-ado-about-monads-maybe-edition/它遵循基于单子(monad)的方法。其实这里例子中用到的数据都是取自这篇文章。然而，尽管使用 monad 来做这么简单的事情看起来就像用大锤敲碎了坚果，但本地图的域和范围类型不同时，文章中给出的解决方案也会失效。

有谁知道我如何在这方面取得进展，而不会给概念上非常简单的东西带来额外的复杂性？

结语

在考虑了由于这个问题而收到的非常有用的输入之后，这就是我们决定采用的方法。

class chainable
{
  protected Dictionary<IComparable, IComparable> items = new Dictionary<IComparable,IComparable>();

  public chainable() {}

  public chainable(params pair[] pairs) { foreach (pair p in pairs) items.Add(p.key, p.value); }

  public void add(IComparable key, IComparable value) { items.Add(key, value); }

  public IComparable lookup(IComparable key) { if (items.ContainsKey(key)) return items[key]; else return null; }

  public static List<chainable> chain(params chainable[] chainables) { return new List<chainable>(chainables); }

  public static IComparable lookup(IComparable key, List<chainable> chain)
  {
    IComparable value = key;
    foreach (chainable link in chain) { value = link.lookup(value); if (value == null) return null; }
    return value;
  }
}

这个类的第一行实际上是对所需内容的规范，其余操作直接从它开始。

chainable employee_department = new chainable(new pair("John", "Sales" ), new pair("Bob",    "IT"    ));
chainable department_country  = new chainable(new pair("IT",   "USA"   ), new pair("Sales",  "France"));
chainable country_currency    = new chainable(new pair("USA",  "Dollar"), new pair("France", "Euro"  ));
chainable exchange_rate       = new chainable(new pair("Euro", 1.08    ), new pair("Dollar", 1.2     ));
List<chainable> chain = chainable.chain(employee_department, department_country, country_currency, exchange_rate);
IComparable result    = chainable.lookup("John", chain);

诚然，可链接类可以在 F# 中构建，但这只是使用 F# 语法编写 C#，所以我们决定去掉中间人。似乎 F# 并不总是能够从所需操作的直接描述中推断出您真正需要操作的数据类型。再次感谢您的帮助(抱歉，不能使用 Haskell)。

Answer 1

使用这个辅助函数

let search map = Option.bind (fun k -> Map.tryFind k map)

您可以使用函数组合将正在搜索的 map 链接在一起:

let searchAll = 
  search employee_department
  >> search department_country
  >> search country_currency
  >> search exchange_rate

searchAll (Some "John") //Some 1.08

这样可以确保映射 N 的值的类型匹配 map N+1 的键的类型.我看不到搜索 list<Map<_,_>> 的方法无需借助某些接口(interface)(如 IDictionary )并插入对 box 的调用/ unbox回避类型系统。

顺便提一下，您的 maybe_map函数可以写成

let maybeMap = List.fold (fun v m -> Option.bind (fun k -> Map.tryFind k m) v)

(对于不同类型的 Map 仍然不起作用)

编辑

由于您的 map 不是在编译时定义的，并且因类型参数而异，因此您可以在运行时构建查找函数的集合。

let maybeMap = Seq.fold (fun v f -> Option.bind f v)
let tryFind m (v: obj) = Map.tryFind (unbox v) m |> Option.map box

let lookups = ResizeArray() //using ResizeArray to emphasize that this is built dynamically
lookups.Add(tryFind employee_department)
lookups.Add(tryFind department_country)
lookups.Add(tryFind country_currency)
lookups.Add(tryFind exchange_rate)

maybeMap (Some (box "John")) lookups

它不是那么整洁，但符合您的要求。