Common recursion pattern

Question

I'm getting used to Haskell's higher-order functions. Usually I can replace explicit patterns of recursion with functions like map, fold, and scan. However, I often run into the following recursion pattern which I don't understand how to express using higher-order functions:

   f (x:[]) = k x
   f (x:xs) = g x (f xs)

For instance, suppose I am representing analytic tableaux. Then I create a data type such as:

   data Tableau = N Expr | S Expr (Tableau) | B Expr (Tableau) (Tableau)

If I want to convert a list of Exprs into a tableau structure, I want a function part of which might resemble:

   f (x:[]) = N x
   f (x:xs) = S x (f xs)

Now, I see three options: (1) create a function which decides, given a tableau and a list, whether the next branch in the tableau should be an S or N (or B, but we'll ignore that case); (2) use a higher-order function to encapsulate the recursion pattern of f; (3) use a function like f.

What would the best option be?

Answer 1

If I've understood the question properly, then here's my evaluation of your options:

1) It's probably a bit nasty to have to match the (presumably arbitrarily complex?) tableau out from underneath the constructor in order to write that function. This approach seems somewhat brittle, although it would probably work just fine.

2) I don't see the need to generalise the pattern out, given that it's a recursive function operating on a recursive structure. Introducing a higher-order pattern would (I think) obfuscate the actual logic behind performing a recursive traversal of this data structure.

3) I think this makes a good deal of sense. As you've observed, it's a reasonably recognised "pattern", but I think it matches the description of the algorithm well to write it down in exactly this way. It may not be as generalisable or reusable, but given that it's essentially the crux of the algorithmic approach, I think it makes sense to write the cases directly as you have done in a function like f. This would be my favoured approach.

Sorry to not provide a particularly concrete answer, but it is a reasonably subjective answer, so given the three options above, I would pick option 3 for reasons of clarity and readability.

Answer 2

I'd most probably use the following:

f xs = foldr g (k (last xs)) (init xs)

It basically means that the end of the list is replaced by k x when folding. Thanks to lazy evaluation present everywhere, it works even for infinite lists.

There are two other solutions - adding empty case and using Maybe.

A) adding empty case:

It would be best if f [] was well-defined. Then, you could write the definition as

f [] = c
f (x:xs) = g x (f xs)

which is f = foldr g c. For example, if you change

data Tableau = N Expr | S Expr Tableau | B Expr Tableau Tableau

to

data Tableau = N | S Expr Tableau | B Expr Tableau Tableau

then you can represent single-element tableaux as S expr N, and the function is defined as one-liner

f = foldr S N

It's the best solution as long the empty case makes sense.

B) use Maybe:

On the other hand, if f [] cannot be sensibly defined, it's worse. Partial functions are often considered ugly. To make it total, you can use Maybe. Define

 f [] = Nothing
 f [x] = Just (k x)
 f (x:xs) = Just (g x w)
            where Just w = f xs

It is a total function - that's better.

But now you can rewrite the function into:

 f [] = Nothing
 f (x:xs) = case f xs of
              Nothing -> Just (k x)
              Just w -> Just (g x w)

which is a right fold:

 addElement :: Expr -> Maybe Tableaux -> Maybe Tableaux
 addElement x Nothing = Just (N x)
 addElement x (Just w) = Just (S x w)

 f = foldr addElement Nothing

In general, folding is idiomatic and should be used when you fit the recursion pattern. Otherwise use explicit recursion or try to reuse existing combinators. If there's a new pattern, make a combinator, but only if you'll use the pattern a lot - otherwise it's overkill. In this case, the pattern is fold for nonempty lists defined by: data List a = End a | Cons a (List a).