Avoid pattern matching in recursion

Question

Consider this code which I used to solve Euler Problem 58:

diagNums = go skips 2
    where go (s:skips) x = let x' = x+s
                           in x':go skips (x'+1)

squareDiagDeltas = go diagNums
    where go xs = let (h,r) = splitAt 4 xs
                  in h:go r

I don't like the pattern matching in the second function. It looks more complicated than necessary! This is something that arises pretty frequently for me. Here, splitAt returns a tuple, so I have to destructure it first before I can recurse. The same pattern arises perhaps even more annoyingly when my recursion itself returns a tuple I want to modify. Consider:

f n = go [1..n]
    where go [] = (0,0)
          go (x:xs) = let (y,z) = go xs
                      in (y+x, z-x)

compared to the nice and simple recursion:

f n = go [1..n]
    where go [] = 0
          go (x:xs) = x+go xs

Of course the functions here are pure nonsense and could be written in a wholly different and better way. But my point is that the need for pattern matching arises every time I need to thread more than one value back through the recursion.

Are there any ways to avoid this, perhaps by using Applicative or anything similar? Or would you consider this style idiomatic?

Answer 1

First of all, that style is actually rather idiomatic. Since you're doing two things to two different values, there is some irreducible complexity; the actual pattern match does not introduce much on its own. Besides, I personally find the explicit style very readable most of the time.

However, there is an alternative. Control.Arrow has a bunch of functions for working with tuples. Since the function arrow -> is an Arrow as well, all these work for normal functions.

So you could rewrite your second example using (***) to combine two functions to work over tuples. This operator has the following type:

(***) :: a b c -> a b' c' -> a (b, b') (c, c')

If we replace a with ->, we get:

(***) :: (b -> c) -> (b' -> c') -> ((b, b') -> (c, c'))

So you could combine (+ x) and (- x) into a single function with (+ x) *** (- x). This would be equivalent to:

\ (a, b) -> (a + x, b - x)

Then you could use it in your recursion. Unfortunately, the - operator is stupid and doesn't work in sections, so you would have to write it with a lambda:

(+ x) *** (\ a -> a - x) $ go xs 

You can obviously imagine using any other operator, all of which aren't quite as stupid :).

Honestly, I think this version is less readable than the original. However, in other cases, the *** version can be more readable, so it's useful to know about it. In particular, if you were passing (+ x) *** (- x) into a higher-order function instead of applying it immediately, I think the *** version would be better than an explicit lambda.

Answer 2

I agree with Tikhon Jelvis that there is nothing wrong with your version. Like he said, using combinators from Control.Arrow can be useful with higher order functions. You can write f using a fold:

f n = foldr (\x -> (+ x) *** subtract x) (0,0) [1..n]

And if you really want to get rid of the let in squareDiagDeltas (I'm not sure I would), you can use second, because you are only modifying the second element of the tuple:

squareDiagDeltas = go diagNums
  where go = uncurry (:) . second go . splitAt 4

Answer 3

I agree with hammar, unfoldr is the way to go here.

You can also get rid of the pattern matching in diagNums:

diagNums = go skips 2
    where go (s:skips) x = let x' = x+s
                           in x':go skips (x'+1)

The recursion makes it a little difficult to tell what's going on here, so let's examine it in depth.

Suppose skips = s0 : s1 : s2 : s3 : ..., then we have:

diagNums = go skips 2
         = go (s0 : s1 : s2 : s3 : ...) 2 
         = s0+2 : go (s1 : s2 : s3 : ... ) (s0+3)
         = s0+2 : s0+s1+3 : go (s2 : s3 : ... ) (s0+s1+4) 
         = s0+2 : s0+s1+3 : s0+s1+s2+4 : go (s3 : ... ) (s0+s1+s2+5) 
         = s0+2 : s0+s1+3 : s0+s1+s2+4 : s0+s1+s2+s3+5 : go (...) (s0+s1+s2+s3+6) 

This makes it much clearer what's going on, we've got the sum of two sequences, which is easy to compute using zipWith (+):

diagNums = zipWith (+) [2,3,4,5,...] [s0, s0+s1, s0+s1+s2, s0+s1+s2+s3,...] 

So now we just need to find a better way to compute the partial sums of skips, which is a great use for scanl1:

scanl1 (+) skips = s0 : s0+s1 : s0+s1+s2 : s0+s1+s2+s3 : ...

Leaving a (IMO) much easier to understand definition for diagNums:

diagNums = zipWith (+) [2..] $ scanl1 (+) skips