如何在F#中自动化地图查找链？

Question

我经常有理由在地图中查找一些关键字,然后在另一个地图中查找结果,依此类推,并寻求推广流程.我还希望能够为此目的预先计算地图列表,以表示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").当我需要使用地图的域和范围类型不同的数据时,问题就出现了.例如,如果我在上面的示例中添加汇率图,则类型检查器会抱怨,即使所涉及的各个操作都不会失败.

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]

尽管Map.tryFind的以下应用程序都是有效的,但类型检查器仍抱怨exchange_rate应为Map <string,string>类型.

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

如果我在C#这样看来,这将是相对简单过过型词典的数据<IComparable的,IComparable的>,并确定maybe_map明确任何"鸭子类型"的语言也没问题,但我看不出如何做到这一点在F#中.

解决这种问题的引用,似乎要拿出相当往往是http://codebetter.com/matthewpodwysocki/2009/01/28/much-ado-about-monads-maybe-edition/随后基于一种方法单子.实际上,这里的示例中使用的数据来自本文.然而,尽管使用monads做一些事情这个简单的事实似乎是使用大锤来破解坚果,但是当地图的域和范围类型不同时,文章中给出的解决方案也会崩溃.

有没有人知道我如何才能在这方面取得进展,而不会在概念上非常简单地引入显着的额外复杂性？

结语

在考虑了这个问题后收到的非常有用的输入后,我们决定采用这种方式.

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)

你可以使用函数组合将搜索的地图链接在一起:

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

searchAll (Some "John") //Some 1.08

这可以确保map的值N类型与map的键类型匹配N+1.我没有看到一种方法来搜索一个list<Map<_,_>>没有求助于某些界面(如IDictionary)和插入调用box/ unbox回避类型系统.

顺便说一下,你的maybe_map功能可以编写

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

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

编辑

由于您的映射未在编译时定义,并且由类型args不同,因此您可以在运行时构建查找函数的集合.

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

它不够整洁,但符合您的要求.