funzione Haskell per la lunghezza lista

Question

Per calcolare la lunghezza di una lista, utilizzando un foldr, si potrebbe fare qualcosa di simile:

foldr (\_ acc -> acc + 1) 0 

espandere ulteriormente l'idea che la funzione di ripiegamento ha bisogno di incrementare il secondo argomento, mi sono con questo (ed è sbagliato):

foldr ((+1) . (flip const)) 0` 

un'ulteriore ispezione del tipo rivela questo:

(+1) . (flip const) :: Num (c -> c) => a -> c -> c 

Haskell higher order function to calculate length C'è un interessante commento su quella pagina, che non riesco a capire davvero

foldr (((+1).).(flip const)) 0 

Qualcuno può spiegare in che modo che la composizione in realtà il lavoro?

Answer 1

Prima di tutto, concentriamoci sul motivo per cui foldr ((+1) . (flip const)) 0 è sbagliato. Si desidera aumentare solo il secondo argomento e dimenticare il primo. Semanticamente, che è

\_ a -> a + 1 

Tuttavia, è scritto quanto segue:

(+1) . flip const 
= (+1) . (\_ a -> a) 
= \x -> (+1) . (\_ a -> a) $ x 
= \x -> (+1) $ (\_ a -> a) $ x 
= \x -> (+1) $ \a -> a 
= \_ -> (+1) (\a -> a) 
= const ((+1) (\a -> a)) 

Quale è il motivo per cui improvvisamente bisogno Num (c -> c), dal momento che si sta cercando di applicare (+1) su id.

Ma in realtà dire:

\_ a -> a + 1 
= \_ a -> (+1) a 
= \_ -> (+1) 
= const (+1) 

Dopo tutto, si vuole dimenticare il primo argomento e utilizzare una funzione f sul secondo. Tutto ciò che devi fare è usare const f.

La composizione ((+1).).(flip const) è eccessivamente prolisso e probabilmente generato da pointfree:

((+1).).(flip const) 
= ((\x -> x + 1).) . (\a _ -> a) 
= \c -> ((\x -> x + 1).) . (\a _ -> a) $ c 
= \c -> ((\x -> x + 1).) $ \_ -> c 
= \c -> \f -> (\x -> x + 1) . f $ \_ -> c 
= \c -> (\x -> x + 1) . \_ -> c 
= \_ c -> (\x -> x + 1) $ c 
= \_ c -> c + 1 

Answer 2

Questo è veramente un commento, ma troppo lungo per uno.

A meno che non hai a che fare con i numeri strane come pigri Nat s, si vuole veramente

length xs = foldl' (\acc _ -> 1 + acc) 0 xs 

Fare questo inutile,

Se si desidera, è possibile trasformare l'originale foldl' espressione in a foldr modulo in questo modo:

length xs = foldr go id xs 0 where 
    go _ r acc = r $! 1 + acc 

masticando go,

go _ r acc = ($!) r $ (+) 1 acc 
go _ r = ($!) r . (+1) 
go _ r = (. (+1)) (($!) r) 
go _ = (. (+1)) . ($!) 
go = const ((. (+1)) . ($!)) 

Masticare length,

length = flip (foldr go id) 0 

Mettere tutto insieme,

length = flip (foldr (const ((. (+1)) . ($!))) id) 0 

Io, per esempio, trovo questa forma libera-punto del tutto opaco.