Lambda Calculus Example - Lists

home1 home2
and the


Lists and list operators are usually "built in" with programming languages based on Lambda Calculus but they can be defined in Lambda Calculus. The following example shows a way to define CONS, NIL, HD (head), TL (tail), NULL. (PRINT is a cheat because it is defined using the system's built-in lists (::), but it too could be defined in Lambda Calculus.)

let rec
 CONS = lambda h. lambda t. lambda f. f h t,

 NIL = lambda f. true,

 NULL = lambda L. L (lambda h. lambda t. false),

 HD = lambda L. L (lambda h. lambda t. h),

 TL = lambda L. L (lambda h. lambda t. t),

 PRINT = lambda L.
   if NULL L then '/' else (HD L)::(PRINT (TL L))

in let L = CONS 1 (CONS 2 (CONS 3 NIL)) {an e.g.}

in PRINT( CONS (NULL NIL)       {T}
        ( CONS (NULL L)         {F}
        ( CONS (HD L)           {1}
        ( CONS (HD (TL L))      {2}
        ( CONS (HD (TL (TL L))) {3}
          NIL)))))              {/}

{\fB Define (Flat) Lists From Scratch. \fP}

Also see [Boolean] and [Ints].

Coding Ockham's Razor, L. Allison, Springer

A Practical Introduction to Denotational Semantics, L. Allison, CUP

free op. sys.
free office suite
~ free photoshop
web browser

λ ...
:: list cons
nil the [ ] list
null  predicate
hd head (1st)
tl tail (rest)

© L. Allison   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Thursday, 25-Jul-2024 11:19:54 AEST.