chiare su definizione del tipo di foldl

Question

foldl :: (a -> b -> a) -> a -> [b] -> a 
foldl step zero (x:xs) = foldl step (step zero x) xs 
foldl _ zero []  = zero 

io non capisco il motivo per cui lo fa (a -> b ->un) tornare un, anche (a -> b -> a) -> a -> [b] ->a restituisce a. Penso che dovrebbe essere come: (a -> b ->c) -> a -> [b] ->c. Qualcuno può spiegarmelo in base all'esempio qui sotto. Grazie!

foldl (+) 0 (1:2:3:[]) 
foldl (+) (0 + 1) (2:3:[]) 
foldl (+) ((0 + 1) + 2) (3:[]) 
foldl (+) (((0 + 1) + 2) + 3) ([]) 
foldl (+) (((0 + 1) + 2) + 3) 

Answer 1

a rappresenta il tipo del valore dell'accumulatore e b rappresenta il tipo di ciascun elemento nell'input. (a -> b -> a) è una funzione che accetta un valore di accumulatore, una voce nell'elenco e restituisce un nuovo valore di accumulatore che può essere passato al passaggio successivo.

Il tipo del valore iniziale deve essere a in modo che la prima chiamata della funzione possa ricevere un valore di accumulatore. La funzione di accumulatore deve prendere un a e restituire un a in modo che un valore di accumulatore possa essere passato a ciascun passo della piega. Il valore finale della piega deve necessariamente essere un a, perché quello è il tipo dell'accumulatore che verrà restituito dalla chiamata finale alla funzione di piega.

(a -> b -> c) -> a -> [b] -> c non può rappresentare una piega, poiché la funzione di piegatura non richiede un c. L'input e l'output della funzione di piegatura devono essere dello stesso tipo in modo che l'accumulatore possa essere passato al passaggio successivo.

Vediamo un esempio di cosa accadrebbe se la funzione di piegatura restituisse un c.

f :: Integer -> Integer -> Bool -- this is a valid (a -> b -> c) 
f acc n = (acc + n) > 0 

Fingere che stiamo usando un linguaggio dinamico e cerchiamo di piegare con f. Cosa succede al runtime?

foldl f 0 [1]  ~ (0 + 1) > 0   == True :: Bool 

foldl f 0 [1, 2] ~ ((0 + 1) > 0) + 2) > 0 == error - no instance of (+) for Bool 
        \_________/ \ 
          |   \ 
         Bool  + Integer 

Si può vedere che non è possibile eseguire una piegatura se si tenta di accumulare con tipi incompatibili.

Answer 2

Il tipo di ritorno della funzione di piegatura (di tipo (a -> b -> a)) deve essere uguale al tipo del suo primo ingresso. Questo perché, guardando la (quasi corretta, eccetto l'ultima riga, che non dovrebbe avere la valutazione foldl (+)) che hai dato, il risultato di una precedente chiamata della funzione di piegatura viene passato come primo input alla successiva chiamata. Pertanto, i tipi devono corrispondere. in (a -> b -> c) i tipi del primo argomento e il risultato corrispondono solo se a ~ c (uguaglianza per i tipi), ma in questo caso come ae c sono uguali potremmo chiamarli entrambi a. Dato che la funzione di piegatura restituisce qualcosa di tipo a, anche il risultato dell'intera chiamata foldl sarà di tipo a, poiché restituisce semplicemente il risultato dell'ultima chiamata alla funzione di piegatura.