How do I automate chains of map lookups in F#?

Question

I regularly have cause to lookup some key in a map and then lookup the result in another map and so on in an arbitrary chain and am seeking to generalise the process. I also want to be able pre-compute lists of maps for this purpose to represent re-usable chains of association in an AI project.

The obvious solution seems to be a simple extension of a map function over lists that I call “maybe_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 

The following is an example of its use.

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]

This works fine and yields the result Some(“Euro”). The problem comes when I need to use data in which the domain and range types of the maps differ. For example if I add an exchange rate map to the above example the type checker complains even though none of the individual operations involved would fail.

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]

The type checker complains that exchange_rate is expected to be of type Map<string,string> despite the fact that the following applications of Map.tryFind are both valid.

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

If I were doing this in C# it seems that it would be relatively straightforward to define maybe_map over over data of type Dictionary<IComparable, IComparable> and clearly any “Duck Typed” language would have no problem, but I cannot see how to do this in F#.

A reference to solving this kind of problem that seems to come up quite often is http://codebetter.com/matthewpodwysocki/2009/01/28/much-ado-about-monads-maybe-edition/ which follows an approach based on monads. In fact, the data used in the examples here are taken from this article. However, despite the fact that using monads to do something this simple seems like using a sledgehammer to crack a nut, the solution given in the article also breaks down when the domain and range types of the maps differ.

Does anyone know how I can make progress with this without introducing significant extra complexity to what seems conceptually very straightforward?

Epilog

After considering the very helpful input received as a result of this question, this is what we decided to go with.

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;
  }
}

The first line of this class is virtually a specification of what is required and the rest of the operations follow straightforwardly from it.

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);

Admittedly the chainable class could be constructed in F#, but that would just be writing C# using F# syntax so we have decided to cut-out the middle man. It seems that F# is not always able to infer the type of the data you really needed to operate on from a straightforward description of the operations required. Thanks again for the help (Sorry, but using Haskell was not an option).

Answer 1

Using this helper function

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

you could chain together the maps being searched using function composition:

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

searchAll (Some "John") //Some 1.08

This ensures that the type of the value of map N matches the type of the key of map N+1. I don't see a way of searching a list<Map<_,_>> without resorting to some interface (like IDictionary) and inserting calls to box/unbox to sidestep the type system.

Incidentally, your maybe_map function could be written

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

(which still doesn't work for Maps of different types)

EDIT

Since your maps aren't defined at compile time, and differ by type args, you could instead build a collection of lookup functions at run-time.

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

It's not as tidy, but meets your requirement.

Answer 2

@Daniel has given a brilliant solution. I want to comment on what can and cannot be done with generics: The original program is obviously type safe, so why doesn't the compiler realise that?

Here are the critical bits (paraphrasing):

let country_currency = Map.ofList([("USA",  "Dollar"); ("France", "Euro")])
let exchange_rate    = Map.ofList([("Euro", 1.08); ("Dollar", 1.2)])
let maps = [country_currency; exchange_rate]
// Error: "... Expecting a Map<string,string> but given a Map<string,float>"    

Well, F# lists are homogenous: they can contain only values of the same type (objects and casting not withstanding). But we want different types Map<..., string> and Map<string, float>, so we can't put chains of maps in lists. We don't really care need a list, though, we just want some collection of maps where the value-type of one is the key-type of the next. Let's try to make such a type.

type Chain<'T,'U> =
    | Link of Chain<'T,'R> * Chain<'R,'U>
    | Node of Map<'T,'U>

The compiler won't let us, though:

error FS0039: The type parameter 'R' is not defined

Ideally, we'd like the Link constructor to be generic in 'R, i.e., to write something like this:

    | Link<'R> of Chain<'T,'R> * Chain<'R,'U>

But this is also not allowed: All type parameters used to define type Chain<...> must be declared in the <...>. Objects and casting not withstanding, this means that a value of an F# type can be composed of only a fixed number of other types. But we don't know how many different types of Map we need to chain!

---

Let's say F# did allow Link to be generic independently of Chain. Then patten matching allows the type parameter 'R to escape:

match c : Chain<string, float> with 
| Link (c1, c2) -> ... // c1 : Map<string, 'R>,  c2 : Map<'R, float> ? 

Of course, the c was constructed somehow by some actual type instead of the type parameter 'R, but we don't know which. In this case, we say that c1 and c2 have "existential type": We know there "exists" some particular type we can put in for 'R above, but we don't know which. If we had such existential types, we could write the requested maybe_map:

// maybe_map<'T,'U> : 'T -> Chain<'T,'U> -> Option<'U> 
let rec maybe_map k = function
   | Node m -> Map.tryFind k m
   | Link (c1, c2) ->            // some 'R. c1: Map<'T,'R>, c2: Map<'R,'U>
        let o = maybe_map k c1   // o : ?'R option 
        match o with                
        | None -> None 
        | Some v -> maybe_map v c2   // : Option<'U>

We don't get to do this in F#, but the Haskell people do. Let's see the entire thing in Haskell:

{-# LANGUAGE ExistentialQuantification #-}

import Data.Map (Map)
import qualified Data.Map as Map

department_country = Map.fromList [("IT",   "USA"   ), ("Sales",  "France")]
country_currency   = Map.fromList [("USA",  "Dollar"), ("France", "Euro")]
exchange_rate      = Map.fromList [("Euro", 1.08),     ("Dollar", 1.2)]

data Chain t u =
    forall r. (Ord r) =>   -- Any type r can be inside the chain
       Link (Chain t r) (Chain r u)
  | Node (Map t u)

lookup :: (Ord t, Ord u) => t -> Chain t u -> Maybe u
lookup k (Node m) = Map.lookup k m
lookup k (Link c1 c2) = case lookup k c1 of
                           Just v -> lookup v c2
                           Nothing -> Nothing

chain = Link (Node department_country) 
             (Link (Node country_currency) (Node exchange_rate))

And try it out:

*Main> maybe_map "IT" chain
Just 1.2