UnboxedSums.md

UnboxedSums

GHC 8.2.1で実装された言語拡張。anonymousでunboxedな直和型を実現する機能。

例: Maybe#

{-# LANGUAGE MagicHash #-} -- Maybe#のハッシュ記号に必要
{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE PolyKinds #-} -- a :: TYPE rに必要
{-# LANGUAGE UnboxedSums #-}
{-# LANGUAGE UnboxedTuples #-} -- (##)に必要
-- バイトコードインタープリタはUnboxedSumsに対応していないためGHCiでは-fobject-codeが必要
{-# OPTIONS_GHC -fobject-code #-}
module UnboxedMaybe where
import GHC.Exts (Int(I#), Int#, RuntimeRep(..), TYPE)

-- | Unboxed 'Maybe' with 'a :: Type'
type Maybe'# a = (# (##) | a #)

-- | Levity-polymorphic unboxed 'Maybe'
type Maybe# (a :: TYPE r) = (# (##) | a #)

-- | Unboxed 'Nothing'
pattern Nothing# :: Maybe# a
pattern Nothing# = (# (##) | #)

-- | Unboxed 'Just'
pattern Just# :: a -> Maybe# a
pattern Just# a = (# | a #)

boxMaybe :: Maybe# a -> Maybe a
boxMaybe Nothing# = Nothing
boxMaybe (Just# a) = Just a

boxMaybeInt :: Maybe# Int# -> Maybe Int
boxMaybeInt (# (##) | #) = Nothing
boxMaybeInt (# | i# #) = Just (I# i#)

メモリレイアウト

Maybe Intの場合

+--------+---------+
|  tag   | pointer |
+--------+----+----+
              |
              v
         +---------+---------+
         |   I#    |   42#   |
         +---------+---------+

Maybe# Intの場合

+--------+---------+
|  tag   | pointer |
+--------+----+----+
              |
              v
         +---------+---------+
         |   I#    |   42#   |
         +---------+---------+

Maybe# Int#の場合

+--------+---------+
|  tag   |   42#   |
+--------+---------+

最適化

data T1 a = Some a | None
data T2 a = C {-# UNPACK #-} !(T1 a)

このようなコードに対して最適化パスでCを次のように変換できるはず。

C (# a | (# #) #)

この最適化を実装する試みはあるがまだmergeされていない。

参考資料

• Glasgow Haskell Compiler User's Guide
• UnpackedSumTypes - GHC