[Haskell-cafe] Static computation/inlining
Felipe Lessa
felipe.lessa at gmail.com
Mon Oct 11 06:51:22 EDT 2010
On Sun, Oct 10, 2010 at 10:51 PM, Alexander Solla <ajs at 2piix.com> 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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ModuleWithData.hs
Type: text/x-haskell
Size: 1057 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20101011/3fd7ea02/ModuleWithData-0001.bin
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ModuleWithFunctions.hs
Type: text/x-haskell
Size: 207 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20101011/3fd7ea02/ModuleWithFunctions-0001.bin
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Template.hs
Type: text/x-haskell
Size: 651 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20101011/3fd7ea02/Template-0001.bin
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Module.hs
Type: text/x-haskell
Size: 129 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20101011/3fd7ea02/Module-0001.bin
More information about the Haskell-Cafe
mailing list