How to construct a function from its graph?

user_7957944 0
Viewed 114

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?

haskell
2 Answers

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.

user_7459030

You could write something like this

fromGraph :: [(Int, b)] -> Int -> b
fromGraph g i = snd (g !! i)

This would only work for Int indices, and would also assume that for every i, the element in the graph g at g !! i would have index i as well. If you want to do it a little more generically, you could write this:

fromGraph :: Eq a => [(a, b)] -> a -> b
fromGraph g i = snd $ head $ filter ((==i) . fst) g

Not that this would still throw an error if you try to use this function with an index that is not part of the graph.

user_62529160
Related