# Number base manipulation in Haskell

I am picking up good Haskell practices!

In this instance, I wanted to pick a file which contains a title in the first line and then every line is a string.

Each string represents a number in base equal to the number of distinct characters that appear on the string, but we do not know what characters correspond to each digit.

We want to find out the difference between the max and min number a string could represent, with the added restriction that a number cannot have leading 0s.

I feel like my code is quite complicated for such a simple task. Can I get any pointers on how to improve it so its more readable and elegant?

import qualified Data.Map as Map
import Data.List
import Data.Maybe

main = do
contents <- (tail . lines) <$> readFile "submitInput" :: IO [String] let input = contents :: [String] let result = max_range <$> input
let decorated_result = ["Case #" ++ show i ++ ": " ++ show s | (i,s) <- zip [1..] result]
writeFile "output.txt" $unlines$ decorated_result

-- Computes the difference between the max and min possible decoding
max_range word = max_decoding word - min_decoding word

-- Computes the minimal possible decoding of word
min_decoding :: String -> Integer
min_decoding word =
let number = fix_decoding $min_aux word (Map.empty :: Map.Map Char Integer) 0 in base_conversion (toInteger . length . nub$ number) $catMaybes number -- The decodification cannot have leading zeros fix_decoding :: [Maybe Integer] -> [Maybe Integer] fix_decoding [] = [] fix_decoding (Just 0:ds) = Just 1 : fix_decoding ds fix_decoding (Just 1:ds) = Just 0 : fix_decoding ds fix_decoding (d:ds) = d : fix_decoding ds min_aux :: [Char] -> Map.Map Char Integer -> Integer -> [Maybe Integer] min_aux [] _ _ = [] min_aux (c:cs) map next | c Map.member map = Map.lookup c map : min_aux cs map next | otherwise = Just next : min_aux cs (Map.insert c next map) (next + 1) -- Computes the maximal possible decoding of word max_decoding :: String -> Integer max_decoding word = let number = max_aux word (Map.empty :: Map.Map Char Integer) ((toInteger . length . nub$ word)-1)
in base_conversion (toInteger . length . nub $number)$ catMaybes number

max_aux :: [Char] -> Map.Map Char Integer -> Integer -> [Maybe Integer]
max_aux [] _ _ = []
max_aux (c:cs) map next
| c Map.member map    = Map.lookup c map : max_aux cs map next
| otherwise             = Just next : max_aux cs (Map.insert c next map) (next - 1)

-- Interprets a list of digits as a number in a given base
base_conversion :: Integer -> [Integer] -> Integer
base_conversion base []     = 0
base_conversion base (d:ds) = d * base ^ (length ds) + base_conversion base ds


# Type signatures and naming

While it's good practice to use type signatures on top-level bindings, it's usually not necessary in expressions unless type classes are involved. For example, the two following lines don't need type signatures:

contents <- (tail . lines) <$> readFile "submitInput" :: IO [String] let input = contents :: [String]  readFile always returns IO String, and tail . lines always changes a String into a [String]. Furthermore, input = contents is a nop, so it's not clear why it's there. Next, you usually use camelCase instead of snake_case in names in Haskell and hide the functionality in local bindings if you don't want to reuse functions, e.g. min_decoding :: String -> Integer min_decoding word = base_conversion (toInteger . length . nub$ number) $catMaybes number where number = fix_decoding$ min_aux word Map.empty 0
min_aux = ...


Feel free to use let … in … instead. By the way, max_range is missing a type signature.

# Recursion and Horner's method

Your base_conversion isn't really optimal. We can use Horner's method to get rid of length. For this we need a helper:

baseConversion :: Num a => a -> [a] -> a
baseConversion base = go 0
where
go acc []     = acc
go acc (d:ds) = go (acc * base + d) ds


You can verify that this yields the same result:

baseConversion 10 [1,2,3,4,5]
= go 0 [1,2,3,4,5]
= go (0  * 10 + 1) [2,3,4,5]
= go (1  * 10 + 2) [3,4,5]
= go (12 * 10 + 3) [4,5]
= go (123 * 10 + 4) [5]
= go (1234 * 10 + 5) = 12345


But there's already a function for this, foldl':

baseConversion :: Num a => a -> [a] -> a
baseConversion base = foldl' (\acc x -> acc * base + x) 0


Either way, we got rid of the ^ (length ds) part.

# Don't repeat yourself

Both min_decoding and max_decoding look very similar, and so do max_aux and min_aux.

We're repeating a lot of logic here. So instead, let us use a single function:

toDigit :: (Integer -> Integer) -> [Char] -> Map.Map Char Integer -> Integer -> [Maybe Integer]
toDigit _    []     _   _    = []
toDigit step (c:cs) m next =
| c Map.member m    = Map.lookup c m : toDigit cs m next
| otherwise           = Just next : toDigit cs (Map.insert c next m) (step next)


Now

min_aux = toDigit (+1)
max_aux = toDigit (subtract 1)


# Use appropriate types

But toDigit is still not optimal. We never return Nothing in our list. Therefore, there is no reason to use [Maybe Integer] as a result type:

toDigit :: (Integer -> Integer) -> [Char] -> Map.Map Char Integer -> Integer -> [Integer]
toDigit _    []     _   _    = []
toDigit step (c:cs) m next = case Map.lookup c m of
Just digit -> digit : toDigit step cs map next
Nothing    -> next  : toDigit step cs (Map.insert c next m) (step next)


While we're at it, you probably want to replace Integer with Int for the digits.