Skip to content

GitLab

  • Projects
  • Groups
  • Snippets
  • Help
    • Loading...
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
  • Sign in / Register
GHC
GHC
  • Project overview
    • Project overview
    • Details
    • Activity
    • Releases
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
    • Locked Files
  • Issues 4,393
    • Issues 4,393
    • List
    • Boards
    • Labels
    • Service Desk
    • Milestones
    • Iterations
  • Merge Requests 381
    • Merge Requests 381
  • Requirements
    • Requirements
    • List
  • CI / CD
    • CI / CD
    • Pipelines
    • Jobs
    • Schedules
    • Test Cases
  • Operations
    • Operations
    • Incidents
    • Environments
  • Analytics
    • Analytics
    • CI / CD
    • Code Review
    • Insights
    • Issue
    • Repository
    • Value Stream
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Members
    • Members
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • Glasgow Haskell Compiler
  • GHCGHC
  • Issues
  • #4937

Closed
Open
Opened Jan 31, 2011 by tibbe@trac-tibbe

Remove indirections caused by sum types, such as Maybe

While null pointers cause correctness issues in languages that allow them, they do have one benefit over Maybe when used to represent nullable values: they allow encoding the absence of a value cheaply. Using Maybe to represent a nullable value adds an extra indirection (pointer) to get to the wrapped value.

We could use the bits set by pointer tagging to encode that the pointer points directly to the value, rather than to an intermediate constructor. I believe JHC takes this approach.

A motivating example is this implementation of a hash array mapped trie (HAMT): A HAMT stores key/value pairs and subtrees in two arrays.

data Node k v = MkNode (Array (Maybe k)) (Array (Either v (Node k v))

Iff index i in the first array is Nothing, the second array contains a Node at index i, otherwise it contains a value.

Adding an extra indirection, using Maybe or Either, adds both space (in terms of extra points and data constructor headers) and time (in terms of additional cache misses and branches).

Trac metadata
Trac field Value
Version 7.0.1
Type FeatureRequest
TypeOfFailure OtherFailure
Priority normal
Resolution Unresolved
Component Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture
Assignee
Assign to
8.0.1
Milestone
8.0.1 (Past due)
Assign milestone
Time tracking
None
Due date
None
Reference: ghc/ghc#4937