A type for prime numbers
Unfortunately, it's not safe. That's due to the records. If I know any Prime, I can construct a new Prime:

import Data.Numbers.Primes.Type

example :: Prime -&gt; Prime
example p = p {getIndex = 0, getValue = 0} -- whoops


So you want to get rid of the records in your type and write the getters by hand:

data Prime int = Prime int Int

getValue :: Prime int -&gt; int
getValue (Prime v _) = v

getIndex :: Prime int -&gt; Int
getIndex (Prime _ idx) = idx


Alternatively rename them, rebind them and don't export the record selectors:

data Prime int = Prime { _getIndex :: Int, _getValue int }

getValue :: Prime n -&gt; n
getValue = _getValue

getIndex :: Prime n -&gt; Int
getIndex = _getIndex


Also, you can improve maybePrime:

maybePrime :: Integral n =&gt; n -&gt; Maybe (Prime n)
maybePrime x = Prime x &lt;$&gt; primeIndex x


Either x is prime and primeIndex returns Just idx, or it isn't. There is no need to check x twice. maybePrime is usually called a "smart constructor", by the way.


  Am I dealing with index type the right way? 


That depends on your use-case. If you need the index of the Prime often, it makes sense to cache it. If you don't need the index often, don't. You could provide an IndexedPrime that always contains the Index, though:

type Index = Int
data IndexedPrime int = IndexedPrime Index int

newtype Prime int     = Prime int


You could split those into separate modules, but that's a matter of personal preference.


  Is an Int the right type for storing indices of primes, in the light of the facts that no prime has a negative index and there is a type Word for bounded unsigned integer values?


That's a good question. The answer is: yes, Int is a right type, but it's not the right type. Most of the time, you want to use the result of getIndex in some operation that wants an Int, not a Word, just like you want to use take (a - b). Note that I said that Int is a correct type. You can of course use Word.


  Is it good to use fromIntegral everywhere to make the types of the functions that deal with indices more general?


It can lead to interesting behaviour. For example, I can use

exampleInput :: Int
exampleInput = 13^9 + 33 + 13 -- yes, that's a prime. found by lucky guess :)

exampleOutput :: Maybe (Prime Word8)
exampleOutput = maybePrime exampleInput

-- exampleOutput = Just (Prime {getValue = 195, getIndex = 333})


That's why I changed maybePrime's type, to ensure that the conversion has to be explicit by the user before they apply maybePrime.

Overall, good ideas and implementation, but try to keep the fromIntegral parts in your own code to a minimum. By the way, if you're interested in predicative types, have a look at Liquid Haskell.