HOWTO om funktionell programmering

Författare:

A. M. Kuchling

Release:

0.32

I det här dokumentet tar vi en rundtur i Pythons funktioner som lämpar sig för att implementera program i en funktionell stil. Efter en introduktion till begreppen funktionell programmering tittar vi på språkfunktioner som iterator och generator samt relevanta biblioteksmoduler som itertools och functools.

Introduktion

Detta avsnitt förklarar det grundläggande konceptet för funktionell programmering; om du bara är intresserad av att lära dig om Python-språkets funktioner, hoppa till nästa avsnitt om Iteratorer.

Programmeringsspråk stöder nedbrytning av problem på flera olika sätt:

  • De flesta programmeringsspråk är procedurspråk: program är listor med instruktioner som talar om för datorn vad den ska göra med programmets indata. C, Pascal och till och med Unix-shell är procedurspråk.

  • I deklarativa språk skriver du en specifikation som beskriver problemet som ska lösas, och språkets implementation räknar ut hur beräkningen ska utföras på ett effektivt sätt. SQL är det deklarativa språk som du troligen känner till; en SQL-fråga beskriver den datamängd som du vill hämta, och SQL-motorn avgör om tabeller ska skannas eller index användas, vilka subklausuler som ska utföras först osv.

  • Objektorienterade program manipulerar samlingar av objekt. Objekt har ett internt tillstånd och stödjer metoder som på något sätt frågar efter eller ändrar detta interna tillstånd. Smalltalk och Java är objektorienterade språk. C++ och Python är språk som stöder objektorienterad programmering, men som inte tvingar fram användning av objektorienterade funktioner.

  • i *funktionell* programmering bryts ett problem ned till en uppsättning funktioner. I idealfallet tar funktioner bara emot indata och producerar utdata, och har inget internt tillstånd som påverkar den utdata som produceras för en given indata. Välkända funktionella språk är bland annat ML-familjen (Standard ML, OCaml och andra varianter) och Haskell.

Konstruktörerna av vissa datorspråk väljer att betona ett visst sätt att programmera. Detta gör det ofta svårt att skriva program som använder ett annat synsätt. Andra språk är multiparadigmspråk som stödjer flera olika synsätt. Lisp, C++ och Python är multiparadigmspråk; du kan skriva program eller bibliotek som till stor del är procedurella, objektorienterade eller funktionella i alla dessa språk. I ett stort program kan olika delar skrivas med olika metoder; GUI:t kan till exempel vara objektorienterat medan bearbetningslogiken är procedurell eller funktionell.

I ett funktionellt program flödar indata genom en uppsättning funktioner. Varje funktion bearbetar sin indata och producerar en viss utdata. Funktionell stil avråder från funktioner med sidoeffekter som ändrar internt tillstånd eller gör andra ändringar som inte syns i funktionens returvärde. Funktioner som inte har några bieffekter alls kallas rent funktionella. Att undvika bieffekter innebär att man inte använder datastrukturer som uppdateras under programmets gång, utan varje funktions utdata får bara bero på dess indata.

Vissa språk är mycket strikta när det gäller renhet och har inte ens assignment statements som a=3 eller c = a + b, men det är svårt att undvika alla bieffekter, till exempel att skriva ut på skärmen eller skriva till en diskfil. Ett annat exempel är ett anrop till funktionen print() eller time.sleep(), som inte ger något användbart värde. Båda anropas endast för sina bieffekter, som att skicka lite text till skärmen eller pausa exekveringen i en sekund.

Python-program skrivna i funktionell stil går vanligtvis inte till ytterligheten att undvika alla I/O eller alla tilldelningar; istället tillhandahåller de ett gränssnitt som ser funktionellt ut men använder icke-funktionella funktioner internt. Till exempel kommer implementeringen av en funktion fortfarande att använda tilldelningar till lokala variabler, men kommer inte att ändra globala variabler eller ha andra biverkningar.

Funktionell programmering kan ses som motsatsen till objektorienterad programmering. Objekt är små kapslar som innehåller ett internt tillstånd tillsammans med en samling metodanrop som låter dig ändra detta tillstånd, och program består av att göra rätt uppsättning tillståndsändringar. Funktionell programmering vill undvika tillståndsändringar så mycket som möjligt och arbetar med dataflöden mellan funktioner. I Python kan du kombinera de två metoderna genom att skriva funktioner som tar och returnerar instanser som representerar objekt i din applikation (e-postmeddelanden, transaktioner etc.).

Funktionell design kan verka som en märklig begränsning att arbeta under. Varför ska man undvika objekt och bieffekter? Det finns teoretiska och praktiska fördelar med den funktionella stilen:

  • Formell bevisbarhet.

  • Modularitet.

  • Komponerbarhet.

  • Enkel felsökning och testning.

Formell bevisbarhet

En teoretisk fördel är att det är lättare att konstruera ett matematiskt bevis för att ett funktionellt program är korrekt.

Under lång tid har forskare varit intresserade av att hitta sätt att matematiskt bevisa att program är korrekta. Detta skiljer sig från att testa ett program på många olika indata och dra slutsatsen att dess utdata vanligtvis är korrekt, eller att läsa ett programs källkod och dra slutsatsen att koden ser rätt ut; målet är istället ett rigoröst bevis för att ett program ger rätt resultat för alla möjliga indata.

Den teknik som används för att bevisa att program är korrekta är att skriva ner invarianter, egenskaper hos indata och hos programmets variabler som alltid är sanna. För varje kodrad visar man sedan att om invarianterna X och Y är sanna innan raden körs, så är de något annorlunda invarianterna X’ och Y’ sanna efter raden körs. Detta fortsätter tills du når slutet av programmet, då invarianterna ska matcha de önskade villkoren på programmets utdata.

Att funktionell programmering undviker tilldelningar beror på att tilldelningar är svåra att hantera med denna teknik; tilldelningar kan bryta invarianter som var sanna före tilldelningen utan att producera några nya invarianter som kan spridas vidare.

