Count numbers whose digits are only increasing or decreasing

The goal is described here: basically, it is to compute the number of numbers below \$10^n\$ such that its digits are either increasing or decreasing (like 112 or 211, but not like 121).

The original version:

-- f computes the number of numbers with increasing digits.
-- digits >= k and the number of digits is n

f :: (Num t1, Num t, Eq t1, Eq t, Enum t) => t -> t1 -> t
f k 0 = 1
f k 1 = 10 - k
f 9 n = 1
f k n = foldl (\sum i -> sum + f i (n-1)) 0 $ enumFromTo k 9

-- h computes the number of numbers with decreasing digits.
-- digits  t -> t1 -> t
h k 0 = 1
h 0 n = 1
h k 1 = k + 1
h k n = foldl (\sum i -> sum + h i (n-1)) 0 $ enumFromTo 0 k

-- The main function is g

g :: (Num t1, Num t, Eq t1, Eq t, Enum t) => t1 -> t
g 0 = 1   
g 1 = 10
g n = g (n-1) + foldl (\sum i -> sum + g1 i (n-1)) 0 (enumFromTo 1 9)

-- g1 computes the number of numbers with either increasing or decreasing digits. 

g1 :: (Num t1, Num t, Eq t1, Eq t, Enum t) => t -> t1 -> t
g1 0 n = f 0 n -- only increasing
g1 9 n = h 9 n -- only decreasing
g1 k 0 = 1     -- necessary for recursion
g1 k n = g1 k (n-1) + s1 + s2
  where
  s1 = foldl (\sum i -> sum + f i (n-1)) 0 $ enumFromTo (k+1) 9
  s2 = foldl (\sum i -> sum + h i (n-1)) 0 $ enumFromTo 0 (k-1)

The problem is it is too slow, and basically g n needs two times of the time needed by g (n-1).

I think maybe I need to memorize the functions, but don't know how to achieve this. Perhaps a list of lists?

The version using a list of lists follows:

total n  = case n of
  0 -> 1
  _ -> foldl (\sum k -> (sum + incg k n + decg k n) - 1) 0 [1..9] + total (n - 1)

incg k n = incgs !! n !! k
decg k n = decgs !! n !! k

incgs :: [[Integer]]
incgs =  [] : take 10 (repeat 1) : rest
  where
  rest = map (reverse . scanl1 (+) . reverse) $ tail incgs

decgs :: [[Integer]]
decgs =  [] : take 10 (repeat 1) : rest
  where
  rest = map (scanl1 (+)) $ tail decgs

Here's a version of your list of lists version using list comprehension and no !! and no explicit recursion:

total 0 = 1
total n = sum
  [ sum (init decgn) + sum (tail decgn) - 9
  | decgn <- take n $ iterate (scanl1 (+)) $ replicate 10 1
  ] + 1

This can probably be reduced further because either of us introduced some unneeded numerical operation somewhere.

StackExchange Code Review Q#143388, answer score: 4