Manual constructor specialization

9 Oct 2007

      I have a rope data type with the invariant that one of its data
constructors can never appear as a leaf.

module Data.Rope where

import Data.Word (Word8)

data Rope = Empty
          | Leaf
          | Node !Rope !Rope

index :: Rope -> Int -> Word8
index Empty _      = error "empty"
index Leaf _       = error "leaf"
index (Node l r) n = index' l n
    where
      index' Leaf _       = error "leaf"
      index' (Node l r) n = index' l n

I removed some of the actual details (Leafs have a ByteString member
and Nodes have a length and a depth field). The point is that Empty
can only appear at the top by construction (i.e. it's not possible to
construct a rope that breaks this invariant using the exported API).
If I understand compilation of case statements correctly they will
compile into some if like construct that checks the constructor tag.
This means that I would like that once we have established that the
constructor is not Empty we could use a specialized function to
traverse the tree without checking for Empty on each iteration. The
above doesn't achieve this as GHC inserts an automatic error branch
for Empty in index'. Perhaps one solution is to reorder the cases and
remove index'?

-- Johan

Johan Tibell

David Benbennick

Johan Tibell

Thomas Schilling

ChrisK

Roberto Zunino

Bryan O'Sullivan

tags

participants (6)