The length of a list without the "length" function in Haskell

Question

I want to see how long a list is, but without using the function length. I wrote this program and it does not work. Maybe you can tell me why? Thanks!

let y = 0
main = do
  list (x:xs) = list (xs)
  y++

list :: [Integer] -> Integer
list [] = y

Answer 1

Your program looks quite "imperative": you define a variable y, and then somehow write a do, that calls (?) the list function (?) that automagically seems to "return y" and then you want to increment y.

That's not how Haskell (and most functional and declarative) languages work:

• in a declarative language, you define a variable only once, after the value is set, there is usually no way to alter its value,
• in Haskell a do usually is used for monads, whereas the length is a pure function,
• the let is a syntax construction to define a variable within the scope of an expression,
• ...

In order to program Haskell (or any functional language), you need to "think functional": think how you would solve the problem in a mathematical way using only functions.

In mathematics, you would say that the empty list [] clearly has length 0. Furthermore in case the list is not empty, there is a first element (the "head") and remaining elements (the "tail"). In that case the result is one plus the length of the tail. We can convert that in a mathematical expression, like:

Now we can easily translate that function into the following Haskell code:

ownLength :: [a] -> Int
ownLength [] = 0
ownLength (_:xs) = 1 + ownLength xs

Now in Haskell, one usually also uses accumulators in order to perform tail recursion: you pass a parameter through the recursive calls and each time you update the variable. When you reach the end of your recursion, you return - sometimes after some post-processing - the accumulator.

In this case the accumulator would be the so far seen length, so you could write:

ownLength :: [a] -> Int
ownLength = ownLength' 0
    where ownLength' a [] = a
          ownLength' a (_:xs) = ownLength' (a+1) xs