Haskell function for list length

Question

To calculate length of a list, using a foldr, one would do something like:

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

Expanding further on the idea that the folding function needs to increment the second argument, i came up with this (and it's wrong):

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

Further inspection of the type reveals this:

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

Haskell higher order function to calculate length There's an interesting comment on that page, which i can't understand really

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

Can someone explain how does that composition actually work ?

Answer 1

First of all, let's focus why foldr ((+1) . (flip const)) 0 is wrong. You want to increment the second argument only and forget the first one. Semantically, that's

\_ a -> a + 1

However, you wrote the following:

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

Which is why you suddenly need Num (c -> c), since you're trying to apply (+1) on id.

But you actually meant:

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

After all, you want to forget the first argument and use a function f on the second. All you have to to is to use const f.

The composition ((+1).).(flip const) is overly verbose and probably generated by 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