Lambda Calculus Example - Lists

LA home
Computing
 Algorithms
 Bioinformatics
 FP,  λ
 Logic,  π
 MML
 Prog.Langs

FP
 Lambda
  Introduction
  Examples
   Bool
   Ints
   Lists
  others

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

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite,
ver 3.4+

The GIMP
~ free photoshop
Firefox
web browser
FlashBlock
like it says!

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

© L. Allison   http://www.allisons.org/ll/   (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, 25-Oct-2014 05:50:05 EST.