import qualified Data.MemoCombinators as Memo -- memoizing a function remembers all earlier computed results -- also known as Dynamic Programming a114852 = closed 0 where closed = Memo.memo2 Memo.integral Memo.integral $ \k n -> -- counts number of closed lambda terms of size n within k nested lambdas 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 closed (k+1) (n-2) + -- only count lambda terms if qLam sum [closed k i * closed k (n-2-i) | i <- [0..n-2]] -- count applications main = print . map a114852 $ [0..]