Wolfram/Lambda | Paclet Repository

Wolfram`Lambda`

EnumerateSizeLambdas

EnumerateSizeLambdas [size]
	return a list of all lambda terms with a given number of leaves.

EnumerateSizeLambdas [size,lambdaSize,appSize,varSize]
	specify how much each type of subterm contributes to the size.

Examples

(1)

Basic Examples

(1)

In[1]:=

EnumerateSizeLambdas

[5]

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]:=

TableLength@

EnumerateSizeLambdas

[size],{size,8}

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]:=

TableLength@

EnumerateSizeLambdas

[size,2,2,1],{size,0,20}

Out[5]=

{0,0,0,0,1,0,1,1,2,1,6,5,13,14,37,44,101,134,298,431,883}

RelatedGuides

▪

Guide

""