FP Complete

Menu

Data types

Strictness annotations

#!/usr/bin/env stack
-- stack --resolver lts-12.21 script
import Data.Foldable (foldl')

data Foo = Foo Int
  deriving Show
data Bar = Bar !Int
  deriving Show
newtype Baz = Baz Int
  deriving Show

main :: IO ()
main = do
  print $ foldl'
    ((Foo total) x -> Foo (total + x))
    (Foo 0)
    [1..1000000]
  print $ foldl'
    ((Bar total) x -> Bar (total + x))
    (Bar 0)
    [1..1000000]
  print $ foldl'
    ((Baz total) x -> Baz (total + x))
    (Baz 0)
    [1..1000000]

Advantages of strictness annotations:

Recommendation: if you don’t need laziness in a field, make it strict.

Pattern matching

#!/usr/bin/env stack
-- stack --resolver lts-12.21 script
import Data.Foldable (foldl')
import UnliftIO.Exception (pureTry)

data Foo = Foo Int
  deriving Show
data Bar = Bar !Int
  deriving Show
newtype Baz = Baz Int
  deriving Show

main :: IO ()
main = do
  print $ pureTry $
    case Foo undefined of
      Foo _ -> "Hello World"
  print $ pureTry $
    case Bar undefined of
      Bar _ -> "Hello World"
  print $ pureTry $
    case Baz undefined of
      Baz _ -> "Hello World"

Memory layout

Unpack

That extra Int data constructor is annoying, get rid of it!

data Bar = Bar {-# UNPACK #-} !Int

Why not always unpack fields? It can be a pessimization with large data types due to copying lots of data instead of copying a single pointer. If the value is a machine word, it’s always better to unpack, thus the primitive type optimization.

What’s in an Int?

Int is defined in normal Haskell code, it’s not a GHC built-in. Don’t believe me?

https://www.stackage.org/haddock/lts-12.21/ghc-prim-0.5.2.0/GHC-Types.html#t:Int

data Int = I# Int#
data Word = W# Word#

Magic hash!

$ stack exec -- ghci -XMagicHash
GHCi, version 8.0.1: https://www.haskell.org/ghc/  :? for help
Prelude> import GHC.Prim
Prelude GHC.Prim> :k Int#
Int# :: TYPE 'GHC.Types.IntRep

Int# is the magic, built-in value provided by GHC, in the ghc-prim package.

#!/usr/bin/env stack
-- stack --resolver lts-12.21 script
{-# LANGUAGE MagicHash #-}
import GHC.Prim
import GHC.Types

main :: IO ()
main = print $ I# (5# +# 6#)

Going low level

High level, good code:

#!/usr/bin/env stack
-- stack --resolver lts-12.21 script

main :: IO ()
main = print $ sum [1..100 :: Int]

Hopefully GHC optimizes this into a tight loop. But let’s write that tight loop manually:

#!/usr/bin/env stack
-- stack --resolver lts-12.21 script
{-# LANGUAGE BangPatterns #-}
main :: IO ()
main = print $ loop 0 1
  where
    loop !total i
      | i > 100 = total
      | otherwise = loop (total + i) (i + 1)

OK, let’s get primitive!

#!/usr/bin/env stack
-- stack --resolver lts-12.21 script
{-# LANGUAGE MagicHash #-}
import GHC.Prim
import GHC.Types

main :: IO ()
main = print $ I# (loop 0# 1#)
  where
    loop total i
      | isTrue# (i ># 100#) = total
      | otherwise = loop (total +# i) (i +# 1#)

Sum type representation

Example:

data Foo = Bar !Int !Int | Baz !Int | Qux

How much memory needed for:

Constructors with no fields (like Qux or Nothing): one copy in memory shared by all usages.

Compare the following:

data Result = Success !Int | Failure
data MaybeResult = SomeResult !Result | NoResult

Versus:

data MaybeResult = Success !Int
                 | Failure
                 | NoResult

Takeaway: if performance is crucial, consider “inlining” layered sum types. Downside:

Pointer tagging

https://ghc.haskell.org/trac/ghc/wiki/Commentary/Rts/HaskellExecution/PointerTagging

Subscribe to our blog via email

Email subscriptions come from our Atom feed and are handled by Blogtrottr. You will only receive notifications of blog posts, and can unsubscribe any time.