import Data.Char
import Data.List

digitRangeToRegex :: Integer -> Integer -> String
digitRangeToRegex min max
    | min == max = digit min : ""
-- uncomment if you want \d instead of [0-9]
--    | min == 0 && max == 9 = "\\d"
    | min >= 10 || max <= 9 = "[" ++ rangeToStr (digit min) (digit max) ++ "]"
    | otherwise = "[" ++ rangeToStr (digit min) '9' ++ rangeToStr 'a' (digit max) ++ "]"
    where
        rangeToStr min max
            | min == max = min : ""
            | otherwise = min : '-' : max : ""
        digit d
            | d >= 0 && d <= 9 = chr (ord '0' + fromIntegral d)
            | d < 36 = chr (ord 'a' + fromIntegral d - 10)

numberRangeToRegex :: Integer -> Integer -> Integer -> String
numberRangeToRegex base min max
    | min == 0 && max == 0 = "0"
    | cmin == cmax = intercalate "|" $ map formatRanges $ step dmin dmax
    | otherwise = intercalate "|" $
        (map formatRanges $ step dmin (replicate cmin (base-1))) ++
        (if cmin + 1 < cmax then [digitRangeToRegex 1 (base - 1) ++ digitRangeToRegex 0 (base-1) ++ formatCount cmin (cmax-2)] else []) ++
        (map formatRanges $ step (1 : replicate (cmax-1) 0) dmax)
    where
        digits 0 = [0]
        digits n = reverse $ map (`mod` base) $ takeWhile (>0) $ iterate (`div` base) n
        dmin = digits min
        dmax = digits max
        cmin = length dmin
        cmax = length dmax
        step [] [] = [[]]
        step (a:as) (b:bs) =
            if a == b then
                prepend a $ step as bs
            else
                (if zeroHead then [] else prepend a $ step as nines) ++
                (if na > nb then [] else [(na, nb) : replicate (length as) (0, base-1)]) ++
                (if nineTail then [] else prepend b $ step zeros bs)
            where
                suffixLen = length as
                zeroHead = all (== 0) as
                nineTail = all (== base-1) bs
                na = if zeroHead then a else a+1
                nb = if nineTail then b else b-1
                zeros = replicate suffixLen 0
                nines = replicate suffixLen (base-1)
                prepend x = map ((x, x):)
        formatRanges = concatMap formatGroup . group . dropWhile (== (0,0)) where
            formatGroup [(min, max)] = digitRangeToRegex min max
            formatGroup xs@((min, max) : _)
                | min == max = concat $ replicate (length xs) $ digitRangeToRegex min max
                | otherwise = digitRangeToRegex min max ++ "{" ++ show (length xs) ++ "}"
        formatCount min max
            | min == 1 && max == 1 = ""
            | min == max = "{" ++ show min ++ "}"
            | otherwise = "{" ++ show min ++ "," ++ show max ++ "}"

main = putStrLn $ numberRangeToRegex 10 42 100500