Safety, sharing, and laziness

Question

Is there a more succinct way to write code like this that has a lot of sharing between branches of the case statement?

(This is the main part of my solution to one of the Round 1 problems of the Facebook Hacker Cup 2012. The round is over.)

type Memoizable a = a -> a

recoveries :: Int -> Memoizable (String -> Int)
recoveries m = go
  where go self ('0':_) = 0
        go self [] = 1
        go self ss = flip rem 0xfaceb00c $ case analysis ss of
          HasMany
            | cValid -> cCase + bCase + aCase
            | bValid -> bCase + aCase
            | aValid -> aCase
          Has2
            | bValid -> bCase + aCase
            | aValid -> aCase
          Has1
            | aValid -> aCase
          _
            | otherwise -> 0
          where a = digitToInt (first ss)
                b = a * 10 + digitToInt (second ss)
                c = b * 10 + digitToInt (third ss)
                aValid = a <= m
                bValid = b <= m
                cValid = c <= m
                aCase = self (drop 1 ss)
                bCase = self (drop 2 ss)
                cCase = self (drop 3 ss)

-- not to be confused with functions of same name from Control.Arrow
first (x:_) = x
second (_:x:_) = x
third (_:_:x:_) = x

data Analysis = Empty | Has1 | Has2 | HasMany

-- a dumb little function to help with safety and sharing                       
analysis :: [a] -> Analysis
analysis [] = Empty
analysis [_] = Has1
analysis [_,_] = Has2
analysis _ = HasMany

Answer 1

Hm, why did you write go as a separate function? It is - as you state - the same as recoveries, why the local definition?

For making it more succinct, I think it's easiest to have an intermediate data structure that carries both pieces of information you seek in the case: Whether there are enough digits and what number the digits so far would form.

The first data structure that comes to mind is a list of numbers - we just need to construct it. In this case, scanl is our friend:

import Data.List (scanl)
import Data.Char (digitToInt)

type Memoizable a = a -> a

recoveries :: Int -> Memoizable (String -> Int)
recoveries _ _    ('0':_) = 0
recoveries _ _    []      = 1
recoveries m self ss      = result `rem` 0xfaceb00c
  where result = case tail (scanl addDigit 0 ss) of
          (_:_:c:_) | c <= m  -> aCase+bCase+cCase
          (_:b:_)   | b <= m  -> aCase+bCase
          (a:_)     | a <= m  -> aCase
          _                   -> 0
        addDigit x c = x*10 + digitToInt c
        aCase = self (drop 1 ss)
        bCase = self (drop 2 ss)
        cCase = self (drop 3 ss)

Unless I've made a mistake (can't test), this should do the same as your code, and now we can write everything cleanly using pattern matches and a few guards on the intermediate list.

You could get rid of aCase, bCase and cCase as well if you would zip the result of scanl with tails ss. But while this is more general, I felt it would have made the code harder to understand, so I left it like this.