Safety, sharing, and laziness
Hm, why did you write go as a separate function? It is - as you state - the same as recoveries, why the local definition?

For making it more succinct, I think it's easiest to have an intermediate data structure that carries both pieces of information you seek in the case: Whether there are enough digits and what number the digits so far would form.

The first data structure that comes to mind is a list of numbers - we just need to construct it. In this case, scanl is our friend:

import Data.List (scanl)
import Data.Char (digitToInt)

type Memoizable a = a -&gt; a

recoveries :: Int -&gt; Memoizable (String -&gt; Int)
recoveries _ _    ('0':_) = 0
recoveries _ _    []      = 1
recoveries m self ss      = result `rem` 0xfaceb00c
  where result = case tail (scanl addDigit 0 ss) of
          (_:_:c:_) | c &lt;= m  -&gt; aCase+bCase+cCase
          (_:b:_)   | b &lt;= m  -&gt; aCase+bCase
          (a:_)     | a &lt;= m  -&gt; aCase
          _                   -&gt; 0
        addDigit x c = x*10 + digitToInt c
        aCase = self (drop 1 ss)
        bCase = self (drop 2 ss)
        cCase = self (drop 3 ss)


Unless I've made a mistake (can't test), this should do the same as your code, and now we can write everything cleanly using pattern matches and a few guards on the intermediate list.

You could get rid of aCase, bCase and cCase as well if you would zip the result of scanl with tails ss. But while this is more general, I felt it would have made the code harder to understand, so I left it like this.