Currency Conversion

I’ve re­cently re­turned to my hledger scripts from the memo “Visu­alise your fin­ances with hledger, In­fluxDB, and Grafana”, and in par­tic­ular adding sup­port for mul­tiple cur­ren­cies.

This got me thinking about market values. If I want to see the cur­rent market value of all my as­sets, I need to con­vert them all to the same cur­rency, using a re­cent ex­change rate. So I now have a script to fetch, once a day, ex­change rates between £ and everything else:

P 2018-05-30 BTC £5501.58
P 2018-05-30 ETH £413.01
P 2018-05-30 LTC £87.85
P 2018-05-30 EUR £0.8775
P 2018-05-30 JPY £0.0069
P 2018-05-30 USD £0.7531
P 2018-05-30 VANEA £210.24

My script ex­ports market values to in­fluxdb, so I can see how the market value of my as­sets (in £) has changed over time. Great!

But what if I want to see the market value in a cur­rency other than £? Like USD, for in­stance? The problem is that I have all these ex­change rates:

%3 BTC BTC £ £ BTC->£ * 5501.58 ETH ETH ETH->£ * 413.01 LTC LTC LTC->£ * 87.85 EUR EUR EUR->£ * 0.8775 JPY JPY JPY->£ * 0.0069 USD USD US­D->£ * 0.7531 VANEA VANEA VANEA->£ * 210.24

But I don’t have, say, the ex­change rate from EUR to USD.

Well it turns out that the re­flex­ive-sym­met­ric-trans­itive closure of that graph is just the thing I want! It looks pretty nasty with 7 cur­ren­cies, so here it is with just 3:

%3 £ £ £->£ * 1 BTC BTC £->BTC * ? ETH ETH £->ETH * ? BTC->£ * 5501.58 BTC->BTC * 1 BTC->ETH * ? ETH->£ * 0.8775 ETH­->BTC * ? ETH­->ETH * 1

Let’s see how to cal­cu­late those ?s.

Rep­res­enting graphs

I could pull in a func­tional graph lib­rary, but the graphs I’m dealing with are so small that I may as well just im­ple­ment the few op­er­a­tions I need my­self.

A graph is es­sen­tially a func­tion node -> node -> Maybe label:

im­port Data.Map (Map)
im­port qual­i­fied Data.Map as M

type Graph node label = Map node (Map node label)

We need an empty graph and, given a graph, we need to be able to add nodes and edges. As our nodes are the keys in the map, they need to be or­der­able.

-- | A graph with no nodes or edges.
empty :: Ord n => Graph n l
empty = M.empty

-- | Add a node to a graph.
addNode :: Ord n => n -> Graph n l -> Graph n l
addNode n = M.in­ser­t­With (\_ old -> old) n M.empty

We don’t allow du­plicate edges, as that means we have two ex­change rates between the same pair of cur­ren­cies, which doesn’t make much sense. So adding edges is a little more in­volved, as the edge might already ex­ist:

-- | Add an edge to a graph, com­bining edges if they ex­ist.
--
-- If the source node doesn't ex­ist, does not change the graph.
ad­dEdge :: Ord n
  => (l -> l -> l)  -- ^ Func­tion to com­bine edge la­bels.
  -> n  -- ^ Source node.
  -> n  -- ^ Target node.
  -> l  -- ^ New la­bel.
  -> Graph n l -> Graph n l
ad­dEdge com­bine from to label graph = case M.lookup from graph of
  Just edges ->
    let edges' = M.in­ser­t­With com­bine to label edges
    in M.in­sert from edges' graph
  Nothing -> graph

Com­puting the closure

Ok, so we can rep­resent our cur­rency graph. Now we need to com­pute the re­flex­ive-sym­met­ric-trans­itive clos­ure.

Re­flex­ivity lets us go from a cur­rency to it­self:

-- | Take the re­flexive closure by adding edges with the given label
-- where miss­ing.
re­flex­ive­Closure :: Ord n => l -> Graph n l -> Graph n l
re­flex­ive­Closure label graph = foldr (.) id
  [ ad­dEdge (\_ old -> old) nA nA label
  | nA <- M.keys graph
  ] graph

If we know a ex­change rate from A to B, sym­metry gives us an ex­change rate from B to A:

-- | Take the sym­metric closure by adding new edges, trans­forming
-- ex­isting la­bels.
sym­met­ric­Closure :: Ord n => (l -> l) -> Graph n l -> Graph n l
sym­met­ric­Closure mk graph = foldr (.) id
  [ ad­dEdge (\_ old -> old) nB nA (mk lAB)
  | (nA, edges) <- M.as­socs graph
  , (nB, lAB) <- M.as­socs edges
  ] graph

If we know an ex­change rate from A to B, and from B to C, trans­it­ivity gives us an ex­change rate from A to C:

-- | Take the trans­itive closure by adding new edges, com­bining
-- ex­isting la­bels.
trans­it­ive­Closure :: (Ord n, Eq l) => (l -> l -> l) -> Graph n l -> Graph n l
trans­it­ive­Closure com­bine = fixEq step where
  fixEq f = find . it­erate f where
    find (a1:a2:as)
      | a1 == a2 = a1
      | oth­er­wise = find (a2:as)

  step graph = foldr (.) id
    [ ad­dEdge (\_ old -> old) nA nC (com­bine lAB lBC)
    | (nA, edges) <- M.as­socs graph
    , (nB, lAB) <- M.as­socs edges
    , (nC, lBC) <- M.as­socs (M.find­With­De­fault M.empty nB graph)
    ] graph

Put­ting it all to­gether

Ex­change rates have three prop­er­ties which we can make use of:

  • Any cur­rency has an ex­change rate with it­self of 1.

  • If we have an ex­change rate of x from A to B, then the rate from B to A is 1/x.

  • If we have an ex­change rate of x from A to B, and an ex­change rate of y from B to C, then the rate from A to C is x*y.

So, given our graph of ex­change rates, we can fill in the blanks like so:

-- | Fill in the blanks in an ex­change rate graph.
com­plet­eR­ates :: (Ord n, Eq l, Frac­tional l) => Graph n l -> Graph n l
com­plet­eR­ates =
  trans­it­ive­Closure (*) .
  sym­met­ric­Closure (1/) .
  re­flex­ive­Closure 1

There’s also a fourth prop­erty we can as­sume in real­ity:

  • Any two paths between the same two cur­ren­cies work out to the same ex­change rate.

Oth­er­wise we could make a profit by going around in a circle, and I’m sure someone would have no­ticed that already and made a lot of money. In our im­ple­ment­a­tion however, we can’t as­sume that. Ex­change rates avail­able on­line have lim­ited pre­ci­sion, and rounding er­rors will in­tro­duce more prob­lems. But in gen­eral things will be close, so it doesn’t matter too much from the per­spective of get­ting a rough idea of our per­sonal fin­ances.

So now I can look at my total as­sets in yen and feel like a mil­lion­aire:

Market value of assets in JPY

Market value of as­sets in JPY

Date
Tags
finance, haskell, programming
Target Audience
The intersection of Haskell programmers, personal finance nerds, and graph nerds.