Lambda Calculus Example - Lists

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].

window on the wide world:

Computer Science Education Week

free op. sys.
free office suite,
ver 3.4+

~ free photoshop
web browser
like it says!

λ ...
:: 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 Saturday, 28-Nov-2020 07:23:53 AEDT.