(Apologies for the bad formatting, but I lack the patience to correct it once more, it's being screwed up repeatedly)

The error message is probably related to the fact that it can't deduce what the type of the literal 1 is. 1 could be an Int, an Integer, a Float, etc. Haskell knows it must be an instance of the Bits class, but that still leaves open a lot of possibilities. You can solve the problem by giving explicit type annotations.

test :: Integer
test = fsr 1 1

Also, I can't get the hang of working with the State monad, which I'm under the impression is the best one to use in this case.

I guess I'm trying to make a Functor or something. I'm still a rookie programmer, so I don't really know.

I need state for a PRNG, obviously. I just need one tuple for now, containing a mask Bits and some state Bits.

I was gonna newtype that, but it's throwing all kinds of crazy errors again, so I was just gonna wing it with Bits.

What I would really like to do is define a Mask type of Bits and a Step type of Bits, then combine them into a Lfsr tuple type.

The reason I want to do this is to catch myself putting Mask into Step or something awful. That /would/ catch me, right?.

I'm not 100% certain of your intentions, I'm a bit confused, so I don't know if my answer will make sense to you. Bits is not a type, it is a type class. As far as I know, it is not possible to define a type which requires its constructor arguments to have types belonging to a certain class.

For example,

newtype Mask = Mask Bits
newtype Step = Step Bits

won't work since Bits is not a type. You actually want something like

newtype (Bits a) => Mask a = Mask a

i.e. "Mask parameterized in some type a that must be an instance of the class Bits", but this does not exist in Haskell. What you can do however, is this

newtype Mask a = Mask a
newtype Step a = Step a
newtype Lfsr a = Lfsr (Mask a, Step a)

This does not enforce that the type of the Mask and Step are instances of Byte, but it will help you make the distinction between masks and steps. Haskell will give an error message if you put a step in a mask spot, or vice versa.

For a PRNG, you only need a part of the state monad's functionality. You can imagine the PRNG as being an infinite list of random numbers. Every time you need a random number, you grab it from the front of this list. This is a more general and would allow you to use different approaches to generating random numbers. The monad would look like this (I believe a similar one already exists in Haskell's standard library):

data PRNG r a = PRNG { runPrng :: [r] -> (a, [r]) }
instance Monad (PRNG r) where
return x = PRNG $ \rs -> (x, rs)
PRNG f >>= g = PRNG $ \rs -> let (a, rs') = f rs in runPrng (g a) rs'
rand :: PRNG r r
----------------
rand = PRNG (\rs -> (head rs, tail rs))

So, a function needing a source of random numbers is one that takes a list of random numbers and returns some result of arbitrary type a and a remaining list of random numbers, i.e. [r] -> (a, [r]). Combining two such functions is done by giving the rest list returned by the first function to the second function (this is what >>= does).

We can define a dumb PRNG as follows:

withSillyPRNG :: PRNG Integer a -> a
------------------------------------
withSillyPRNG (PRNG f) = fst $ f [0..]

and use it as follows:

throwDie :: PRNG Integer Integer
--------------------------------
throwDie = do x <- rand
return $ x `mod` 6 + 1
throwDice :: Int -> PRNG Integer Integer
----------------------------------------
throwDice 0 = return 0
throwDice n = do x <- throwDie
y <- throwDice (n - 1)
return $ x + y
withSillyPRNG (throwDice 5)
15
generateList :: Int -> PRNG r [r]
---------------------------------
generateList 0 = return []
generateList n = do x <- rand
xs <- generateList (n - 1)
return $ x : xs
withSillyPRNG (generateList 10)
[0,1,2,3,4,5,6,7,8,9]

A PRNG based on your lfsr (probably not as you intend to make it, but hey, it seems to generate numbers)

withLFSR :: Bits r => r -> r -> PRNG r a -> a
---------------------------------------------
withLFSR seed mask (PRNG f) = fst $ f nums
where
nums = seed : map (lfsr seed) nums
withLFSR 1078 176 (generateList 10)
[1078,539,1339,1707,1891,1927,2037,1996,998,499]