import Data.Map as Map
import Data.Map ((!))

data Cache a b = Cache (a -> b) (Map a b)

insert :: (a -> b) -> Cache a b
insert fun =
	Cache fun Map.empty

apply :: Ord a => (Cache a b) -> a -> b
apply (Cache fun m) x =
	if Map.member x m
		then m ! x
	else
		fun x

applyMutate :: Ord a => (Cache a b) -> a -> (Cache a b, b)
applyMutate cache@(Cache fun m) x =
	(Cache fun (Map.insert x out m), out) where
		out = apply cache x

mapCache :: Ord a => (Cache a b) -> [a] -> [b]
mapCache _ [] = []
mapCache cache (x:xs) = out : (mapCache cache1 xs) where
	(cache1, out) = applyMutate cache x


main = putStrLn "Hello World"

Hello World