Phantom Types in Haskell

Question

This is a simplified version of my problem.

I have a recursive data structure (Stream1). When I introduced phantom types (Stream a), a recursive description (i.e. t1) no longer works. On the other hand, t2 works fine by creating an infinite structure, as it uses Stream1 directly. I need to use the constructor preI, such as in t1. What am I missing? I need t1 to behave like t2 - that is, return an infinite stream.

data Stream a = Stream Stream1
  deriving (Eq, Show)

data Stream1 = PreI Integer Stream1
  deriving (Eq, Show)

preI :: Integer -> Stream Int -> Stream Int
preI n (Stream s) = Stream (PreI n s)

t1 :: Stream Int
t1 = let x = preI 0 x
     in x

t2 :: Stream Int
t2 = let x = PreI 0 x
     in Stream x

Answer 1

preI :: Integer -> Stream Int -> Stream Int
preI n (Stream s) = ...
    -- ^^^^^^^^^^

This pattern matching forces the argument before any output is produced. For streams, this is bad, since it keeps the least fixed point at bottom (non-termination) instead of at an infinite stream.

You can try a lazy/irrefutable pattern matching instead:

preI :: Integer -> Stream Int -> Stream Int
preI n ~(Stream s) = Stream (PreI n s)
    -- ^

This essentially means:

preI :: Integer -> Stream Int -> Stream Int
preI n z = Stream (PreI n s)
    where s = case z of Stream x -> x

which first produces the Stream, PreI in the output, and only later on starts unwrapping its input (which happens when s is used).

Or, even better, change Stream from being a data to being a newtype: in such way, the pattern matching will always be lazy. Indeed, using newtype we no longer have any wrapping at runtime, and pattern matching is actually a no-op.