CODEWITHSUNDEEP
listhaskellfoldcurrying
C. Rib
C. Rib

Reputation: 390

Haskell: Calculate the length of a list using (curry snd)

I was given an assignment to calculate the length of a list using the foldr Haskell function, so I did these two examples

flength :: [a] -> Int
flength = foldr (\ _ n -> n+1) 0

flength' :: [a] -> Int
flength' l = foldr aux 0 l
    where
        aux _ n = n+1

Then, as a personal challenge, the professor asked us to use the snd function and yesterday I came up with this:

flength'' :: [a] -> Int
flength'' = foldr ((+1).(curry snd)) 0

What I want to happen is that this function will turn the head of the list h and the accumulator 0 into the pair (h,0) then return 0 and after that apply it to the function (+1)

I expected this to be done recursively, effectively giving me the length of the list at the end.

Instead, I get this error message:

    [1 of 1] Compiling Main             ( f1.hs, interpreted )

f1.hs:54:24: error:
    * No instance for (Num (Int -> Int))
        arising from an operator section
        (maybe you haven't applied a function to enough arguments?)
    * In the first argument of `(.)', namely `(+ 1)'
      In the first argument of `foldr', namely `((+ 1) . (curry snd))'
      In the expression: foldr ((+ 1) . (curry snd)) 0 xs
Failed, modules loaded: none.

Why is this happening and how can I get this code to work?

Upvotes: 2

Views: 219

Answers (1)

Zeta
Zeta

Reputation: 105905

Let us lay all our tools in front of us, like a good artisan does:

foldr :: (a -> b -> b) -> b -> [a] -> b
snd   :: (a, b) -> b

First, we note that snd and foldr do not really fit well. So let's use curry, just like you did, and add curry snd to our small tool library:

foldr     :: (a -> b -> b) -> b -> [a] -> b
curry snd ::  a -> b -> b

This looks very promising. Now we need to add 1 to the result of curry snd, otherwise we're just writing flip const. Let's start with a lambda:

\a b -> 1 + curry snd a b
= \a b -> ((+1) . curry snd a) b

We can now shove of b and end up with

\a -> (+1) . curry snd a
= \a -> (.) (+1) (curry snd a)
= \a -> ((.) (+1)) (curry snd a)
= \a -> (((.) (+1)) . curry snd) a

Now we can eta-reduce a from both sides too and end up with

(((.) (+1)) . curry snd) = ((+1) . ) . curry snd

Therefore, your third variant would be 

flength'' = foldr (((+1) . ) . curry snd) 0

Now, why did you get your error message? You were close with (+1) . curry snd, but the types don't work out:

(+1)      :: Int -> Int
--            v                    v
(.)       :: (b ->  c)    -> (a -> b       ) -> a -> c
curry snd ::                  t -> (x -> x)
              ^                     ^

But in your case, the bs in (.)'s signature didn't match. One of them was an Int, the other was a function.

TL;DR: If you want to write f (g x y) point-free, write ((f.) . g)

Upvotes: 4

Related Questions