Apa persamaan 'pythonic' dengan fungsi 'fold' dari pemrograman fungsional?

116

Apa cara paling idiomatis untuk mencapai sesuatu seperti berikut ini, di Haskell:

foldl (+) 0 [1,2,3,4,5]
--> 15

Atau yang setara di Ruby:

[1,2,3,4,5].inject(0) {|m,x| m + x}
#> 15

Jelas, Python menyediakan reducefungsi, yang merupakan implementasi dari lipatan, persis seperti di atas, namun, saya diberitahu bahwa cara pemrograman 'pythonic' adalah untuk menghindari lambdaistilah dan fungsi tingkat tinggi, lebih memilih pemahaman daftar jika memungkinkan. Oleh karena itu, apakah ada cara yang disukai untuk melipat daftar, atau struktur seperti daftar di Python yang bukan reducefungsinya, atau reducecara idiomatik untuk mencapai ini?

mistertim.dll
sumber
2
sumtidak cukup baik?
JBernardo
3
tidak yakin apakah ini contoh yang bagus untuk pertanyaan Anda. Ini dapat dengan mudah dicapai dengan sum, Anda mungkin ingin memberikan beberapa jenis contoh yang berbeda.
jamylak
14
Hai JBernardo - Menjumlahkan daftar angka dimaksudkan sebagai contoh yang agak merosot, saya lebih tertarik pada gagasan umum untuk mengumpulkan elemen daftar menggunakan beberapa operasi biner, dan nilai awal, bukan menjumlahkan bilangan bulat secara khusus.
mistertim
1
@mistertim: sum()sebenarnya menyediakan fungsionalitas terbatas dengan ini. sum([[a], [b, c, d], [e, f]], [])kembali [a, b, c, d, e, f]misalnya.
Joel Cornett
Meskipun kasus melakukannya dengan daftar adalah demonstrasi yang baik tentang hal-hal yang harus diperhatikan dengan teknik ini - +daftar adalah operasi waktu linier baik dalam waktu maupun memori, membuat seluruh panggilan menjadi kuadrat. Penggunaannya list(itertools.chain.from_iterable([a], [b,c,d],[e,f],[]])linier secara keseluruhan - dan jika Anda hanya perlu mengulanginya satu kali, Anda dapat menghentikan panggilan listuntuk membuatnya konstan dalam hal memori.
lvc

Jawaban:

115

Cara Pythonic untuk menjumlahkan sebuah array digunakan sum. Untuk tujuan lain, terkadang Anda dapat menggunakan beberapa kombinasi reduce(dari functoolsmodul) dan operatormodul, misalnya:

def product(xs):
    return reduce(operator.mul, xs, 1)

Sadarilah bahwa reducesebenarnya adalah foldl, dalam istilah Haskell. Tidak ada sintaks khusus untuk melakukan lipatan, tidak ada bawaan foldr, dan sebenarnya menggunakan reducedengan operator non-asosiatif dianggap gaya yang buruk.

Menggunakan fungsi tingkat tinggi cukup bersifat pythonic; itu memanfaatkan prinsip Python bahwa semuanya adalah objek, termasuk fungsi dan kelas. Anda benar bahwa lambda disukai oleh beberapa Pythonistas, tetapi sebagian besar karena mereka cenderung tidak terlalu mudah dibaca ketika menjadi kompleks.

Fred Foo
sumber
4
@ JBernardo: Anda mengatakan bahwa apa pun yang tidak ada di modul builtins tidak pythonic?
Fred Foo
4
Tidak, itu bodoh untuk dikatakan. Tapi beri saya satu alasan mengapa menurut Anda GvR akan sangat membenci fungsi pengurangan pada titik menghapusnya dari bawaan?
JBernardo
6
@JBernardo: karena orang mencoba memainkan trik yang terlalu pintar dengannya. Mengutip dari posting blog itu, "penerapan dari reduce()cukup terbatas pada operator asosiatif, dan dalam semua kasus lain lebih baik untuk menulis lingkaran akumulasi secara eksplisit." Jadi, penggunaannya terbatas, tetapi bahkan GvR pun tampaknya harus mengakui bahwa ini cukup berguna untuk menyimpannya di pustaka standar.
Fred Foo
13
@JBernardo, jadi apakah itu berarti bahwa setiap penggunaan lipatan di Haskell dan Skema sama buruknya? Itu hanya gaya pemrograman yang berbeda, mengabaikannya dan meletakkan jari Anda di telinga dan mengatakan itu tidak jelas tidak membuatnya demikian. Seperti kebanyakan hal dengan gaya yang berbeda , dibutuhkan latihan untuk membiasakan diri . Idenya adalah untuk memasukkan sesuatu ke dalam kategori umum sehingga lebih mudah untuk bernalar tentang program. "Oh, saya ingin melakukan ini, hmm, tampak seperti lipatan" (atau peta, atau terungkap, atau terungkap kemudian lipat di atasnya)
Wes
3
Lambda dengan Python tidak boleh berisi lebih dari satu ekspresi. Anda tidak dapat membuatnya rumit bahkan jika Anda berusaha keras. Jadi Pythonista yang tidak menyukainya mungkin tidak terbiasa dan karenanya tidak menyukai gaya pemrograman fungsional.
golem
16

