On this page:
map
filter
foldr
foldl
build-list
andmap
ormap
quicksort
sort
apply
argmin
argmax
6.12

2.8 Higher order - funktiot

Nämä funktiot vaativat käyttöön Intermediate Student Language tai Advanced Student Language:n.

Jotta saat nämä funktiot käyttöösi vaihda kieleksi ISL tai ASL DrRacket:issa: Language->Choose language->Teaching languages->Intermediate/Advanced student. WeScheme:ssä funktiot toimivat automaattisesti.

procedure

(map f l ...)  lista<Z>

  f : (X ... -> Z)
  l : lista<X>
Tekee uuden listan käyttämällä funktiota f, jokaiseen alkioon joka on listassa l tai sitä seuraavissa listoissa.
(map f (list x-1 ... x-n)) = (list (f x-1) ... (f x-n))
(map f (list x-1 ... x-n) (list y-1 ... y-n)) = (list (f x-1 y-1) ... (f x-n y-n))
> (map add1 (list 3 -4 1/2))

'(4 -3 1.5)

> (map sub1 (list 3 -4 1/2))

'(2 -5 -0.5)

> ellipsit

(list image image image)

> (map (lambda (x) (rotate 45 x)) ellipsit)

(list image image image)

procedure

(filter p? l)  lista<X>

  p? : (X -> totuusarvo)
  l : lista<X>
Tekee uuden listan niistä listan l alkioita, joille pätee predikaatti p?.

> (filter odd? (list 0 1 2 3 4 5 6 7 8 9))

'(1 3 5 7 9)

> raja-arvo

3

> (filter (lambda (x) (>= x raja-arvo)) '(0 1 2 3 4 5 6 7 8 9))

'(3 4 5 6 7 8 9)

procedure

(foldr f pohja l ...)  Y

  f : (X ... Y -> Y)
  pohja : Y
  l : lista<X>
Ketjuttaa funktion f suorituksen niin, että sille ensin annetaan argumenteiksi pohja sekä listan l viimeinen alkio. Saatu paluuarvo sijoitetaan uudeksi pohja:ksi jne. Kun lista on käyty läpi palautettaan saatu arvo. pohja:n tyypin on oltava sama kuin funktion f paluuarvon.

(foldr f pohja (list x-1 ... x-n)) = (f x-1 ... (f x-n pohja))
(foldr f pohja (list x-1 ... x-n) (list y-1 ... y-n))
= (f x-1 y-1 ... (f x-n y-n pohja))
> (foldr + 0 (list 0 1 2 3 4 5 6 7 8 9))

45

> ellipsit

(list image image image)

> (foldr above empty-image ellipsit)

image

> (foldr (lambda (r kuva) (overlay (circle r "outline" "black") kuva))
         empty-image
         (list 5 10 15 20))

image

procedure

(foldl f pohja l)  Y

  f : (X Y -> Y)
  pohja : Y
  l : lista<X>
Ketjuttaa funktion f suorituksen niin, että sille ensin annetaan argumenteiksi pohja sekä listan l ensimmäinen alkio. Saatu paluuarvo sijoitetaan uudeksi pohja:ksi jne. Kun lista on käyty läpi palautettaan saatu arvo. pohja:n tyypin on oltava sama kuin funktion f paluuarvon.

(foldl f pohja (list x-1 ... x-n)) = (f x-n ... (f x-1 pohja))
(foldl f pohja (list x-1 ... x-n) (list x-1 ... x-n))
= (f x-n y-n ... (f x-1 y-1 pohja))
> (foldl - 100 (list 0 1 2 3 4 5 6 7 8 9))

105

> tähdet

(list image image image image)

> (foldl overlay empty-image tähdet)

image

procedure

(build-list n f)  lista<X>

  n : luonnollinen-luku
  f : (luonnollinen-luku -> X)
Tekee listan käyttämällä funktiota f lukuihin välillä 0 ja (- n 1).
(build-list n f) = (list (f 0) ... (f (- n 1)))
> (build-list 22 add1)

'(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22)

> i

3

> (build-list 3 (lambda (j) (+ j i)))

'(3 4 5)

> (build-list 10 (lambda (r)(star (+ 5 r)  "outline" "blue")))

(list image image image image image image image image image image)

procedure

(andmap p? [l])  totuusarvo

  p? : (X ... -> totuusarvo)
  l : lista<X> = ...
Tutkii onko predikaatin p? arvo tosi kaikille listan l alkioille.
(andmap p (list x-1 ... x-n)) = (and (p x-1) ... (p x-n))
(andmap p (list x-1 ... x-n) (list y-1 ... y-n)) = (and (p x-1 y-1) ... (p x-n y-n))
> (andmap odd? (list 1 3 5 7 9))

#true

> (andmap positive? (list 2 3 -2 1 0))

#false

> raja-arvo

3

> (andmap (lambda (x) (< x raja-arvo)) (list 0 1 2))

#true

procedure

(ormap p? l)  totuusarvo

  p? : (X -> totuusarvo)
  l : lista<X>
Tutkii onko predikaatin p? arvo tosi vähintään yhdelle listan l alkiolle.
(ormap p (list x-1 ... x-n)) = (or (p x-1) ... (p x-n))
(ormap p (list x-1 ... x-n) (list y-1 ... y-n)) = (or (p x-1 y-1) ... (p x-n y-n))
> (ormap odd? (list 1 3 5 7 9))

#true

> raja-arvo

3

> (ormap positive? (list 2 3 -2 1 0))

#true

> (ormap (lambda (x) (< x raja-arvo)) (list 6 7 8 1 5))

#true

procedure

(quicksort l vertailu)  lista<X>

  l : lista<X>
  vertailu : (X X -> totuusarvo)
Järjestää l:n alkiot vertailuoperaattorin vertailu mukaisesti (käyttää quicksort algorithmia).
> (quicksort (list 6 7 2 1 3 4 0 5 9 8) <)

'(0 1 2 3 4 5 6 7 8 9)

procedure

(sort l vertailu)  lista<X>

  l : lista<X>
  vertailu : (X X -> totuusarvo)
Järjestää l:n alkiot vertailuoperaattorin vertailu mukaisesti.
> (sort (list 6 7 2 1 3 4 0 5 9 8) <)

'(0 1 2 3 4 5 6 7 8 9)

procedure

(apply f l)  Y

  f : (X-1 ... X-N -> Y)
  l : (lista X-1 ... X-N)
Kutsuu funktiota listan l argumenteilla.
(apply f (list x-1 ... x-n)) = (f x-1 ... x-n)
> a-lista

'(0 1 2 3 4 5 6 7 8 9)

> (apply max a-lista)

9

> (apply + a-lista)

45

procedure

(argmin f l)  X

  f : (X -> reaaliluku)
  l : lista<X>
Etsii listan (ensimmäisen) alkion, joka minimoi annetun funktion paluuarvon.
> (argmin second (list (list "Väinö" 98) (list "Erkki" 78) (list "Heikki" 93)))

'("Erkki" 78)

procedure

(argmax f l)  X

  f : (X -> reaaliluku)
  l : lista<X>
Etsii listan (ensimmäisen) alkion, joka maksimoi annetun funktion paluuarvon.
> (argmax second (list (list "Väinö" 98) (list "Erkki" 78) (list "Heikki" 93)))

'("Väinö" 98)