CODEWITHSUNDEEP
haskellfold
sa___
sa___

Reputation: 363

Haskell function for list length

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 ?

Upvotes: 8

Views: 1455

Answers (2)

dfeuer
dfeuer

Reputation: 48591

This is really a comment, but much too long for one.

Unless you're dealing with weird numbers like lazy Nats, you really want

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

Making this pointless,

length = foldl' (\acc -> const ((1+) acc)) 0
length = foldl' (const . (1+)) 0

If you like, you can transform the original foldl' expression into a foldr form like so:

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

Chewing on go,

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

Chewing on length,

length = flip (foldr go id) 0

Putting it all together,

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

I, for one, find this point-free form utterly opaque.

Upvotes: 3

Zeta
Zeta

Reputation: 105885

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

Upvotes: 6

Related Questions