[Python] foldL come foldR...

Messaggioda kaspar » 14/12/2019, 18:15

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
kaspar
Junior Member
Junior Member
 
Messaggio: 33 di 495
Iscritto il: 17/11/2019, 09:58

Re: [Python] foldL come foldR...

Messaggioda apatriarca » 15/12/2019, 00:22

È 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)
apatriarca
Moderatore
Moderatore
 
Messaggio: 5330 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: [Python] foldL come foldR...

Messaggioda kaspar » 15/12/2019, 08:20

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
\]
kaspar
Junior Member
Junior Member
 
Messaggio: 34 di 495
Iscritto il: 17/11/2019, 09:58

Re: [Python] foldL come foldR...

Messaggioda apatriarca » 15/12/2019, 18:04

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:
apatriarca
Moderatore
Moderatore
 
Messaggio: 5331 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: [Python] foldL come foldR...

Messaggioda kaspar » 15/12/2019, 19:18

Ah, ecco volevo dire. :lol: Adesso funziona. Appena ho un po' di tempo provo e leggermi la definizione e a comprenderla.
kaspar
Junior Member
Junior Member
 
Messaggio: 35 di 495
Iscritto il: 17/11/2019, 09:58

Re: [Python] foldL come foldR...

Messaggioda apatriarca » 17/12/2019, 10:27

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.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5332 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite