## Lists

 home  Bib Algorithms Bioinfo FP Logic MML Prog.Lang and the mmlist

FP
Lambda
Introduction
Examples
pure λ
Lists
Trees
others

There are many useful Lambda Calculus functions that are commonly defined on lists.

To append two lists, L1 and L2, if L1 is empty return L2, otherwise the result is the first element of L1 (i.e. hd L1) followed by the result of appending the tail of L1 and all of L2 (i.e. append (tl L1) L2).

```append = lambda L1. lambda L2.
if null L1 then L2
else (hd L1) :: (append (tl L1) L2)

```

Zip takes two lists and returns a list of pairs.

```zip = lambda L1. lambda L2.
if null L1 or null L2 then nil
else (pair hd L1 hd L2)::(zip tl L1 tl L2)

```

This version of merge allows duplicate entries that are common to L1 and L2; it is assumed that L1 and L2 are sorted in which case the result is sorted.

```merge = lambda L1. lambda L2.
if null L1 then L2
else if null L2 then L1
else { neither L1 nor L2 is null }
if hd L1 < hd L2 then
hd L1 :: merge tl L1 L2
else { NB. duplicates allowed }
hd L2 :: merge L1 tl L2

```

The slow version of reverse takes O(|L|2)-time. This is because append L1 L2 takes O(|L1|)-time, and reverseS calls append |L|-times.

```reverseS = lambda L.  { O(|L|**2)-time }
if null L then nil
else append (reverseS tl L) (hd L :: nil)

```

The fast version of reverse takes O(|L|)-time by using an accumulating output parameter.

```reverse = lambda L.
let rec rev = lambda inp. lambda op.
{ op is an `accumulating parameter' }
if null inp then op
else rev (tl inp) ((hd inp)::op)
{ inp shrinks   op grows  }
in rev L nil

```

Filter builds a sublist of those elements of a list, L, that satisfy a predicate (test, truth function), p.

```filter = lambda p. lambda L.
{ those elements of L that satisfy p }
if null L then nil
else let hdL = hd L in
if p hdL then hdL::(filter p tl L)
else filter p tl L

```

Map applies a function, f, to every element of a list L. Map is also known as apply-to-all.

```map = lambda f. lambda L.
{ [f L1, f L2, ..., f Ln] }
if null L then nil
else (f hd L)::(map f tl L)

```

Foldl, fold-left, applies a binary operator, f, in a left-associative way, to all the elements of a list L, e.g. foldl times 1 (2::3::4::nil) = ((1×2)×3)×4.

```foldl = lambda f. lambda z. lambda L.
{ f( ... (f (f z L1) L2) ...) Ln }
let rec ff = lambda inp. lambda ans.
if null inp then ans
else ff tl inp (f ans hd inp)
in ff L z

```

Foldr, fold-right, applies a binary operator, f, in a right-associative way, to all the elements of a list L.

```foldr = lambda f. lambda z. lambda L.
{ f L1 (f L2 ( ... (f Ln z) ) ) }
let rec ff = lambda L.
if null L then z
else f hd L (ff tl L)
in ff L

```

(The list data structure is either built-in, or can be easily defined, in most programming languages that are based on the λ-calculus. However, lists can be defined, from scratch, in the pure λ-calculus.)

The following form exercises the above functions; change the final expression and experiment.

window on the wide world:
 The Darwin Awards V: Next Evolution

 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 Tuesday, 20-Aug-2019 10:44:51 AEST.