Palindrome.md

So we're given the task of determining whether a given integer is a palindrome in base 10.

Seems easy enough:

isPalindrome :: Integer -> Bool
isPalindrome n = show n == reverse (show n)

Done. That was a short article.

Oh wait, type String = [Char] and we can't use lists.

Well, let's see if we can refactor this into something that doesn't use lists, step by step.

---

First, let's get rid of that use of show. It made me feel kinda sketchy anyway, using strings.

We can get rid of the one on the left by applying read to both sides:

isPalindrome n = read (show n) == read (reverse (show n))

(To handle negative numbers, and numbers ending in 0, I really should use read' = read . takeWhile isDigit . dropWhile (=='0'), so let's imagine I did).

Then we can use read . show == id (for Integer, at least) to simplify:

isPalindrome n = n == read (reverse (show n))

Since we'll be playing with the RHS of the == for the rest, let's extract that to its own function:

isPalindrome = n == reversal n

reversal :: Integer -> Integer
reversal = read . reverse . show

To get rid of the read and show, let's come up with a way to convert an integer to and from a list of digits:

reversal = fromDigits . reverse . toDigits

type Digit = Integer

toDigits :: Integer -> [Digit]
toDigits = unfoldr getDigit
  where getDigit 0 = Nothing
        getDigit n = let (q,r) = n `quotRem` 10 in Just (r,q)

fromDigits :: [Digit] -> Integer
fromDigits = foldr useDigit 0
  where useDigit d m = 10*m + d

(I should caveat that we've changed the behaviour of reversal a bit. Now reversal (-12345) == -54321 where previously it returned 54321. If you have strong opinions on whether negative numbers can be palindromes, be aware).

Now expanding the definition of toDigits and fromDigits in reversal we get:

reversal = foldr useDigit 0 . reverse . unfoldr getDigit
  where getDigit 0 = Nothing
        getDigit n = let (q,r) = n `quotRem` 10 in Just (r,q)
        useDigit d m = 10*m + d

Now, foldr f b . reverse == foldl (flip f) b, so by swapping the argument order for useDigit, we can simplify this to:

reversal = foldl useDigit 0 . unfoldr getDigit
  where getDigit 0 = Nothing
        getDigit n = let (q,r) = n `quotRem` 10 in Just (r,q)
        useDigit m d = 10*m + d

The thing about foldl f c . unfoldr g is that it's really modeling a linear tail-recursive function. It uses g to unpack a value from the input, which f then combines with c. When g can't unpack any more from the input, it returns c.

We can always refactor foldl f c . unfoldr g into

foldl f c . unfoldr g == go c 
  where go c b = case g b of
          Nothing       -> c
          Just (a, b')  -> go (f c a) b'

Applying this transformation, we get

reversal = go 0
  where getDigit 0 = Nothing
        getDigit n = let (q,r) = n `quotRem` 10 in Just (r,q)
        useDigit m d = 10*m + d
        go c b = case getDigit b of
          Nothing       -> c
          Just (a, b')  -> go (useDigit c a) b'

Now we can simplify, inlining getDigit and useDigit:

reversal = go 0
  where go c 0 = c
        go c n = let (q,r) = n `quotRem` 10 in go (10*c + r) q

Which gives us a pretty elegant looking solution.

Comment and complain on reddit.

nice! fusing and inlining can make compilers write nice code too, huh.

you have a typo: reversal = toDigits . reverse . fromDigits should be the other way around.

@WillNess Thanks! Fixed.