[Python] foldL come foldR...

[kaspar1]

Ciao! Qualche tempo fa il professore ha lasciato come esercizio per i curiosi la definizione in termini di [inline]foldR[/inline] di altre funzioni. Solo [inline]foldL[/inline] non mi riesce... Veniamo al sodo.

# 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.

[apatriarca]

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

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

Il seguente dovrebbe quindi funzionare (non l'ho verificato)

def foldl(f, xs, v):
    def g(h, r):
        return lambda z: r(f(z, h))
    return foldr(g, xs, id)(v)

[kaspar1]

Cos'è [tt]id[/tt]? Mi pare che non sia quello che vuoi

>>> foldl(lambda x,y: x+y, [1,2,3], 0)
94234912400288

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

[apatriarca]

[strike][tt]id[/tt] dovrebbe essere una funzione built-in che restituisce il suo argomento,[/strike] ma stranamente sostituendo [tt]id[/tt] con [tt]lambda x: x[/tt] 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.

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. [tt]id[/tt] restituisce il valore univoco associato ad un particolare valore in Python. Certamente non quello che volevo..

[kaspar1]

Ah, ecco volevo dire. Adesso funziona. Appena ho un po' di tempo provo e leggermi la definizione e a comprenderla.

[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 [tt]g[/tt] e [tt]h[/tt] per cui:

lambda v: foldl(f, xs, v) == foldr(g, xs, h)

Entrambe le funzioni hanno una definizione particolare per [tt]xs == [][/tt] per cui otteniamo la prima funzione:

lambda v: v == h

Per la seconda funzione dobbiamo guardare alla seconda definizione per entrambe ottenendo

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:

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:

g(H, R) = lambda v: R(f(v, H))

come nella mia definizione.