Haskell-Funktion für Listenlänge

Question

Um Länge einer Liste zu berechnen, eine foldr verwenden, würde man etwas tun:

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

baut auf der Idee, dass die Klappfunktion das zweite Argument erhöhen muss, kam ich up mit diesem (und es ist falsch):

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

Eine weitere Untersuchung des Typs zeigt dies:

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

Haskell higher order function to calculate length Es ist ein interessanter Kommentar auf dieser Seite, die ich wirklich nicht verstehen kann

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

Kann mir jemand erklären, wie funktioniert eigentlich, dass Zusammensetzung arbeiten?

Answer 1

Zunächst konzentrieren wir uns, warum foldr ((+1) . (flip const)) 0 falsch ist. Sie möchten nur das zweite Argument erhöhen und das erste Argument vergessen. Semantisch ist das

\_ a -> a + 1 

Sie jedoch folgendes geschrieben:

(+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)) 

Welches ist, warum Sie plötzlich Num (c -> c) benötigen, da Sie (+1) auf id anzuwenden versuchen.

Aber du eigentlich gemeint:

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

Schließlich wollen Sie das erste Argument vergessen und eine Funktion f auf dem zweiten verwenden. Alles, was Sie tun müssen, ist const f zu verwenden.

Die Zusammensetzung ((+1).).(flip const) ist allzu ausführlich und wahrscheinlich erzeugt durch 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

Das ist wirklich ein Kommentar, aber für eine zu lange viel.

Wenn Sie nicht mit seltsamen Zahlen wie faul Nat s es zu tun, die Sie wirklich wollen

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

machen diese sinnlos,

Wenn Sie möchten, können Sie die ursprüngliche foldl' Ausdruck verwandeln sich in eine foldr Form etwa so:

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

Kauen auf go,

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

Kauen auf length,

length = flip (foldr go id) 0 

setzen sie alle zusammen,

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

ich, für einen, finden diesen Punkt freier Form völlig undurchsichtig.