Heaps should be more dynamic than this; the (type of the) *reference* should encode the type it points to, but the (type of the) *heap* should not.
However, the heap can store polymorphic values. Therefore, we can use a heap to store the polymorphic heap... Your example, slightly re-written as follows, types test5 = do let heapi = init_gh let (href,heap2) = alloc_gh undefined heapi let (mr,heap1) = if 1<2 then let (xr,h) = alloc_gh 42 heapi heap2' = alter_gh href h heap2 in (Just xr,heap2') else (Nothing,heap2) print $ case mr of Nothing -> "" Just r -> show (fetch_gh r (fetch_gh href heap1)) and even prints the answer to everything...