Question: I made a implementation of the KMP algorithm's fail table.

```
kmp s = b
    where a = listArray (0,length s-1) s
          b = 0:list 0 (tail s)
          list _ [] = [] 
          list n (x:xs) 
            | x==a!n    = (n+1):list (n+1) xs
            | n > 0     = list (b!!(n-1)) (x:xs)
            | otherwise = 0:list 0 xs

```

`b` is a list, and `b!!(n-1)` in the last line is slow, therefore I wish to speed it up and did the following.

```
kmp s = b
    where a = listArray (0,length s-1) s
          t = listArray (0,length s-1) b
          b = 0:list 0 (tail s)
          list _ [] = [] 
          list n (x:xs) 
            | x==a!n    = (n+1):list (n+1) xs
            | n > 0     = list (t!(n-1)) (x:xs)
            | otherwise = 0:list 0 xs

```

Note the only difference is to replace `b!!` by `t!` and declares `t` to be the array generated from `b`. 

For the same input, the original code have the correct output, but the new one just outputs `<<loop>>`.

How can one fix this problem?

Answer: 
Your problem is that the list `b` needs the array `t` to determine its structure (length). But the array `t` needs the length of the list before it exists:

```
listArray :: Ix i => (i,i) -> [e] -> Array i e
listArray (l,u) es = runST (ST $ \s1# ->
    case safeRangeSize (l,u)            of { n@(I# n#) ->
    case newArray# n# arrEleBottom s1#  of { (# s2#, marr# #) ->
    let fillFromList i# xs s3# | i# ==# n# = s3#
                               | otherwise = case xs of
            []   -> s3#
            y:ys -> case writeArray# marr# i# y s3# of { s4# ->
                    fillFromList (i# +# 1#) ys s4# } in
    case fillFromList 0# es s2#         of { s3# ->
    done l u n marr# s3# }}})

```

As you can see, first a raw array of appropriate size is allocated, then it is filled with `arrEleBottom` (which is an `error` call with message undefined array element), then the list is traversed and the list elements are written to the array (the list elements can refer to array values without problem). Then, finally, the array is frozen. Before the array is frozen, it cannot be accessed from outside the filling code (it's basically an `ST s` computation).

The simplest way to fix it is IMO to use a mutable array in an `ST s` monad,

```
kmp s = elems b
  where
    l = length s - 1
    a = listArray (0, l) s
    b = runSTArray $ do
           t <- newArray_ (0,l)
           writeArray t 0 0
           let fill _ _ [] = return t
               fill i n (x:xs)
                 | x == a!n = do
                        writeArray t i (n+1)
                        fill (i+1) (n+1) xs
                 | n > 0    = do
                        k <- readArray t (n-1)
                        fill i k (x:xs)
                 | otherwise = do
                        writeArray t i 0
                        fill (i+1) 0 xs
           fill 1 0 (tail s)

```

is a very direct (and a bit inefficient) translation of the code.
This doesn't directly answer your question, but gives a simpler fix than the proposed version using `STArray`s.

The imperative version of the algorithm translates directly into a version that doesn't use repeated list indexing or state, just lazy array construction:

```
import Data.Array.IArray

kmp :: String -> Array Int Int
kmp s = b
  where
    a :: Array Int Char
    a = listArray (0,l-1) s
    b = listArray (1,l) (0:map (\q -> f (b!(q-1)) q) [2..l])
    f k q
      | k > 0 && (a ! k) /= (a ! (q-1)) =
        f (b ! k) q
      | a ! k == a ! (q-1) = k + 1
      | otherwise = k
    l = length s

```

However, I haven't benchmarked this.