Как построить функцию из ее графика?

#haskell

Вопрос:

Интересно, можно ли сделать обратную следующую функцию:

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

Я имею в виду, я не понимаю, как написать функцию Haskell

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

такое, что

 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

Возможно ли это?
По крайней мере, для конечного списка входных данных?

1. Да, это возможно.

2. Несвязанный: [(e,v) | e <- [0..], v <- [f e]] может быть упрощен до [(e,v) | e <- [0..], let v = f e] или даже до [(e,f e) | e <- [0..]] . Нет необходимости создавать одноэлементный список [f e] только для того, чтобы иметь возможность извлекать из него ( v <- ... ) .

3. Вы можете зафиксировать ограничение, что график должен быть конечным, используя Bounded вместо Enum в ограничениях.

4. Смотрите Также Мой пакет юниверса ; он включает Read Show экземпляры and для функций, которые включают идеи в этом Q / A , и различные другие экземпляры и операции, которые могут быть полезны в тех же ситуациях, когда вы хотели graphOf бы и fromGraph .

Ответ №1:

Самый простой способ — использовать lookup функцию:

 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

Хотя это довольно неэффективно (для каждого запроса он просто проходит по списку линейно). Возможно, вы захотите подкрепить ее более быстрым механизмом поиска, используя структуры из containers unordered-containers пакетов or, например

 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

Обратите внимание, что я написал fastLookup l = k -> ... . Не упрощайте это fastLookup l k = ... , потому что это приведет к повторному построению хэш-карты для каждого запроса.

Ответ №2:

Вы могли бы написать что-то вроде этого

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

Это будет работать только для Int индексов, а также предполагает, что для каждого i элемента в графе g at g !! i i также будет иметь индекс. Если вы хотите сделать это немного более обобщенно, вы могли бы написать это:

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

Не то, чтобы это все равно выдавало ошибку, если вы попытаетесь использовать эту функцию с индексом, который не является частью графика.