Haskell How recursion on list works

Question

Im learning Haskell, can someone explain me, why this function works? i mean, how the induction case is not running forever? what is the stop condition here?

    myLength :: [a] -> Integer
    myLength []     = 0
    myLength (x:xs) = (+1) (myLength xs)

Answer 1

The stop condition is that the list is exhausted, so the [] pattern. In that case Haskell will return an 0.

In the recursive case, we thus match with any non-empty list (x:xs), with x the first element, and xs the tail (the list of remaining elements). In that case we thus return 1 + myLength xs, so we recurse on the tail.

This means that for every finite list, we will eventually make a recursive call with [] as parameter, and thus return 0.

An equivalent algorithm in Python will thus look like:

def myLength(items):
    if len(items):
        return myLength(items[1:]) + 1
    else:
        return 0

here calculating the tail will take O(n), whereas in Haskell it will take O(1).