Recursion and intermediate result #

In some cases, we need recursive calls to return more information than what the function should compute.

Example. We want to implement a function

longestWord :: String -> Int

that maps a string to the length of its longest word.

For simplicity, we will assume that words are separated by a blank space (noted ' ' in Haskell).
For instance,

longestWord "Hi there"

should evaluate to 5.

Recall that a string in Haskell is an array of characters.

Consider a string s of the form (c : cs).

Performing a recursive call on cs does not provide enough information to solve the problem for the whole string. In addition to the length lw of the longest word in cs, we may also use the length fw of the first word in cs (i.e. the longest prefix of cs that is free of blank spaces).
Then:

• if c is a blank space, then longestWord s is lw,
• otherwise, longestWord s is max lw (fw + 1).

In order to implement this, we can create an auxiliary recursive function that provides all the information that we need (i.e. returns both lw and fw), as follows:

-- This function is not recursive
longestWord :: String -> Int
longestWord s = lw
    where (_, lw) = longestWordRec s -- call the auxiliary function, and return its second output value

{-
  This auxiliary function is recursive.
  It returns a pair (fw, lw), where
    - `fw` is the length of the first word in the input string, and
    - `lw` is the length of the longest word in the input string.
-}
longestWordRec :: String -> (Int, Int)
longestWordRec [] = (0,0)
longestWordRec (c : cs) | c == ' ' =  (0, lw) -- if `c` is blank, then set `fw` to 0, and `lw` is unchanged
                        | otherwise = (fw + 1, max lw (fw + 1)) -- otherwise increment `fw` and update `lw`
              where (fw,lw) = longestWordRec cs -- recursive call

Note. Auxiliary recursive functions (like the one above) are a very frequent, in all kinds of programming languages (imperative, functional, etc.).