Lazy decoding of a list with Data.Binary

I am lazily encoding lists using this code (taken from this SO question):

import Data.Binary

newtype Stream a = Stream { unstream :: [a] }

instance Binary a => Binary (Stream a) where

    put (Stream [])     = putWord8 0
    put (Stream (x:xs)) = putWord8 1 >> put x >> put (Stream xs)

The problem is that the decoding implementation is not lazy:

    get = do
        t <- getWord8
        case t of
            0 -> return (Stream [])
            1 -> do x         <- get
                    Stream xs <- get
                    return (Stream (x:xs))

This looks to me like it should be lazy, but if we run this test code:

head $ unstream (decode $ encode $ Stream [1..10000000::Integer] :: Stream Integer)

memory usage explodes. For some reason it wants to decode the whole list before letting me look at the first element.

Why is this not lazy, and how I can make it lazy?