How to construct a function from its graph?

Question

I wonder if it is possible to make the inverse of the following function:

graphOf :: (Num a, Enum a) => (a -> b) -> [(a, b)]
graphOf f = [(e,v) | e <- [0..], v <- [f e]]

I mean I don't figure out how to write a Haskell function

fromGraph ::  (Enum a) => [(a, b)] -> (a -> b)

such that

fromGraph [(1,3),(2,4),(3,5)] :: (Num a) => a -> a
(fromGraph [(1,3),(2,4),(3,5)]) 1 == 3
(fromGraph [(1,3),(2,4),(3,5)]) 2 == 4
(fromGraph [(1,3),(2,4),(3,5)]) 3 == 5

Is it possible? At least for finite input list?

Answer 1

The simplest way is to use the lookup function:

Prelude> :m +Data.List
Prelude Data.List> lookup 1 [(1,3),(2,4),(3,5)]
Just 3
Prelude Data.List> lookup 2 [(1,3),(2,4),(3,5)]
Just 4
Prelude Data.List> lookup 3 [(1,3),(2,4),(3,5)]
Just 5

This is pretty inefficient though (for every query it just goes through the list linearly). You may want to back it with a faster lookup mechanism, using structures from the containers or unordered-containers packages, for example

import qualified Data.HashMap.Strict as HMS
import Data.Hashable (Hashable)

fastLookup :: Hashable k => [(k,b)] -> k -> Maybe b
fastLookup l = \k -> HMS.lookup k table
 where table = HMS.fromList l

Note that I wrote fastLookup l = \k -> .... Do not simplify this to fastLookup l k = ..., because that would re-build the hash map for every query.