On Sun, Oct 10, 2010 at 10:51 PM, Alexander Solla <[email protected]> wrote:
> Is there anyway to instruct GHC (and maybe other compilers) to compute these
> maps statically? Are GHC and the other compilers smart enough to do it
> automatically? Although the list isn't huge, I would still rather get rid of
> the O(2*n) operation of turning it into maps at run-time. (Especially since
> some later list encodings like these might be enormous) What should I be
> looking into?
You may use Template Haskell and forget about the 'Data.Map's entirely =).
I've attached a proof-of-concept code that turns
list :: [(a,b)]
list = [(x1,y1), (x2, y2), ..., (xn, yn)]
into two functions (you can choose the names)
fromAtoB :: a -> b
fromAtoB x1 = y1
fromAtoB x2 = y2
...
fromAtoB xn = yn
fromBtoA :: b -> a
fromBtoA y1 = x1
...
fromBtoA yn = xn
but with the arguments tranformed to patterns.
Compiling a test module:
$ ghc -ddump-splices -c ModuleWithFunctions.hs
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
Loading package array-0.3.0.1 ... linking ... done.
Loading package containers-0.3.0.0 ... linking ... done.
Loading package pretty-1.0.1.1 ... linking ... done.
Loading package template-haskell ... linking ... done.
ModuleWithFunctions.hs:1:0:
ModuleWithFunctions.hs:1:0: Splicing declarations
bimap
"map_country_to_country_code"
"map_country_code_to_country"
countries_and_iso_country_codes
======>
ModuleWithFunctions.hs:8:2-98
map_country_to_country_code Afghanistan
= ISOCountryCode AF AFG (NC 4)
map_country_to_country_code AlandIslands
= ISOCountryCode AX ALA (NC 248)
map_country_to_country_code Albania = ISOCountryCode AL ALB (NC 8)
map_country_to_country_code Zimbabwe
= ISOCountryCode ZW ZWE (NC 716)
map_country_code_to_country ISOCountryCode AF AFG NC 4
= Afghanistan
map_country_code_to_country ISOCountryCode AX ALA NC 248
= AlandIslands
map_country_code_to_country ISOCountryCode AL ALB NC 8 = Albania
map_country_code_to_country ISOCountryCode ZW ZWE NC 716 = Zimbabwe
So two functions were spliced into your code with explicit pattern
matches. I don't know how efficient is the code that GHC generates
for functions with many patterns. Now, testing them:
$ ghci
GHCi, version 6.12.3: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
:Prelude> :l Module
[4 of 4] Compiling Module ( Module.hs, interpreted )
Ok, modules loaded: Module, ModuleWithData, ModuleWithFunctions, Template.
*Module> :bro Module
data Country = Afghanistan | AlandIslands | Albania | Zimbabwe
data ISOCountryCode = ISOCountryCode TwoCode ThreeCode NumCode
data NumCode = NC Int
data ThreeCode = AFG | ALA | ALB | ZWE
data TwoCode = AF | AX | AL | ZW
countries_and_iso_country_codes :: [(Country, ISOCountryCode)]
isoNumericCode :: Int -> NumCode
map_country_code_to_country :: ISOCountryCode -> Country
map_country_to_country_code :: Country -> ISOCountryCode
*Module> map_country_to_country_code Albania
Loading package array-0.3.0.1 ... linking ... done.
Loading package containers-0.3.0.0 ... linking ... done.
Loading package pretty-1.0.1.1 ... linking ... done.
Loading package template-haskell ... linking ... done.
ISOCountryCode AL ALB (NC 8)
*Module> map_country_code_to_country $ ISOCountryCode AL ALB (NC 8)
Albania
Cheers! =)
--
Felipe.
{-# LANGUAGE DeriveDataTypeable #-}
module ModuleWithData where
import Data.Data
import Data.Typeable
data Country = Afghanistan | AlandIslands | Albania | Zimbabwe
deriving (Data, Eq, Ord, Show, Typeable)
data ISOCountryCode = ISOCountryCode TwoCode ThreeCode NumCode
deriving (Data, Eq, Ord, Show, Typeable)
data TwoCode = AF | AX | AL | ZW
deriving (Data, Eq, Ord, Show, Typeable)
data ThreeCode = AFG | ALA | ALB | ZWE
deriving (Data, Eq, Ord, Show, Typeable)
data NumCode = NC Int
deriving (Data, Eq, Ord, Show, Typeable)
isoNumericCode :: Int -> NumCode
isoNumericCode = NC
countries_and_iso_country_codes :: [ (Country, ISOCountryCode) ]
countries_and_iso_country_codes =
[ (Afghanistan, ISOCountryCode AF AFG (isoNumericCode 004))
, (AlandIslands, ISOCountryCode AX ALA (isoNumericCode 248))
, (Albania, ISOCountryCode AL ALB (isoNumericCode 008))
, (Zimbabwe, ISOCountryCode ZW ZWE (isoNumericCode 716))
]
{-# LANGUAGE TemplateHaskell #-}
module ModuleWithFunctions where
import ModuleWithData
import Template
$(bimap "map_country_to_country_code" "map_country_code_to_country" countries_and_iso_country_codes)
module Template (bimap, map') where
import Control.Monad
import Data.Data
import Language.Haskell.TH
import Language.Haskell.TH.Quote
bimap :: (Data a, Data b) => String -> String -> [(a,b)] -> Q [Dec]
bimap name1 name2 xs = do m1 <- map' name1 xs
m2 <- map' name2 [(b,a) | (a,b) <- xs]
return [m1,m2]
map' :: (Data a, Data b) => String -> [(a,b)] -> Q Dec
map' name xs = liftM (FunD $ mkName name) (mapM mkClause xs)
where
mkClause (a,b) = do
a_pat <- dataToPatQ (const Nothing) a
b_exp <- dataToExpQ (const Nothing) b
return $ Clause [a_pat] (NormalB b_exp) []
module Module
(module ModuleWithData
,module ModuleWithFunctions) where
import ModuleWithData
import ModuleWithFunctions
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