Haskell

foldl (+) 0 [1,2,3,4,5]

Python

reduce(lambda a,b: a+b, [1,2,3,4,5], 0)

Jelas, itu adalah contoh yang sepele untuk mengilustrasikan suatu hal. Dengan Python Anda hanya akan melakukannya sum([1,2,3,4,5])dan bahkan puritan Haskell umumnya lebih suka sum [1,2,3,4,5].

Untuk skenario non-trivial ketika tidak ada fungsi kemudahan yang jelas, pendekatan pythonic idiomatik adalah dengan secara eksplisit menulis loop for dan menggunakan tugas variabel yang bisa berubah daripada menggunakan reduceatau a fold.

Itu sama sekali bukan gaya fungsional, tetapi itu adalah cara "pythonic". Python tidak dirancang untuk puritan fungsional. Lihat bagaimana Python menyukai pengecualian untuk kontrol aliran untuk melihat bagaimana python idiomatik non-fungsional itu.

tanah liat
sumber
12
lipatan berguna untuk lebih dari sekadar "puritan" fungsional. Mereka adalah abstraksi tujuan umum. Masalah rekursif tersebar luas dalam komputasi. Lipatan menawarkan cara untuk menghapus boilerplate dan cara untuk membuat solusi rekursif aman dalam bahasa yang tidak mendukung rekursi asli. Jadi hal yang sangat praktis. Prasangka GvR di bidang ini sangat disayangkan.
itsbruce
12

Di Python 3, reducetelah dihapus: Catatan rilis . Meskipun demikian, Anda dapat menggunakan modul functools

import operator, functools
def product(xs):
    return functools.reduce(operator.mul, xs, 1)

Di sisi lain, dokumentasi mengungkapkan preferensi terhadap for-loop daripada reduce, karenanya:

def product(xs):
    result = 1
    for i in xs:
        result *= i
    return result
Kyr
sumber
8
reducetidak dihapus dari pustaka standar Python 3. reducedipindahkan ke functoolsmodul saat Anda tunjukkan.
tanah liat
@clay, saya baru saja mengambil frasa dari catatan rilis Guido, tetapi Anda mungkin benar :)
Kyr
6

Memulai Python 3.8, dan pengenalan ekspresi tugas (PEP 572) ( :=operator), yang memberikan kemungkinan untuk memberi nama hasil ekspresi, kita dapat menggunakan pemahaman daftar untuk mereplikasi apa yang oleh bahasa lain disebut operasi lipat / lipat / kurangi:

Diberikan daftar, fungsi pereduksi dan akumulator:

items = [1, 2, 3, 4, 5]
f = lambda acc, x: acc * x
accumulator = 1

kita dapat melipat itemsdengan funtuk mendapatkan dihasilkan tersebut accumulation:

[accumulator := f(accumulator, x) for x in items]
# accumulator = 120

atau dalam bentuk kental:

acc = 1; [acc := acc * x for x in [1, 2, 3, 4, 5]]
# acc = 120

Perhatikan bahwa ini sebenarnya juga merupakan operasi "scanleft" karena pemahaman daftar menunjukkan status akumulasi di setiap langkah:

acc = 1
scanned = [acc := acc * x for x in [1, 2, 3, 4, 5]]
# scanned = [1, 2, 6, 24, 120]
# acc = 120
Xavier Guihot
sumber
5

Anda juga dapat menemukan kembali roda:

def fold(f, l, a):
    """
    f: the function to apply
    l: the list to fold
    a: the accumulator, who is also the 'zero' on the first call
    """ 
    return a if(len(l) == 0) else fold(f, l[1:], f(a, l[0]))

print "Sum:", fold(lambda x, y : x+y, [1,2,3,4,5], 0)

print "Any:", fold(lambda x, y : x or y, [False, True, False], False)

print "All:", fold(lambda x, y : x and y, [False, True, False], True)

# Prove that result can be of a different type of the list's elements
print "Count(x==True):", 
print fold(lambda x, y : x+1 if(y) else x, [False, True, True], 0)
Frédéric
sumber
Anda menukar argumen menjadi fsekitar dalam kasus rekursif Anda.
KayEss
7
Karena Python tidak memiliki rekursi ekor, ini akan merusak daftar yang lebih panjang dan boros. Selain itu, ini bukan benar-benar fungsi "lipat", tetapi hanya lipatan kiri, yaitu lipatan, yaitu, persis apa yang reducesudah ditawarkan (perhatikan bahwa tanda tangan fungsi reduce adalah reduce(function, sequence[, initial]) -> value- ini, juga, mencakup fungsi memberikan nilai awal untuk aki).
cemper93
5

