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 &gt;= k and the number of digits is n

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

-- h computes the number of numbers with decreasing digits.
-- digits &lt;= k and the number of digits is n

h :: (Num t1, Num t, Eq t1, Eq t, Enum t) =&gt; t -&gt; t1 -&gt; t
h k 0 = 1
h 0 n = 1
h k 1 = k + 1
h k n = foldl (\sum i -&gt; 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) =&gt; t1 -&gt; t
g 0 = 1   
g 1 = 10
g n = g (n-1) + foldl (\sum i -&gt; 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) =&gt; t -&gt; t1 -&gt; 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 -&gt; sum + f i (n-1)) 0 $ enumFromTo (k+1) 9
  s2 = foldl (\sum i -&gt; 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 -&gt; 1
  _ -&gt; foldl (\sum k -&gt; (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 &lt;- take n $ iterate (scanl1 (+)) $ replicate 10 1
  ] + 1


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