Att bevisa att program är korrekta är tyvärr till stor del opraktiskt och inte relevant för Python-programvara. Även triviala program kräver bevis som är flera sidor långa; korrekthetsbeviset för ett måttligt komplicerat program skulle vara enormt, och få eller inga av de program du använder dagligen (Python-tolken, din XML-parser, din webbläsare) kan bevisas vara korrekta. Även om du skrev ner eller genererade ett bevis, skulle det då vara frågan om att verifiera beviset; kanske finns det ett fel i det, och du tror felaktigt att du har bevisat att programmet är korrekt.

Modularitet

En mer praktisk fördel med funktionell programmering är att den tvingar dig att dela upp ditt problem i små bitar. Program är mer modulära som ett resultat. Det är lättare att specificera och skriva en liten funktion som gör en sak än en stor funktion som utför en komplicerad transformation. Små funktioner är också lättare att läsa och att kontrollera om det finns fel.

Enkel felsökning och testning

Det är enklare att testa och felsöka ett program med funktionell stil.

Felsökningen förenklas av att funktionerna i allmänhet är små och tydligt specificerade. När ett program inte fungerar är varje funktion en gränssnittspunkt där du kan kontrollera att data är korrekta. Du kan titta på de mellanliggande in- och utmatningarna för att snabbt isolera den funktion som är ansvarig för en bugg.

Testning är enklare eftersom varje funktion är ett potentiellt objekt för ett enhetstest. Funktionerna är inte beroende av systemtillstånd som måste replikeras innan ett test körs, utan man behöver bara syntetisera rätt indata och sedan kontrollera att utdata motsvarar förväntningarna.

Komposabilitet

När du arbetar med ett funktionellt program kommer du att skriva ett antal funktioner med varierande in- och utgångar. Vissa av dessa funktioner kommer oundvikligen att vara specialiserade för en viss applikation, men andra kommer att vara användbara i en mängd olika program. Till exempel kan en funktion som tar en katalogsökväg och returnerar alla XML-filer i katalogen, eller en funktion som tar ett filnamn och returnerar dess innehåll, användas i många olika situationer.

Med tiden kommer du att skapa ett personligt bibliotek med verktyg. Ofta sätter du ihop nya program genom att ordna befintliga funktioner i en ny konfiguration och skriva några funktioner som är specialiserade för den aktuella uppgiften.

Iteratorer

Jag ska börja med att titta på en funktion i Python-språket som är en viktig grund för att skriva program i funktionell stil: iteratorer.

En iterator är ett objekt som representerar en ström av data; detta objekt returnerar data ett element i taget. En iterator i Python måste stödja en metod som heter __next__() som inte tar några argument och alltid returnerar nästa element i strömmen. Om det inte finns några fler element i flödet måste __next__() ge upphov till undantaget StopIteration. Iteratorer behöver dock inte vara ändliga; det är helt rimligt att skriva en iterator som producerar en oändlig ström av data.

Den inbyggda funktionen iter() tar ett godtyckligt objekt och försöker returnera en iterator som returnerar objektets innehåll eller element, och ger upphov till TypeError om objektet inte stöder iteration. Flera av Pythons inbyggda datatyper stöder iteration, de vanligaste är listor och ordböcker. Ett objekt kallas iterable om du kan få en iterator för det.

Du kan experimentera med iterationsgränssnittet manuellt:

>>> L = [1, 2, 3]
>>> it = iter(L)
>>> it
<...iterator object at ...>
>>> it.__next__()  # same as next(it)
1
>>> next(it)
2
>>> next(it)
3
>>> next(it)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>>

Python förväntar sig itererbara objekt i flera olika sammanhang, varav det viktigaste är for-satsen. I uttalandet for X in Y måste Y vara en iterator eller något objekt för vilket iter() kan skapa en iterator. Dessa två satser är likvärdiga:

för i i iter(obj):
    print(i)

för i i obj:
    print(i)

Iteratorer kan materialiseras som listor eller tupler med hjälp av konstruktörsfunktionerna list() eller tuple():

>>> L = [1, 2, 3]
>>> iterator = iter(L)
>>> t = tuple(iterator)
>>> t
(1, 2, 3)

Uppackning av sekvenser stöder även iteratorer: om du vet att en iterator kommer att returnera N element kan du packa upp dem till en N-tupel:

>>> L = [1, 2, 3]
>>> iterator = iter(L)
>>> a, b, c = iterator
>>> a, b, c
(1, 2, 3)

Inbyggda funktioner som max() och min() kan ta ett enda iteratorargument och returnerar det största eller minsta elementet. Operatorerna "in" och "not in" stöder också iteratorer: X in iterator är sant om X finns i den ström som returneras av iteratorn. Du kommer att stöta på uppenbara problem om iteratorn är oändlig; max(), min() kommer aldrig att returnera, och om elementet X aldrig visas i strömmen kommer operatorerna "in" och "not in" inte heller att returnera.

Observera att du bara kan gå framåt i en iterator; det finns inget sätt att hämta föregående element, återställa iteratorn eller göra en kopia av den. Iteratorobjekt kan valfritt tillhandahålla dessa ytterligare funktioner, men iteratorprotokollet specificerar endast __next__()-metoden. Funktioner kan därför konsumera all iteratorns utdata, och om du behöver göra något annat med samma ström måste du skapa en ny iterator.

Datatyper som stöder iteratorer

Vi har redan sett hur listor och tupler stöder iteratorer. Faktum är att alla Python-sekvenstyper, till exempel strängar, automatiskt stöder skapandet av en iterator.

Om du anropar iter() på en ordbok returneras en iterator som loopar över ordbokens nycklar:

>>> m = {'Jan': 1, 'Feb': 2, 'Mar': 3, 'Apr': 4, 'May': 5, 'Jun': 6,
...      'Jul': 7, 'Aug': 8, 'Sep': 9, 'Oct': 10, 'Nov': 11, 'Dec': 12}
>>> for key in m:
...     print(key, m[key])
Jan 1
Feb 2
Mar 3
Apr 4
May 5
Jun 6
Jul 7
Aug 8
Sep 9
Oct 10
Nov 11
Dec 12

