Funktionalprogrammering.sagews

Funktionalprogrammering

Att applicera en funktion på samtliga elemenr i en lista kan implementeras t.ex. med iteration eller funktionalprogrammering. Vi ska här introducera den senare metoden.

L = [randint(0, 1000) for k in [1..10]]
L

[83, 237, 234, 406, 620, 948, 798, 296, 581, 59]

Antag att vi har en lista $$L = \{a_0, a_1, \ldots, a_n\}$$ och vi vill bestämma listan $$f(L) = \{f(a_0), f(a_1), \ldots, f(a_n)\}$$ där $f$ är en funktion. Det åstadkommer vi genom att skriva map(f, L).

map(is_odd, L)  # avgör vilka element i listan som är udda

[True, True, False, False, False, False, False, False, True, True]

Notera att listan är oförändrad.

L

[760, 916, 807, 148, 444, 196, 900, 823, 286, 711]

Imperativ programmering är klumpigare.

ny_L = []
for k in range(len(L)) :
    x = L[k]
    y = is_odd(x)
    ny_L.append(y)
ny_L

[True, True, False, False, False, False, False, False, True, True]

Applicera Eulers fi-funktion på varje element i listan.

map(euler_phi, L)

[82, 156, 72, 168, 240, 312, 216, 144, 492, 58]

För att t.ex. applicera funktionen $f(x) = x^2 - 3x$ på varje element $x$ i listan kan vi använda en anonym funktion.

map(lambda x : x^2 - 3*x, L)

[6640, 55458, 54054, 163618, 382540, 895860, 634410, 86728, 335818, 3304]

Motsvarande kod där man använder iteration skulle kunna ha följande form.

# Alternativ 1
# Nackdel: extra temporär lista behövs
L_tmp = []
for x in L :
    L_tmp.append(x^2 - 3*x)
L_tmp

[6640, 55458, 54054, 163618, 382540, 895860, 634410, 86728, 335818, 3304]

# Alternativ 2 (väldigt lik funktionalprorgammering)
[x^2 - 3*x for x in L]

[6640, 55458, 54054, 163618, 382540, 895860, 634410, 86728, 335818, 3304]

Man kan kombinera flera listor.

L1 = [1, 2, 3, 4]
L2 = ['a', 'b', 'c', 'd']
map(None, L1, L2)  # funktionen None gör inget

[(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')]

Vi ser att första elementen i båda listorna kombineras till ett par, likaså andra, tredje och fjärde elementen i respektive listan paras ihop. Med en anonym funktion med två variabler i sitt argument kan vi evaluera dessa par.

map(lambda x, y : x * y, L1, L2)  # t.ex.: 3 * 'c' = 'ccc'

['a', 'bb', 'ccc', 'dddd']

Med funktionen filter kan man plocka bort de element som inte uppfyller ett visst villkor. I koden nedan behåller vi de element $x$ i listan som uppfyller $\sqrt{x} [removed]

filter(lambda x : sqrt(x) < 20, L)

[83, 237, 234, 296, 59]

Antag att vi har en binär operator $*$ och en lista $[a_0, a_1, \ldots, a_n]$ och vill beräkna $a_0 * a_1 * \dots * a_n$. Det kan vi lösa med funktionen reduce.

L = [1, 2, 3, 4]
reduce(lambda x, y : x^2 * y, L)

576

I ovanstående exmepel är $x * y = x^2y$ och vi beräknar således $((1^2 \cdot 2)^2 \cdot 3)^2 \cdot 4$.

Funktionen zip kombinerar listor på liknande sätt som i exemplet ovan med flera listor i map.

zip(L1, L2)

[(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')]

L3 = map(is_even, L1)
zip(L1, L2, L3)

[(1, 'a', False), (2, 'b', True), (3, 'c', False), (4, 'd', True)]

L = range(2, 11)  # heltalen 2, 3, ..., 10
P = zip(L, map(is_prime, L))  # avgör vilka element som är primtal
P

[(2, True), (3, True), (4, False), (5, True), (6, False), (7, True), (8, False), (9, False), (10, False)]

filter(lambda x : x[1], P)  # behåll primtalen

[(2, True), (3, True), (5, True), (7, True)]

Även existenskvantifikatorn och allkvantifikatorn finns implementerade i Sage/Python.

L = [random() for k in [1..20]]  # tjugo slumptal mellan 0 och 1

Finns det något element i L som är mindre än 0.1?

any(map(lambda x : x < 0.1, L))

True

Är alla element mindre än 0.5?

all(map(lambda x : x < 0.5, L))

False