Tidak benar-benar menjawab pertanyaan tersebut, tetapi satu baris untuk foldl dan foldr:

a = [8,3,4]

## Foldl
reduce(lambda x,y: x**y, a)
#68719476736

## Foldr
reduce(lambda x,y: y**x, a[::-1])
#14134776518227074636666380005943348126619871175004951664972849610340958208L
Mehdi Nellen
sumber
2
Saya rasa ini adalah cara yang lebih baik untuk menulis foldr Anda: reduce(lambda y, x: x**y, reversed(a)). Sekarang memiliki penggunaan yang lebih alami, bekerja dengan iterator, dan mengkonsumsi lebih sedikit memori.
Mateen Ulhaq
2

Jawaban sebenarnya untuk masalah (kurangi) ini adalah: Cukup gunakan satu putaran!

initial_value = 0
for x in the_list:
    initial_value += x #or any function.

Ini akan lebih cepat daripada pengurangan dan hal-hal seperti PyPy dapat mengoptimalkan loop seperti itu.

BTW, kasus penjumlahan harus diselesaikan dengan sumfungsi

JBernardo
sumber
5
Ini tidak akan dianggap pythonic untuk contoh seperti ini.
jamylak
7
Loop Python terkenal lambat. Menggunakan (atau menyalahgunakan) reduceadalah cara umum untuk mengoptimalkan program Python.
Fred Foo
2
@larsmans Tolong, jangan datang untuk mengatakan pengurangan lebih cepat daripada loop sederhana ... Itu akan selalu memiliki overhead panggilan fungsi untuk setiap iterasi. Juga, sekali lagi, Pypy dapat mengoptimalkan loop ke kecepatan C
JBernardo
1
@JBernardo: ya, itulah yang saya klaim. Saya baru saja memprofilkan versi saya productterhadap satu dalam gaya Anda, dan itu lebih cepat (meskipun secara marginal).
Fred Foo
1
@JBernardo Dengan asumsi fungsi bawaan (seperti operator.add) sebagai argumen untuk dikurangi: Panggilan ekstra itu adalah panggilan C (yang jauh lebih murah daripada panggilan Python), dan menghemat pengiriman dan interpretasi beberapa instruksi bytecode, yang dapat dengan mudah menyebabkan lusinan panggilan fungsi.
1

Saya yakin beberapa responden dari pertanyaan ini telah melewatkan implikasi yang lebih luas dari foldfungsi sebagai alat abstrak. Ya, sumdapat melakukan hal yang sama untuk daftar bilangan bulat, tetapi ini adalah kasus yang sepele. foldlebih umum. Ini berguna saat Anda memiliki urutan struktur data dengan berbagai bentuk dan ingin mengekspresikan agregasi dengan rapi. Jadi, alih-alih harus membangun forloop dengan variabel agregat dan menghitung ulang secara manual setiap kali, foldfungsi (atau versi Python, yang reducetampaknya sesuai) memungkinkan pemrogram untuk mengekspresikan maksud agregasi jauh lebih jelas dengan hanya menyediakan dua hal:

  • Nilai awal atau "benih" default untuk agregasi.
  • Fungsi yang mengambil nilai agregasi saat ini (dimulai dengan "seed") dan elemen berikutnya dalam daftar, dan mengembalikan nilai agregasi berikutnya.
rq_
sumber
Hai rq_! Saya pikir jawaban Anda akan lebih baik dan menambahkan banyak jika Anda memberikan contoh yang tidak sepele foldyang sulit dilakukan dengan bersih dengan Python, dan kemudian " fold" itu di Python :-)
Scott Skiles
0

Saya mungkin terlambat ke pesta, tetapi kita dapat membuat kustom foldrmenggunakan kalkulus lambda sederhana dan fungsi kari. Berikut adalah implementasi saya dari foldr dengan python.

def foldr(func):
    def accumulator(acc):
        def listFunc(l):
            if l:
                x = l[0]
                xs = l[1:]
                return func(x)(foldr(func)(acc)(xs))
            else:
                return acc
        return listFunc
    return accumulator  


def curried_add(x):
    def inner(y):
        return x + y
    return inner

def curried_mult(x):
    def inner(y):
        return x * y
    return inner

print foldr(curried_add)(0)(range(1, 6))
print foldr(curried_mult)(1)(range(1, 6))

Meskipun implementasinya rekursif (mungkin lambat), itu akan mencetak nilai 15dan 120masing - masing

Celana
sumber