Wolfram Language Paclet Repository
Community-contributed installable additions to the Wolfram Language
Wolfram`Lambda`
EnumerateSizeLambdas  |
|
| | ||||
|
| | ||||
Examples
(1)
Basic Examples
(1)
In[1]:=
 | EnumerateSizeLambdas |
Out[1]=
{λ.[λ.[λ.[λ.[1]]]],λ.[λ.[λ.[λ.[2]]]],λ.[λ.[λ.[λ.[3]]]],λ.[λ.[λ.[λ.[4]]]],λ.[λ.[λ.[1[1]]]],λ.[λ.[λ.[1[2]]]],λ.[λ.[λ.[1[3]]]],λ.[λ.[λ.[2[1]]]],λ.[λ.[λ.[2[2]]]],λ.[λ.[λ.[2[3]]]],λ.[λ.[λ.[3[1]]]],λ.[λ.[λ.[3[2]]]],λ.[λ.[λ.[3[3]]]],λ.[λ.[λ.[1][1]]],λ.[λ.[λ.[1][2]]],λ.[λ.[λ.[2][1]]],λ.[λ.[λ.[2][2]]],λ.[λ.[λ.[3][1]]],λ.[λ.[λ.[3][2]]],λ.[λ.[1[λ.[1]]]],λ.[λ.[1[λ.[2]]]],λ.[λ.[1[λ.[3]]]],λ.[λ.[2[λ.[1]]]],λ.[λ.[2[λ.[2]]]],λ.[λ.[2[λ.[3]]]],λ.[λ.[1[1][1]]],λ.[λ.[1[1[1]]]],λ.[λ.[1[1][2]]],λ.[λ.[1[1[2]]]],λ.[λ.[1[2][1]]],λ.[λ.[1[2[1]]]],λ.[λ.[1[2][2]]],λ.[λ.[1[2[2]]]],λ.[λ.[2[1][1]]],λ.[λ.[2[1[1]]]],λ.[λ.[2[1][2]]],λ.[λ.[2[1[2]]]],λ.[λ.[2[2][1]]],λ.[λ.[2[2[1]]]],λ.[λ.[2[2][2]]],λ.[λ.[2[2[2]]]],λ.[λ.[λ.[1]][1]],λ.[λ.[λ.[2]][1]],λ.[λ.[λ.[3]][1]],λ.[λ.[1[1]][1]],λ.[λ.[1[2]][1]],λ.[λ.[2[1]][1]],λ.[λ.[2[2]][1]],λ.[1[λ.[λ.[1]]]],λ.[1[λ.[λ.[2]]]],λ.[1[λ.[λ.[3]]]],λ.[1[λ.[1[1]]]],λ.[1[λ.[1[2]]]],λ.[1[λ.[2[1]]]],λ.[1[λ.[2[2]]]],λ.[λ.[1][λ.[1]]],λ.[λ.[1][λ.[2]]],λ.[λ.[2][λ.[1]]],λ.[λ.[2][λ.[2]]],λ.[λ.[1][1][1]],λ.[λ.[1][1[1]]],λ.[λ.[2][1][1]],λ.[λ.[2][1[1]]],λ.[1[λ.[1]][1]],λ.[1[λ.[1][1]]],λ.[1[λ.[2]][1]],λ.[1[λ.[2][1]]],λ.[1[1][λ.[1]]],λ.[1[1[λ.[1]]]],λ.[1[1][λ.[2]]],λ.[1[1[λ.[2]]]],λ.[1[1][1][1]],λ.[1[1[1][1]]],λ.[1[1[1]][1]],λ.[1[1[1[1]]]],λ.[1[1][1[1]]],λ.[λ.[1]][λ.[1]],λ.[λ.[2]][λ.[1]],λ.[1[1]][λ.[1]],λ.[1][λ.[λ.[1]]],λ.[1][λ.[λ.[2]]],λ.[1][λ.[1[1]]]}
Number of closed lambda-terms of size n with size 0 for the variables:
In[2]:=
ResourceFunction["OEISSequence"]["A220894"]
Out[2]=
{0,1,3,14,82,579,4741,43977,454283,5159441,63782411,851368766,12188927818,186132043831,3017325884473,51712139570022,933654684562038,17702959714232057,351535449888420187,7292626296788508624,157698798590301690864,3547597554377118966359}
In[3]:=
TableLength@
[size],{size,8}
 | EnumerateSizeLambdas |
Out[3]=
{0,1,3,14,82,579,4741,43977}
The number of closed lambda calculus terms of size n, where size(lambda x.M)=2+size(M), size(M N)=2+size(M)+size(N), and size(V)=1+i for a variable V bound by the i-th enclosing lambda (corresponding to a binary encoding):
In[4]:=
ResourceFunction["OEISSequence"]["A114852"]
Out[4]=
{0,0,0,0,1,0,1,1,2,1,6,5,13,14,37,44,101,134,298,431,883,1361,2736,4405,8574,14334,27465,47146,89270,156360,293840,522913,978447,1761907,3288605,5977863,11148652,20414058,38071898,70125402,130880047}
In[5]:=
TableLength@
[size,2,2,1],{size,0,20}
| EnumerateSizeLambdas |
Out[5]=
{0,0,0,0,1,0,1,1,2,1,6,5,13,14,37,44,101,134,298,431,883}
 |
|
""