@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