[Haskell-cafe] How to speedup generically parsing sum types?
Bas van Dijk
v.dijk.bas at gmail.com
Thu Nov 3 15:21:24 CET 2011
For those who find this interesting. Here's the code of the BigSum benchmark
with a manual Generic instance with inlined 'from' and 'to':
https://gist.github.com/1336426
José, I was thinking about the following idea. Say GHC generates the
following instance for BigSum:
instance Generic BigSum where
type Rep BigSum = D1 D1BigSum SumOfBigSum
...
type SumOfBigSum =
( ( ( C1 C1_0BigSum U1
:+: (C1 C1_1BigSum U1 :+: C1 C1_2BigSum U1)
)
:+: ( C1 C1_3BigSum U1
:+: (C1 C1_4BigSum U1 :+: C1 C1_5BigSum U1)
)
)
:+: ( ( C1 C1_6BigSum U1
:+: (C1 C1_7BigSum U1 :+: C1 C1_8BigSum U1)
)
:+: ( C1 C1_9BigSum U1
:+: (C1 C1_10BigSum U1 :+: C1 C1_11BigSum U1)
)
)
)
:+: ( ( ( C1 C1_12BigSum U1
:+: (C1 C1_13BigSum U1 :+: C1 C1_14BigSum U1)
)
:+: ( C1 C1_15BigSum U1
:+: (C1 C1_16BigSum U1 :+: C1 C1_17BigSum U1)
)
)
:+: ( ( C1 C1_18BigSum U1
:+: (C1 C1_19BigSum U1 :+: C1 C1_20BigSum U1)
)
:+: ( (C1 C1_21BigSum U1 :+: C1 C1_22BigSum U1)
:+: (C1 C1_23BigSum U1 :+: C1 C1_24BigSum U1)
)
)
)
It also generates the following function (or method): (I haven't
figured out the correct type yet. A correct version might need to use
type families or functional dependencies)
conPath :: String -> Maybe (C1 ? ? ? -> SumOfBigSum)
conPath "F01" = Just $ L1 . L1 . L1 . L1
conPath "F02" = Just $ L1 . L1 . L1 . R1 . L1
conPath "F03" = Just $ L1 . L1 . L1 . R1 . R1
conPath "F04" = Just $ L1 . L1 . R1 . L1
conPath "F05" = Just $ L1 . L1 . R1 . R1 . L1
conPath "F06" = Just $ L1 . L1 . R1 . R1 . R1
conPath "F07" = Just $ L1 . R1 . L1 . L1
conPath "F08" = Just $ L1 . R1 . L1 . R1 . L1
conPath "F09" = Just $ L1 . R1 . L1 . R1 . R1
conPath "F10" = Just $ L1 . R1 . R1 . L1
conPath "F11" = Just $ L1 . R1 . R1 . R1 . L1
conPath "F12" = Just $ L1 . R1 . R1 . R1 . R1
conPath "F13" = Just $ R1 . L1 . L1 . L1
conPath "F14" = Just $ R1 . L1 . L1 . R1 . L1
conPath "F15" = Just $ R1 . L1 . L1 . R1 . R1
conPath "F16" = Just $ R1 . L1 . R1 . L1
conPath "F17" = Just $ R1 . L1 . R1 . R1 . L1
conPath "F18" = Just $ R1 . L1 . R1 . R1 . R1
conPath "F19" = Just $ R1 . R1 . L1 . L1
conPath "F20" = Just $ R1 . R1 . L1 . R1 . L1
conPath "F21" = Just $ R1 . R1 . L1 . R1 . R1
conPath "F22" = Just $ R1 . R1 . R1 . L1 . L1
conPath "F23" = Just $ R1 . R1 . R1 . L1 . R1
conPath "F24" = Just $ R1 . R1 . R1 . R1 . L1
conPath "F25" = Just $ R1 . R1 . R1 . R1 . R1
conPath _ = Nothing
conPath is given the name of the constructor. If it's a valid name it
will return a function that constructs a SumOfBigSum given the
corresponding constructor. Of course, since the types of the
constructors can vary (not in this case) coming up with a correct
implementation is a challenge.
Using conPath in my gParseJSON is easy:
instance (GFromJSON a, GFromJSON b) => GFromJSON (a :+: b) where
gParseJSON (Object (M.toList -> [(key, val)])) =
case conPath key of
Nothing -> mzero
Just path -> path <$> gParseJSON val
gParseJSON v = typeMismatch "sum (:+:)" v
{-# INLINE gParseJSON #-}
I suspect this to be much more efficient.
Bas
More information about the Haskell-Cafe
mailing list