Avoid pattern matching in recursion

Question

Consider this code that I used to solve Euler 58 problem:

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 pattern matching in the second function. It looks harder than necessary! This is something that arises quite often for me. Here splitAt returns the tuple, so I must first destroy it before I can return. The same picture arises, perhaps even more annoyingly, when the recursion itself returns the tuple that I want to change. Consider:

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

compared to good and simple recursion:

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

Of course, the functions here are pure nonsense and can be written in a completely different and better way. But I want to say that the need for pattern matching arises every time I need to scroll more than one value back through recursion.

Are there any ways to avoid this, possibly using Applicative or something like that? Or do you think this style is idiomatic?

Answer 1

First of all, this style is actually quite idiomatic. Since you do two things with two different meanings, there is some irreducible complexity; Actual pattern matching does little. In addition, I personally believe that explicit style is very readable most of the time.

However, there is an alternative. Control.Arrow has tons of functions for working with tuples. Since the arrow -> function -> also an Arrow , they all work for normal functions.

So, you can rewrite your second example using (***) to combine the two functions for working on tuples. This statement has the following type:

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

If we replace a with -> , we get:

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

So you can combine (+ x) and (- x) into one function with (+ x) *** (- x) . This will be equivalent to:

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

Then you can use it in your recursion. Unfortunately, the operator is stupid and does not work in partitions, so you have to write it using lambda:

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

You obviously can imagine using any other operator, all of which are not so stupid :).

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

Answer 2

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

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

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

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

Answer 3

I agree with hammar , unfoldr - the way here .

You can also get rid of pattern matching in diagNums :

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

Recursion lets you talk a little about what's going on here, so let's take a close look at it.

Suppose that 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 more clear what is happening, we have a sum of two sequences that are easy to calculate 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 the best way to calculate the partial sums of skips , which is very useful for scanl1 :

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

Leave (IMO) is much easier to understand for diagNums :

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