Pagina 1 di 1

[Python] foldL come foldR...

MessaggioInviato: 14/12/2019, 18:15
da kaspar
Ciao! Qualche tempo fa il professore ha lasciato come esercizio per i curiosi la definizione in termini di foldR di altre funzioni. Solo foldL non mi riesce... Veniamo al sodo.

Codice:
# FUNZIONI FONDAMENTALI SU LISTE

head = lambda xs: xs[0]
tail = lambda xs: xs[1:]
nil = []

# foldR
foldR = lambda f, xs, v: v if xs == nil else f(head(xs), foldR(f, tail(xs), v))

# foldL (in termini ricorsivi)
foldL = lambda f, xs, v: v if xs == nil else foldL(f, tail(xs), f(v, head(xs)))

# Ma foldL come foldR?


Grazie per l'aiuto. :smt039

Re: [Python] foldL come foldR...

MessaggioInviato: 15/12/2019, 00:22
da apatriarca
È in effetti abbastanza complicato. L'idea è quella di costruire, usando foldR, una funzione che restituisce il risultato della tua foldL dato come argomento il valore iniziale. Il codice del tuo nuovo foldl apparirà quindi nella forma foldR(g, xs, id)(v) per una opportuna funzione g.

La tua g prenderà quindi due argomenti: il primo argomento è head(xs) e il secondo è foldR(g, tail(xs), v). Per ipotesi, il secondo argomento è una funzione che restituisce il valore della foldL calcolato su tail(xs) dato il terzo argomento. Questo terzo argomento deve essere uguale a f(v, head(xs)) (con v calcolato nel passaggio precedente).

Il seguente dovrebbe quindi funzionare (non l'ho verificato)
Codice:
def foldl(f, xs, v):
    def g(h, r):
        return lambda z: r(f(z, h))
    return foldr(g, xs, id)(v)

Re: [Python] foldL come foldR...

MessaggioInviato: 15/12/2019, 08:20
da kaspar
Cos'è id? :shock: Mi pare che non sia quello che vuoi
Codice:
>>> foldl(lambda x,y: x+y, [1,2,3], 0)
94234912400288

Io mi aspetterei \[
(((0+1)+2)+3)=6
\]

Re: [Python] foldL come foldR...

MessaggioInviato: 15/12/2019, 18:04
da apatriarca
id dovrebbe essere una funzione built-in che restituisce il suo argomento, ma stranamente sostituendo id con lambda x: x nella definizione di sopra ha funzionato per me. Non ti saprei dire perché. La seguente versione mi restituisce insomma il risultato corretto (e anche le operazione eseguite sono quelle corrette se provi a stamparle.
Codice:
def foldl(f, xs, v):
    return foldR(lambda h, g: lambda x: g(f(x, h)), xs, lambda x: x)(v)

def print_args(x, y):
     print(x, y, x + y)
     return x + y

foldl(print_args, [1, 2, 3], 0)
# 0 1 1
# 1 2 3
# 3 3 6
# Out[27]: 6


EDIT: Ovviamente sarebbe stato meglio se avessi letto la documentazione invece di andare a memoria. id restituisce il valore univoco associato ad un particolare valore in Python. Certamente non quello che volevo.. :oops:

Re: [Python] foldL come foldR...

MessaggioInviato: 15/12/2019, 19:18
da kaspar
Ah, ecco volevo dire. :lol: Adesso funziona. Appena ho un po' di tempo provo e leggermi la definizione e a comprenderla.

Re: [Python] foldL come foldR...

MessaggioInviato: 17/12/2019, 10:27
da apatriarca
Forse un modo più semplice per affrontare la definizione (che sarebbe più comoda se python supportasse alcune funzionalità aggiuntive dei linguaggi funzionali) è quella di cercare di trovare le funzioni g e h per cui:
Codice:
lambda v: foldl(f, xs, v) == foldr(g, xs, h)

Entrambe le funzioni hanno una definizione particolare per xs == [] per cui otteniamo la prima funzione:
Codice:
lambda v: v == h

Per la seconda funzione dobbiamo guardare alla seconda definizione per entrambe ottenendo
Codice:
lambda v: foldl(f, tail(xs), f(v, head(xs)) == g(head(xs), foldr(g, tail(xs), h))

A questo punto puoi riutilizzare la relazione che vuoi dimostrare nella parte sinistra dell'equazione ottenendo:
Codice:
lambda v: foldr(g, tail(xs), h)(f(v, head(xs)) == g(head(xs), foldr(g, tail(xs), h))

Aggiungendo un po' di variabili a questo punto ottieni:
Codice:
g(H, R) = lambda v: R(f(v, H))

come nella mia definizione.