[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