Observera att från och med Python 3.7 är ordbokens iterationsordning garanterad att vara densamma som insättningsordningen. I tidigare versioner var beteendet ospecificerat och kunde variera mellan olika implementeringar.

Om du använder iter() på en dictionary loopar du alltid över nycklarna, men dictionaries har metoder som returnerar andra iteratorer. Om du vill iterera över värden eller nyckel/värde-par kan du uttryckligen anropa metoderna values() eller items() för att få en lämplig iterator.

Konstruktören dict() kan acceptera en iterator som returnerar en ändlig ström av (key, value)-tupler:

>>> L = [('Italy', 'Rome'), ('France', 'Paris'), ('US', 'Washington DC')]
>>> dict(iter(L))
{'Italy': 'Rome', 'France': 'Paris', 'US': 'Washington DC'}

Filer stöder också iteration genom att anropa metoden readline() tills det inte finns några fler rader i filen. Detta innebär att du kan läsa varje rad i en fil så här:

för rad i filen:
    # gör något för varje rad
    ...

Uppsättningar kan ta sitt innehåll från en iterabel och låta dig iterera över uppsättningens element:

>>> S = {2, 3, 5, 7, 11, 13}
>>> for i in S:
...     print(i)
2
3
5
7
11
13

Generatoruttryck och listkomprehensioner

Två vanliga operationer på en iterators utdata är 1) att utföra någon operation för varje element, 2) att välja en delmängd av element som uppfyller något villkor. Om du till exempel har en lista med strängar kanske du vill ta bort efterföljande blanksteg från varje rad eller extrahera alla strängar som innehåller en viss delsträng.

