Finding the next higher digital permutation of a number

Question

This is my solution for CodeEval challenge 44.

You are writing out a list of numbers.Your list contains all numbers with exactly Di digits in its decimal representation which are equal to i, for each i between 1 and 9, inclusive. You are writing them out in ascending order. For example, you might be writing every number with two '1's and one '5'. Your list would begin 115, 151, 511, 1015, 1051. Given N, the last number you wrote, compute what the next number in the list will be. The number of 1s, 2s, ..., 9s is fixed but the number of 0s is arbitrary.

INPUT SAMPLE:

Your program should accept as its first argument a path to a filename. Each line in this file is one test case. Each test case will contain an integer n < 10^6. E.g.

115
842
8000

OUTPUT SAMPLE:

For each line of input, generate a line of output which is the next integer in the list. E.g.

151
2048
80000

The function followingInteger takes a number in its decimal representation and returns the next higher permutation of the digits of the number. If there isn't a larger permutation of the digits, a '0' may be added to the digits:

ghci> followingInteger "123"
"132"
ghci> followingInteger "10"
"100"

The entire program can be used like this:

./ch044_solution ch044_input

where ch044_input is a file containing one integer on each line.

The code:

import Data.List (partition, sort)
import System.Environment (getArgs)

followingInteger :: String -> String
followingInteger digits
  | isSortedDesc digits = lowestPermutation ('0' : digits)
  | otherwise           = nextHigherPermutation digits

isSortedDesc :: (Ord a) => [a] -> Bool
isSortedDesc xs = all (uncurry (>=)) $ zip xs (tail xs)

lowestPermutation :: String -> String
lowestPermutation digits = let (zeros, nonZeros) = partition (== '0') digits
                               (lowestNonZeroDigit:otherDigits) = sort nonZeros
                           in  lowestNonZeroDigit : zeros ++ otherDigits

nextHigherPermutation :: String -> String
nextHigherPermutation = snd . foldr foldFun (False, "")
  where foldFun d (True, digits)  = (True, d:digits)
        foldFun d (False, digits)
          | null biggerDigits = (False, d:digits)
          | otherwise         = (True, newTail)
          where (biggerDigits, smallerDigits) = partition (> d) digits
                (swapDigit:otherDigits) = sort biggerDigits
                newTail = swapDigit : sort smallerDigits ++ (d : otherDigits)

mapFileLines :: (String -> String) -> IO ()
mapFileLines f = do
    (fileName:_) <- getArgs
    contents <- readFile fileName
    mapM_ (putStrLn . f) $ lines contents

main = mapFileLines followingInteger

I'm pretty new to Haskell, so please criticize my code in every way possible!

I'm especially interested in ways to make the code more readable!

Answer 1

First of all: your code is very readable and you seem to know your way around standard library functions, which is very important is Haskell. Good job!

A couple of suggestions:

1. A simpler isSortedDesc:

   import Data.List.Ordered (isSortedBy)
   
   isSortedDesc :: (Ord a) => [a] -> Bool
   isSortedDesc = isSortedBy (>=)
   

   Edit: Sorry, isSortedBy is not a standard function - it belongs to data-ordlist-0.2. I'd implement it in a straightforward recursive manner:

   isSortedDesc :: (Ord a) => [a] -> Bool
   isSortedDesc (x:y:xs') = x>=y && isSortedDesc (y:xs')
   isSortedDesc _ = True
   

2. foldFun:

   In foldFun, try to make the arguments more understandable. You can add a type signature, name the arguments or add a comment. For example, what is the purpose of the boolean argument?

   Another thing: nextHigherPermutation has two execution steps - find a digit we can swap, and then just copy the rest of the string. Personally I'm not a fun of the idea of passing extra information to fold (the boolean argument) and then discarding it. Instead, consider splitting it to two seperate functions - for example, one that finds the swap digit and another that performs the swap.