import qualified Data.MemoCombinators as Memo -- memoizing a function remembers all earlier computed results -- and thus is a form of Dynamic Programming a195691 = normal True 0 where normal = Memo.memo3 Memo.bool Memo.integral Memo.integral $ \qLam k n -> -- counts number of normal form closed lambda terms of size n within k nested lambdas -- avoid redexes by not allowing the first term in an application to be a lambda term if n<2 then 0 else -- no code shorter than 2 bits (if n-2<k then 1 else 0) + -- encode variable index n-1 in n bits (if qLam then normal True (k+1) (n-2) else 0) + -- only count lambda terms if qLam sum [normal False k i * normal True k (n-2-i) | i <- [0..n-2]] -- count applications main = print . map a195691 $ [0..]