Perché fold left si aspetta (a -> b -> a) anziché (b -> a -> a)?

Question

Mi chiedo perché la funzione prevista dalla piega a sinistra abbia la firma del tipo a -> b -> a anziché b -> a -> a. C'è una decisione di progettazione dietro a questo?

In Haskell, ad esempio, devo scrivere foldl (\xs x -> x:xs) [] xs per invertire un elenco anziché il più breve foldl (:) [] xs (che sarebbe possibile con b -> a -> a). D'altra parte, ci sono casi d'uso che richiedono lo standard a -> b -> a. In Scala, questo potrebbe essere aggiunto: xs.foldLeft(List.empty[Int]) ((xs, x) => xs:+x) che può essere scritto come xs.foldLeft(List.empty[Int]) (_:+_).

In proporzione, più casi di utilizzo si verificano richiedendo la firma del tipo specificato anziché quella alternativa, o ci sono altre decisioni che hanno portato al design che fold ha lasciato in Haskell e Scala (e probabilmente in molte altre lingue)?

Answer 1

Concettualmente parlando, un diritto piega, dire foldr f z [1..4] sostituisce un elenco del seguente modulo

: 
/\ 
1 : 
/\ 
    2 : 
    /\ 
    3 : 
    /\ 
     4 [] 

con il valore di un'espressione della forma seguente

f 
/\ 
1 f 
/\ 
    2 f 
    /\ 
    3 f 
    /\ 
     4 z 

Se dovessimo rappresentare questo espressione su una singola riga, tutte le parentesi si associano a destra, quindi la piega a destra del nome: (1 `f` (2 `f` (3 `f` (4 `f` z)))). Una piega a sinistra è doppia in un certo senso per una piega a destra. In particolare, vorremmo per la forma del diagramma corrispondente per una piega sinistra sia un'immagine speculare di quello per una piega sinistra, come il seguente:

 f 
    /\ 
     f 4 
    /\ 
    f 3 
/\ 
    f 2 
/\ 
z 1 

Se dovessimo scrivere questo diagramma una singola linea, otterremmo un'espressione in cui tutto associato parentesi a sinistra, che strambate bene con il nome di una piega a sinistra:

((((z `f` 1) `f` 2) `f` 3) `f` 4) 

Ma notare che in questo diagramma specchio, il risultato ricorsiva della piega è alimentato a f come primo argomento, mentre ogni elemento della lista è alimentato come secondo argomento, cioè gli argomenti vengono inviati a f in ordine inverso rispetto alle pieghe giuste.

Answer 2

Perché si scrive (a /: bs) per foldLeft in forma abbreviata; questo è un operatore che spinge lo attraverso tutti gli bs, quindi è naturale scrivere la funzione allo stesso modo (ad esempio (A,B) => A). Notare che foldRight lo fa nell'altro ordine.

Answer 3

La firma del tipo è foldl :: (a -> b -> a) -> a -> [b] -> a; è naturale che la funzione di combinazione abbia il valore iniziale a sinistra, perché è il modo in cui si combina con gli elementi della lista. Allo stesso modo, noterai che foldr ha il contrario. La complicazione della tua definizione di reverse è dovuta al fatto che stai usando un'espressione lambda in cui flip sarebbe stato più bello: foldl (flip (:)) [] xs, che ha anche la piacevole somiglianza tra i concetti di flip e reverse.

Answer 4

Diciamo che avete questo:

List(4, 2, 1).foldLeft(8)(_/_) 

Questo è lo stesso di:

((8/4)/2)/1 

vedere come il primo parametro è sempre te accumulatore?Avere i parametri in questo ordine rende la sintassi del segnaposto (il carattere di sottolineatura) una traduzione diretta nell'espressione espansa.