Haskell How recursion on list works

user_16690464 0
Viewed 150

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)
haskell
3 Answers

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).

user_675790

Functions can be defined in a piecewise fashion in Haskell; the cases are checked from top to bottom, with the first one that applies being used.

The definition can be written more explicitly as

myLength ns = case ns of
                [] -> 0
                (x:xs) -> (+1) (myLength xs)

or

myLength ns = if null ns then 0 else (+1) (myLength (tail xs))

If the [] case matches or null as is true, then the recursive call is never made. If the recursive call is made, note that xs is a strictly shorter list than ns (when ns is finite), so the recursion will terminate. (In some sense, xs is also shorter than ns even when ns is infinite, but I don't want to get into the intricacies of infinities here.)

user_11268410

The first line describes the types: it takes a list of something and returns an Integer.

The next two lines are the function implementation: which line is executed depends on what the arguments passed in are. This is called pattern matching.

The second line says that if the list passed in is empty the function returns 0.

Otherwise the function has received a non empty list where the first element is called x and the rest of the list is called xs. It adds 1 to the result of calling itself with xs.

So once this function is called every iteration receives a smaller list to work on until a call receives the empty list, at which point the second line is called.

user_2173240
Related