Listkomprehensioner och generatoruttryck (kortform: ”listcomps” och ”genexps”) är en kortfattad notation för sådana operationer, som lånats från det funktionella programmeringsspråket Haskell (https://www.haskell.org/). Du kan ta bort alla blanksteg från en ström av strängar med följande kod:

>>> line_list = ['  line 1\n', 'line 2  \n', ' \n', '']

>>> # Generator expression -- returns iterator
>>> stripped_iter = (line.strip() for line in line_list)

>>> # List comprehension -- returns list
>>> stripped_list = [line.strip() for line in line_list]

Du kan välja endast vissa element genom att lägga till ett "if"-villkor:

>>> stripped_list = [line.strip() for line in line_list
...                  if line != ""]

Med en list comprehension får du tillbaka en Python-lista; stripped_list är en lista som innehåller de resulterande raderna, inte en iterator. Generatoruttryck returnerar en iterator som beräknar värdena efter behov, utan att behöva materialisera alla värden på en gång. Det innebär att listcomprehensions inte är användbara om du arbetar med iteratorer som returnerar en oändlig ström eller en mycket stor mängd data. Generatoruttryck är att föredra i dessa situationer.

Generatoruttryck omges av parenteser (”()”) och listkomprehensioner omges av hakparenteser (”[]”). Generatoruttryck har formen:

( uttryck för expr i sekvens1
             om villkor1
             för expr2 i sekvens2
             om villkor2
             för expr3 i sekvens3
             ...
             om villkor3
             för exprN i sekvensN
             om villkorN )

Även här är det bara de yttre hakparenteserna som är annorlunda (hakparenteser i stället för parenteser).

Elementen i den genererade utdata kommer att vara de på varandra följande värdena av expression. if -satserna är alla valfria; om de finns utvärderas expression endast och läggs till resultatet när condition är sant.

Generatoruttryck måste alltid skrivas inom parentes, men även de parenteser som signalerar ett funktionsanrop räknas. Om du vill skapa en iterator som omedelbart skickas till en funktion kan du skriva:

obj_total = sum(obj.count för obj i list_all_objects())

Klausulerna for...in innehåller de sekvenser som ska itereras över. Sekvenserna behöver inte vara lika långa, eftersom de itereras från vänster till höger, inte parallellt. För varje element i sequence1, loopas sequence2 från början. sequence3 loopas sedan över för varje resulterande par av element från sequence1 och sequence2.

För att uttrycka det på ett annat sätt är en listförståelse eller ett generatoruttryck likvärdigt med följande Python-kod:

för expr1 i sekvens1:
    if not (villkor1):
        continue # Hoppa över detta element
    för expr2 i sekvens2:
        if not (condition2):
            fortsätt # Hoppa över detta element
        ...
        för exprN i sekvensN:
            if not (conditionN):
                fortsätt # Hoppa över detta element

            # Skriv ut värdet av
            # uttrycket.

Det innebär att när det finns flera for...in -satser men inga if -satser, kommer längden på det resulterande resultatet att vara lika med produkten av längden på alla sekvenser. Om du har två listor med längden 3, kommer resultatlistan att innehålla 9 element:

>>> seq1 = 'abc'
>>> seq2 = (1, 2, 3)
>>> [(x, y) for x in seq1 for y in seq2]
[('a', 1), ('a', 2), ('a', 3),
 ('b', 1), ('b', 2), ('b', 3),
 ('c', 1), ('c', 2), ('c', 3)]

För att undvika att införa en tvetydighet i Pythons grammatik, om expression skapar en tupel, måste den omges av parenteser. Den första listförståelsen nedan är ett syntaxfel, medan den andra är korrekt:

# Syntaxfel
[x, y för x i seq1 för y i seq2]
# Korrekt
[(x, y) för x i seq1 för y i seq2]

Generatorer

Generatorer är en speciell klass av funktioner som förenklar arbetet med att skriva iteratorer. Vanliga funktioner beräknar ett värde och returnerar det, men generatorer returnerar en iterator som returnerar en ström av värden.

Du är säkert bekant med hur vanliga funktionsanrop fungerar i Python eller C. När du anropar en funktion får den ett privat namnrymd där dess lokala variabler skapas. När funktionen når ett return-slutsats förstörs de lokala variablerna och värdet returneras till anroparen. Ett senare anrop till samma funktion skapar ett nytt privat namnrymd och en ny uppsättning lokala variabler. Men tänk om de lokala variablerna inte kastades bort när en funktion avslutades? Tänk om du senare kunde återuppta funktionen där den slutade? Detta är vad generatorer tillhandahåller; de kan betraktas som återupptagbara funktioner.

Här är det enklaste exemplet på en generatorfunktion:

>>> def generate_ints(N):
...    for i in range(N):
...        yield i

Varje funktion som innehåller ett yield-nyckelord är en generatorfunktion; detta upptäcks av Pythons bytecode-kompilator som kompilerar funktionen speciellt som ett resultat.

När du anropar en generatorfunktion returnerar den inte ett enda värde, utan ett generatorobjekt som stöder iteratorprotokollet. När uttrycket yield exekveras returnerar generatorn värdet av i, på samma sätt som ett return-uttryck. Den stora skillnaden mellan yield och ett return-uttryck är att när yield nås avbryts generatorns exekveringstillstånd och lokala variabler bevaras. Vid nästa anrop till generatorns __next__()-metod återupptas funktionens exekvering.

Här är ett exempel på användning av generatorn generate_ints():

>>> gen = generate_ints(3)
>>> gen
<generator object generate_ints at ...>
>>> next(gen)
0
>>> next(gen)
1
>>> next(gen)
2
>>> next(gen)
Traceback (most recent call last):
  File "stdin", line 1, in <module>
  File "stdin", line 2, in generate_ints
StopIteration

Du skulle lika gärna kunna skriva for i in generate_ints(5), eller a, b, c = generate_ints(3).

I en generatorfunktion orsakar return value att StopIteration(value) utlöses från metoden __next__(). När detta händer, eller när botten av funktionen har nåtts, avslutas värdeprocesssionen och generatorn kan inte ge några ytterligare värden.

Du kan uppnå effekten av generatorer manuellt genom att skriva din egen klass och lagra alla lokala variabler i generatorn som instansvariabler. Att returnera en lista med heltal kan till exempel göras genom att sätta self.count till 0 och låta __next__()-metoden öka self.count och returnera den. Men för en måttligt komplicerad generator kan det vara mycket krångligare att skriva en motsvarande klass.

Testsviten som ingår i Pythons bibliotek, Lib/test/test_generators.py, innehåller ett antal mer intressanta exempel. Här är en generator som implementerar en ordnad traversal av ett träd med hjälp av generatorer rekursivt.

# En rekursiv generator som genererar trädblad i ordning.
def inorder(t):
    if t:
        för x i inorder(t.left):
            avkastning x

        yield t.etikett

        för x i inorder(t.right):
            avkastning x

Två andra exempel i test_generators.py producerar lösningar för N-Queens-problemet (placera N drottningar på ett NxN schackbräde så att ingen drottning hotar en annan) och Knight’s Tour (hitta en rutt som tar en riddare till varje ruta på ett NxN schackbräde utan att besöka någon ruta två gånger).

Överföra värden till en generator

I Python 2.4 och tidigare producerade generatorer bara utdata. När en generators kod anropades för att skapa en iterator fanns det inget sätt att skicka någon ny information till funktionen när dess exekvering återupptas. Du kan hacka ihop denna förmåga genom att få generatorn att titta på en global variabel eller genom att skicka in något mutabelt objekt som anroparna sedan ändrar, men dessa tillvägagångssätt är röriga.

I Python 2.5 finns det ett enkelt sätt att skicka värden till en generator. yield blev ett uttryck som returnerar ett värde som kan tilldelas en variabel eller på annat sätt bearbetas:

val = (avkastning i)

Jag rekommenderar att du alltid sätter parenteser runt ett yield-uttryck när du gör något med det returnerade värdet, som i exemplet ovan. Parenteserna är inte alltid nödvändiga, men det är lättare att alltid lägga till dem istället för att behöva komma ihåg när de behövs.

(PEP 342 förklarar de exakta reglerna, som är att ett yield-uttryck alltid måste stå inom parenteser utom när det förekommer i det högsta uttrycket på höger sida av en tilldelning. Det betyder att du kan skriva val = yield i men måste använda parenteser när det finns en operation, som i val = (yield i) + 12.)

Värden skickas till en generator genom att anropa dess metod send(value). Denna metod återupptar generatorns kod och uttrycket yield returnerar det angivna värdet. Om den vanliga metoden __next__() anropas returnerar yield None.

Här är en enkel räknare som ökar med 1 och gör det möjligt att ändra värdet på den interna räknaren.

def counter(maximum):
    i = 0
    while i < maximum:
        val = (avkastning i)
        # Om värde tillhandahålls, ändra räknaren
        om val inte är None:
            i = val
        i annat fall
            i += 1

Och här är ett exempel på hur man ändrar räknaren:

>>> it = counter(10)
>>> next(it)
0
>>> next(it)
1
>>> it.send(8)
8
>>> next(it)
9
>>> next(it)
Traceback (most recent call last):
  File "t.py", line 15, in <module>
    it.next()
StopIteration

Eftersom yield ofta kommer att returnera None, bör du alltid kontrollera för detta fall. Använd inte bara dess värde i uttryck om du inte är säker på att metoden send() kommer att vara den enda metod som används för att återuppta din generatorfunktion.

Förutom send() finns det två andra metoder för generatorer:

  • throw(value) används för att skapa ett undantag inuti generatorn; undantaget skapas av yield-uttrycket där generatorns exekvering pausas.

  • close() skickar ett GeneratorExit undantag till generatorn för att avsluta iterationen. Vid mottagandet av detta undantag måste generatorns kod antingen höja GeneratorExit eller StopIteration; att fånga undantaget och göra något annat är olagligt och kommer att utlösa ett RuntimeError. close() kommer också att anropas av Pythons skräpsamlare när generatorn är skräpsamlad.

    Om du behöver köra upprensningskod när en GeneratorExit inträffar föreslår jag att du använder en try: ... finally: svit istället för att fånga GeneratorExit.

Den sammantagna effekten av dessa förändringar är att generatorer förvandlas från enkelriktade producenter av information till både producenter och konsumenter.

Generatorer blir också coroutines, en mer generaliserad form av subrutiner. Subrutiner startas vid en punkt och avslutas vid en annan punkt (toppen av funktionen och ett return-svar), medan coroutines kan startas, avslutas och återupptas vid många olika punkter (yield-svar).

Inbyggda funktioner

Låt oss titta närmare på inbyggda funktioner som ofta används med iteratorer.

Två av Pythons inbyggda funktioner, map() och filter(), duplicerar funktionerna i generatoruttryck:

map(f, iterA, iterB, ...) returnerar en iterator över sekvensen

f(iterA[0], iterB[0]), f(iterA[1], iterB[1]), f(iterA[2], iterB[2]), ....

>>> def upper(s):
...     return s.upper()

>>> list(map(upper, ['sentence', 'fragment']))
['SENTENCE', 'FRAGMENT']
>>> [upper(s) for s in ['sentence', 'fragment']]
['SENTENCE', 'FRAGMENT']

Du kan naturligtvis uppnå samma effekt med en listförståelse.

filter(predicate, iter) returnerar en iterator över alla sekvenselement som uppfyller ett visst villkor, och dupliceras på liknande sätt av listförståelser. Ett predikat är en funktion som returnerar sanningsvärdet för ett visst villkor; för användning med filter() måste predikatet ta ett enda värde.

>>> def is_even(x):
...     return (x % 2) == 0

>>> list(filter(is_even, range(10)))
[0, 2, 4, 6, 8]

Detta kan också skrivas som en listförståelse:

>>> list(x for x in range(10) if is_even(x))
[0, 2, 4, 6, 8]

enumerate(iter, start=0) räknar bort elementen i iterabeln och returnerar 2-tuples som innehåller antalet (från start) och varje element.

>>> for item in enumerate(['subject', 'verb', 'object']):
...     print(item)
(0, 'subject')
(1, 'verb')
(2, 'object')

enumerate() används ofta när man loopar genom en lista och registrerar de index vid vilka vissa villkor är uppfyllda:

f = open('data.txt', 'r')
för i, rad i uppräkning(f):
    if line.strip() == '':
        print('Blank rad på rad #%i' % i)

sorted(iterable, key=None, reverse=False) samlar alla element i iterable i en lista, sorterar listan och returnerar det sorterade resultatet. Argumenten key och reverse skickas vidare till den konstruerade listans sort()-metod.

>>> import random
>>> # Generate 8 random numbers between [0, 10000)
>>> rand_list = random.sample(range(10000), 8)
>>> rand_list
[769, 7953, 9828, 6431, 8442, 9878, 6213, 2207]
>>> sorted(rand_list)
[769, 2207, 6213, 6431, 7953, 8442, 9828, 9878]
>>> sorted(rand_list, reverse=True)
[9878, 9828, 8442, 7953, 6431, 6213, 2207, 769]

(För en mer detaljerad diskussion om sortering, se Sorteringstekniker)

Inbyggnaderna any(iter) och all(iter) tittar på sanningsvärdena i en iterabels innehåll. any() returnerar True om något element i iterabeln är ett sant värde, och all() returnerar True om alla element är sanna värden:

>>> any([0, 1, 0])
True
>>> any([0, 0, 0])
False
>>> any([1, 1, 1])
True
>>> all([0, 1, 0])
False
>>> all([0, 0, 0])
False
>>> all([1, 1, 1])
True

zip(iterA, iterB, ...) tar ett element från varje iterabel och returnerar dem i en tupel:

zip(['a', 'b', 'c'], (1, 2, 3)) =>
  ('a', 1), ('b', 2), ('c', 3)

Den konstruerar inte en lista i minnet och tömmer inte alla inmatade iteratorer innan den returneras; istället konstrueras och returneras tupler endast om de begärs. (Den tekniska termen för detta beteende är lazy evaluation.)

Denna iterator är avsedd att användas med iterabler som alla har samma längd. Om iteratorerna är olika långa kommer den resulterande strömmen att vara lika lång som den kortaste iteratorn.

zip(['a', 'b'], (1, 2, 3)) =>
  ('a', 1), ('b', 2)

Du bör dock undvika att göra detta, eftersom ett element kan tas från de längre iteratorerna och kasseras. Detta innebär att du inte kan fortsätta att använda iteratorerna ytterligare eftersom du riskerar att hoppa över ett kasserat element.

Modulen itertools

Modulen itertools innehåller ett antal vanligt förekommande iteratorer samt funktioner för att kombinera flera iteratorer. Detta avsnitt introducerar modulens innehåll genom att visa små exempel.

Modulens funktioner kan delas in i ett par breda klasser:

  • Funktioner som skapar en ny iterator baserat på en befintlig iterator.

  • Funktioner för att behandla en iterators element som funktionsargument.

  • Funktioner för att välja ut delar av en iterators utdata.

  • En funktion för att gruppera en iterators utdata.

Skapa nya iteratorer

itertools.count(start, step) returnerar en oändlig ström av jämnt fördelade värden. Du kan välja att ange starttalet, som är 0 som standard, och intervallet mellan talen, som är 1: som standard:

itertools.count() =>
  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
itertools.count(10) =>
  10, 11, 12, 13, 14, 15, 16, 17, 18, 19, ...
itertools.count(10, 5) => 10, 15, 20, 25, ..
  10, 15, 20, 25, 30, 35, 40, 45, 50, 55, ...

itertools.cycle(iter) sparar en kopia av innehållet i en angiven iterabel och returnerar en ny iterator som returnerar dess element från första till sista. Den nya iteratorn kommer att upprepa dessa element i oändlighet.

itertools.cycle([1, 2, 3, 4, 5]) =>
  1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...

itertools.repeat(elem, [n]) returnerar det angivna elementet n gånger, eller returnerar elementet oändligt om n inte anges.

itertools.repeat('abc') =>
  abc, abc, abc, abc, abc, abc, abc, abc, abc, abc, abc, ...
itertools.repeat('abc', 5) =>
  abc, abc, abc, abc, abc

itertools.chain(iterA, iterB, ...) tar ett godtyckligt antal iteratorer som indata, och returnerar alla element i den första iteratorn, sedan alla element i den andra, och så vidare, tills alla iteratorer har uttömts.

itertools.chain(['a', 'b', 'c'], (1, 2, 3)) =>
  a, b, c, 1, 2, 3

itertools.islice(iter, [start], stop, [step]) returnerar en ström som är en del av iteratorn. Med ett enda stop-argument returneras de första stop-elementen. Om du anger ett startindex får du stop-start-element, och om du anger ett värde för step hoppas elementen över i enlighet med detta. Till skillnad från Pythons sträng- och listskärning kan du inte använda negativa värden för start, stop eller step:

itertools.islice(range(10), 8) =>
  0, 1, 2, 3, 4, 5, 6, 7
itertools.islice(intervall(10), 2, 8) => 2, 3, 4, 5, 6, 7
  2, 3, 4, 5, 6, 7
itertools.islice(intervall(10), 2, 8, 2) => 2
  2, 4, 6

itertools.tee(iter, [n]) replikerar en iterator; den returnerar n oberoende iteratorer som alla kommer att returnera innehållet i källiteratorn. Om du inte anger något värde för n är standardvärdet 2. Replikering av iteratorer kräver att en del av innehållet i källiteratorn sparas, så detta kan förbruka betydande minne om iteratorn är stor och en av de nya iteratorerna förbrukas mer än de andra.

itertools.tee( itertools.count() ) =>
   iterA, iterB

där iterA ->
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...

och iterB ->
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...

Anropa funktioner på element

Modulen operator innehåller en uppsättning funktioner som motsvarar Pythons operatorer. Några exempel är operator.add(a, b) (lägger till två värden), operator.ne(a, b) (samma som a != b), och operator.attrgetter('id') (returnerar en anropbar funktion som hämtar attributet .id).

itertools.starmap(func, iter) antar att iterable kommer att returnera en ström av tuples, och anropar func med dessa tuples som argument:

itertools.starmap(os.path.join,
                  [('/bin', 'python'), ('/usr', 'bin', 'java'),
                   ('/usr', 'bin', 'perl'), ('/usr', 'bin', 'ruby')])
=>
  /bin/python, /usr/bin/java, /usr/bin/perl, /usr/bin/ruby

Välja element

En annan grupp av funktioner väljer en delmängd av en iterators element baserat på ett predikat.

itertools.filterfalse(predicate, iter) är motsatsen till filter() och returnerar alla element för vilka predikatet returnerar false:

itertools.filterfalse(is_even, itertools.count()) =>
  1, 3, 5, 7, 9, 11, 13, 15, ...

itertools.takewhile(predicate, iter) returnerar element så länge som predikatet returnerar sant. När predikatet returnerar falskt kommer iteratorn att signalera slutet på sina resultat.

def less_than_10(x):
    returnera x < 10

itertools.takewhile(less_than_10, itertools.count()) =>
  0, 1, 2, 3, 4, 5, 6, 7, 8, 9

itertools.takewhile(är_jämn, itertools.count()) =>
  0

itertools.dropwhile(predicate, iter) kasserar element medan predikatet returnerar sant, och returnerar sedan resten av iterabelns resultat.

itertools.dropwhile(less_than_10, itertools.count()) =>
  10, 11, 12, 13, 14, 15, 16, 17, 18, 19, ...

itertools.dropwhile(är_jämn, itertools.count()) =>
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...

itertools.compress(data, selectors) tar två iteratorer och returnerar endast de element i data för vilka motsvarande element i selectors är sant, och stoppar när någon av dem är uttömd:

itertools.compress([1, 2, 3, 4, 5], [True, True, False, False, True]) =>
   1, 2, 5

Kombinatoriska funktioner

itertools.combinations(iterable, r) returnerar en iterator som ger alla möjliga r-tupelkombinationer av de element som ingår i iterable.

itertools.combinations([1, 2, 3, 4, 5], 2) => (1, 2, 3, (1, 4, 5)
  (1, 2), (1, 3), (1, 4), (1, 5),
  (2, 3), (2, 4), (2, 5),
  (3, 4), (3, 5),
  (4, 5)

itertools.combinations([1, 2, 3, 4, 5], 3) => (1, 2, 3)
  (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5),
  (2, 3, 4), (2, 3, 5), (2, 4, 5),
  (3, 4, 5)

Elementen i varje tupel kvarstår i samma ordning som iterable returnerade dem. Till exempel är siffran 1 alltid före 2, 3, 4 eller 5 i exemplen ovan. En liknande funktion, itertools.permutations(iterable, r=None), tar bort denna begränsning av ordningen och returnerar alla möjliga arrangemang av längden r:

itertools.permutationer([1, 2, 3, 4, 5], 2) =>
  (1, 2), (1, 3), (1, 4), (1, 5),
  (2, 1), (2, 3), (2, 4), (2, 5),
  (3, 1), (3, 2), (3, 4), (3, 5),
  (4, 1), (4, 2), (4, 3), (4, 5),
  (5, 1), (5, 2), (5, 3), (5, 4)

itertools.permutationer([1, 2, 3, 4, 5]) =>
  (1, 2, 3, 4, 5), (1, 2, 3, 5, 4), (1, 2, 4, 3, 5),
  ...
  (5, 4, 3, 2, 1)

Om du inte anger något värde för r används iterationens längd, vilket innebär att alla element permuteras.

Observera att dessa funktioner producerar alla möjliga kombinationer efter position och inte kräver att innehållet i iterable är unikt:

itertools.permutationer('aba', 3) =>
  ('a', 'b', 'a'), ('a', 'a', 'b'), ('b', 'a', 'a'),
  ('b', 'a', 'a'), ('a', 'a', 'b'), ('a', 'b', 'a')

Den identiska tupeln ('a', 'a', 'b') förekommer två gånger, men de två ’a’-strängarna kom från olika positioner.

Funktionen itertools.combinations_with_replacement(iterable, r) släpper på en annan begränsning: element kan upprepas inom en enda tupel. Konceptuellt väljs ett element för den första positionen i varje tupel och ersätts sedan innan det andra elementet väljs.

itertools.combinations_with_replacement([1, 2, 3, 4, 5], 2) => (1, 1, 2, 1, 3, 4, 5)
  (1, 1), (1, 2), (1, 3), (1, 4), (1, 5),
  (2, 2), (2, 3), (2, 4), (2, 5),
  (3, 3), (3, 4), (3, 5),
  (4, 4), (4, 5),
  (5, 5)

Gruppering av element

Den sista funktionen som jag ska diskutera, itertools.groupby(iter, key_func=None), är den mest komplicerade. key_func(elem) är en funktion som kan beräkna ett nyckelvärde för varje element som returneras av iterable. Om du inte anger någon nyckelfunktion är nyckeln helt enkelt varje element i sig.

groupby() samlar in alla på varandra följande element från den underliggande iterabeln som har samma nyckelvärde och returnerar en ström av 2-tuples som innehåller ett nyckelvärde och en iterator för elementen med den nyckeln.

city_list = [('Decatur', 'AL'), ('Huntsville', 'AL'), ('Selma', 'AL'),
             ('Anchorage', 'AK'), ('Nome', 'AK'),
             ('Flagstaff', 'AZ'), ('Phoenix', 'AZ'), ('Tucson', 'AZ'),
             ...
            ]

def get_state(city_state):
    returnera city_state[1]

itertools.groupby(city_list, get_state) =>
  ('AL', iterator-1),
  ('AK', iterator-2),
  ('AZ', iterator-3), ...

där
iterator-1 =>
  ('Decatur', 'AL'), ('Huntsville', 'AL'), ('Selma', 'AL')
iterator-2 => ('Anchor', 'AL')
  ('Anchorage', 'AK'), ('Nome', 'AK')
iterator-3 => ('Flagstaff', 'AK')
  ('Flagstaff', 'AZ'), ('Phoenix', 'AZ'), ('Tucson', 'AZ')

groupby() förutsätter att innehållet i den underliggande iterabeln redan är sorterat baserat på nyckeln. Observera att de returnerade iteratorerna också använder den underliggande iterabeln, så du måste konsumera resultaten av iterator-1 innan du begär iterator-2 och dess motsvarande nyckel.

Modulen functools

Modulen functools innehåller några funktioner av högre ordning. En högre ordningens funktion tar en eller flera funktioner som indata och returnerar en ny funktion. Det mest användbara verktyget i denna modul är funktionen functools.partial().

För program som är skrivna i en funktionell stil vill du ibland konstruera varianter av befintliga funktioner som har några av parametrarna ifyllda. Tänk på en Python-funktion f(a, b, c); du kanske vill skapa en ny funktion g(b, c) som är likvärdig med f(1, b, c); du fyller i ett värde för en av f():s parametrar. Detta kallas ”partiell funktionstillämpning”.

Konstruktorn för partial() tar argumenten (function, arg1, arg2, ..., kwarg1=value1, kwarg2=value2). Det resulterande objektet är anropsbart, så du kan bara anropa det för att anropa function med de ifyllda argumenten.

Här är ett litet men realistiskt exempel:

import functools

def log(message, subsystem):
    """Write the contents of 'message' to the specified subsystem."""
    print('%s: %s' % (subsystem, message))
    ...

server_log = functools.partial(log, subsystem='server')
server_log('Unable to open socket')

functools.reduce(func, iter, [initial_value]) utför en kumulativ operation på alla iterationens element och kan därför inte tillämpas på oändliga iterationer. func måste vara en funktion som tar två element och returnerar ett enda värde. functools.reduce() tar de två första elementen A och B som returneras av iteratorn och beräknar func(A, B). Den begär sedan det tredje elementet, C, beräknar func(func(A, B), C), kombinerar detta resultat med det fjärde elementet som returneras och fortsätter tills iteratorn är uttömd. Om iterabeln inte returnerar några värden alls, uppstår ett TypeError undantag. Om det initiala värdet anges används det som utgångspunkt och func(initial_value, A) är den första beräkningen.

>>> import operator, functools
>>> functools.reduce(operator.concat, ['A', 'BB', 'C'])
'ABBC'
>>> functools.reduce(operator.concat, [])
Traceback (most recent call last):
  ...
TypeError: reduce() of empty sequence with no initial value
>>> functools.reduce(operator.mul, [1, 2, 3], 1)
6
>>> functools.reduce(operator.mul, [], 1)
1

Om du använder operator.add() med functools.reduce() kommer du att lägga ihop alla element i iterabeln. Det här fallet är så vanligt att det finns en speciell inbyggd funktion som heter sum() för att beräkna det:

>>> import functools, operator
>>> functools.reduce(operator.add, [1, 2, 3, 4], 0)
10
>>> sum([1, 2, 3, 4])
10
>>> sum([])
0

För många användningar av functools.reduce() kan det dock vara tydligare att bara skriva den uppenbara for -loopen:

import functools
# Instead of:
product = functools.reduce(operator.mul, [1, 2, 3], 1)

# You can write:
product = 1
for i in [1, 2, 3]:
    product *= i

En relaterad funktion är itertools.accumulate(iterable, func=operator.add). Den utför samma beräkning, men istället för att bara returnera det slutliga resultatet returnerar accumulate() en iterator som också ger varje delresultat:

itertools.accumulate([1, 2, 3, 4, 5]) =>
  1, 3, 6, 10, 15

itertools.ackumulera([1, 2, 3, 4, 5], operator.mul) =>
  1, 2, 6, 24, 120

Operatormodulen

Modulen operator nämndes tidigare. Den innehåller en uppsättning funktioner som motsvarar Pythons operatorer. Dessa funktioner är ofta användbara i funktionell kod eftersom de gör att man slipper skriva triviala funktioner som utför en enda operation.

Några av funktionerna i denna modul är:

  • Matematiska operationer: add(), sub(), mul(), floordiv(), abs(), …

  • Logiska operationer: not_(), truth().

  • Bitvisa operationer: and_(), or_(), invert().

  • Jämförelser: eq(), ne(), lt(), le(), gt() och ge().

  • Objektets identitet: is_(), is_not().

Se operatormodulens dokumentation för en fullständig lista.

Små funktioner och lambda-uttrycket

När du skriver program i funktionell stil behöver du ofta små funktioner som fungerar som predikat eller som kombinerar element på något sätt.

Om det finns en inbyggd Python-funktion eller en modulfunktion som är lämplig behöver du inte definiera en ny funktion alls:

stripped_lines = [line.strip() för line i lines]
befintliga_filer = filter(os.path.exists, fil_lista)

Om den funktion du behöver inte finns, måste du skriva den. Ett sätt att skriva små funktioner är att använda uttrycket lambda. lambda tar ett antal parametrar och ett uttryck som kombinerar dessa parametrar, och skapar en anonym funktion som returnerar värdet av uttrycket:

adder = lambda x, y: x+y

print_assign = lambda name, value: name + '=' + str(value)

Ett alternativ är att bara använda def-satsen och definiera en funktion på vanligt sätt:

def adder(x, y):
    returnerar x + y

def print_assign(namn, värde):
    return namn + '=' + str(värde)

Vilket alternativ är att föredra? Det är en stilfråga; min vanliga kurs är att undvika att använda lambda.

En anledning till att jag föredrar detta är att lambda är ganska begränsat när det gäller vilka funktioner det kan definiera. Resultatet måste kunna beräknas som ett enda uttryck, vilket innebär att du inte kan ha flervägssammanställningar av if... elif... else eller try... except -satser. Om du försöker göra för mycket i en lambda-sats blir resultatet ett överdrivet komplicerat uttryck som är svårt att läsa. Snabbt, vad gör följande kod?

import functools
total = functools.reduce(lambda a, b: (0, a[1] + b[1]), items)[1]

Du kan räkna ut det, men det tar tid att reda ut uttrycket för att ta reda på vad som händer. Att använda en kort nästlad def-sats gör saker lite bättre:

import functools
def combine(a, b):
    return 0, a[1] + b[1]

total = functools.reduce(combine, items)[1]

Men det bästa av allt hade varit om jag helt enkelt hade använt en for-loop:

totalt = 0
för a, b i artiklar:
    total += b

Eller den inbyggda sum() och ett generatoruttryck:

total = sum(b for a, b in items)

Många användningar av functools.reduce() är tydligare när de skrivs som for-loopar.

Fredrik Lundh föreslog en gång följande uppsättning regler för refaktorisering av användningar av lambda:

  1. Skriv en lambda-funktion.

  2. Skriv en kommentar som förklarar vad sjutton den där lambdan gör.

  3. Studera kommentaren en stund och fundera ut ett namn som fångar essensen i kommentaren.

  4. Konvertera lambdan till en def-sats med det namnet.

  5. Ta bort kommentaren.

Jag gillar verkligen de här reglerna, men det är fritt fram att inte hålla med om huruvida den här lambda-fria stilen är bättre.

Revideringshistorik och erkännanden

Författaren vill tacka följande personer för förslag, korrigeringar och hjälp med olika utkast av denna artikel: Ian Bicking, Nick Coghlan, Nick Efford, Raymond Hettinger, Jim Jewett, Mike Krell, Leandro Lameiro, Jussi Salmela, Collin Winter, Blake Winton.

Version 0.1: publicerad den 30 juni 2006.

Version 0.11: publicerad den 1 juli 2006. Rättelser av stavfel.

Version 0.2: publicerad 10 juli 2006. Sammanslagna genexp- och listcomp-avsnitt till ett. Korrigeringar av stavfel.

Version 0.21: Lagt till fler referenser som föreslagits på tutor-mailinglistan.

Version 0.30: Lägger till ett avsnitt om den functional-modulen skriven av Collin Winter; lägger till ett kort avsnitt om operatormodulen; några andra redigeringar.

Referenser

Allmänt

Structure and Interpretation of Computer Programs, av Harold Abelson och Gerald Jay Sussman med Julie Sussman. Boken finns tillgänglig på https://mitpress.mit.edu/sicp. I denna klassiska lärobok i datavetenskap diskuteras i kapitlen 2 och 3 användningen av sekvenser och strömmar för att organisera dataflödet i ett program. Boken använder Scheme för sina exempel, men många av de designmetoder som beskrivs i dessa kapitel är tillämpliga på Python-kod i funktionell stil.

https://defmacro.org/2006/06/19/fp.html: En allmän introduktion till funktionell programmering som använder Java-exempel och har en lång historisk introduktion.

https://en.wikipedia.org/wiki/Functional_programming: Allmän Wikipedia-post som beskriver funktionell programmering.

https://en.wikipedia.org/wiki/Coroutine: Inlägg för coroutines.

https://en.wikipedia.org/wiki/Partial_application: Inlägg för begreppet partiell funktionstillämpning.

https://en.wikipedia.org/wiki/Currying: Inlägg för begreppet currying.

Python-specifik

https://gnosis.cx/TPiP/: I det första kapitlet i David Mertz bok Text Processing in Python diskuteras funktionell programmering för textbearbetning, i avsnittet ”Utilizing Higher-Order Functions in Text Processing”.

Mertz har också skrivit en artikelserie i tre delar om funktionell programmering för IBM:s DeveloperWorks-webbplats; se del 1, del 2 och del 3,

Python-dokumentation

Dokumentation för modulen itertools.

Dokumentation för modulen functools.

Dokumentation för modulen operator.

PEP 289: ”Generatoruttryck”

PEP 342: ”Coroutines via Enhanced Generators” beskriver de nya generatorfunktionerna i Python 2.5.