Haskell functions to extract and reverse integers hiding in strings

Question

There may not be a "right" way to do it, but I'm inexperienced in functional programming. I'd like some feedback on how the code can be written in a more idiomatic way.

Here it is:

import Data.Maybe (fromJust, isJust)
sepInt n = if n >= 10
 then ( sepInt ( n `div` 10 ) ) ++ ((n `mod` 10):[])
 else n `mod` 10 : []
getStuff (x:xs) = if isJust x || null xs
 then fromJust x
 else getStuff xs
base10IntTOstring num =
 let chars = [ (1, '1'), (2, '2'), (3, '3'), (4, '4'), (5, '5'), (6, '6'), (7, '7'), (8, '8'), (9, '9'), (0, '0') ]
 numbahs = sepInt num in
 map getStuff ( map (\a -> (map (\(x,y) -> if a == x then Just y else Nothing ) chars ) ) numbahs )
charTOBase10Int char =
 let chars = [ ('1', 1), ('2', 2), ('3', 3), ('4', 4), ('5', 5), ('6', 6), ('7', 7), ('8', 8), ('9', 9), ('0', 0) ] in
 let charslist = ( map (\(a,x) -> if char == a then Just x else Nothing) chars ) in
 getStuff charslist
stringTOBase10Int string =
 let integers = ( map charTOBase10Int string ) in
 let multByBase i (x:xs) = if null xs
 then (10^i)*x
 else (10^i)*x + multByBase ( i-1 ) xs
 in multByBase ( (length integers)-1 ) integers

It also reverses integers.

sepInt n = if n >= 10
 then ( sepInt ( n `div` 10 ) ) ++ ((n `mod` 10):[])
 else n `mod` 10 : []
reverseInteger string =
 let integers = sepInt string in
 let multByBase i (x:xs) = if null xs
 then (10^i)*x
 else (10^i)*x + multByBase ( i-1 ) xs
 in multByBase ( (length integers) - 1 ) integers

• Gabriella Gonzalez: Also, I highly recommend that when you share code with other people, whether on Stack Overflow or otherwise, that you annotate your functions with types. It makes it much easier for other people to review your code.

Answer 1

Let's take one function at a time, until we're all done.

sepInt

sepInt n = if n >= 10
 then ( sepInt ( n `div` 10 ) ) ++ ((n `mod` 10):[])
 else n `mod` 10 : []

First things first: you'll definitely want to learn a bit about precedence! Normally I'm in favor of adding some unnecessary parentheses if it helps disambiguate a strange situation or if the operators involved aren't often mixed, but too many of them can get in the way of readability. Also, take advantage of that sweet syntactic sugar for lists that the language provides! So iteration one of this function is

sepInt n = if n >= 10
 then sepInt (n `div` 10) ++ [n `mod` 10]
 else [n `mod` 10]

Now, as we all know, building up a linked list by repeatedly appending to the end is a bit inefficient. Probably for such small lists as you'll be using in test cases here it won't matter, but it's a good idea to get in the habit of paying attention to some of the easiest stuff, so let's try to improve this a bit. We have a choice here: either we can keep the interface of this function as-is, that is, always output a list in the right order, or we can choose to change the interface, and change all the call-sites of this function. I think for this case we can keep the interface. The idea we'll take is to build up the list backwards, then reverse it at the very end. The name go is traditional for local workers.

sepInt = reverse . go where
 go n = if n >= 10
 then [n `mod` 10] ++ go (n `div` 10)
 else [n `mod` 10]

There's something a bit funny about this base case to me. It seems like it's not the most basic one you could choose. If we let the "loop" run one more time...

sepInt = reverse . go where
 go n = if n > 0
 then [n `mod` 10] ++ go (n `div` 10)
 else []

There's a few things I find more satisfying about this: our base-case input is 0, a common base for Integers; our base-case output is [], a common base for []s; and there's no duplicated code in the two branches of the if. Finally, I think I'd choose to replace the if-then-else with a pattern match, noting however that this function has a slightly different behavior for negative numbers. Since we were never really doing the right thing for negative numbers, this doesn't bother me too much.

sepInt = reverse . go where
 go 0 = []
 go n = [n `mod` 10] ++ go (n `div` 10)

If we're feeling fancy, we can choose to use divMod instead of two separate calls to div and mod; and we can unroll the definition of (++); but I think neither of these is terribly important. Nevertheless, they're idiomatic, so:

sepInt = reverse . go where
 go 0 = []
 go n = let (d, m) = n `divMod` 10 in m : go d

Okay, let's check our work. We already know that the final thing works differently for negative numbers, so let's only check non-negative ones.

*Main Test.QuickCheck> quickCheck (\(NonNegative n) -> sepInt n == sepInt' n)
*** Failed! Falsifiable (after 2 tests): 
NonNegative {getNonNegative = 0}

Whoa, whoops! Can you figure out which refactoring above was the culprit? =)

Now we have to decide whether we like the old behavior better or the new one. I think in this particular case we should like the old behavior better, since the goal is to show a number, and we'd like 0 to show up as "0" rather than as "". It's a bit ugly, but we can special-case it. Since we like our future selves, we'll leave ourselves a note about this, too.

-- special case for a human-readable 0
sepInt 0 = [0]
sepInt n = reverse . go $ n where
 go 0 = []
 go n = let (d, m) = n `divMod` 10 in m : go d

Now the test passes:

*Main Test.QuickCheck> quickCheck (\(NonNegative n) -> sepInt n == sepInt' n)
+++ OK, passed 100 tests.

getStuff

getStuff (x:xs) = if isJust x || null xs
 then fromJust x
 else getStuff xs

This name sure leaves something to be desired! And it leaves another important thing to be desired, too: there's lots of inputs where it just crashes. Nasty! It turns out that you never call it on inputs of that form later, but totality is another good habit that you should get yourself into. It's just another tool in the mature programmer's defensive programming toolbelt. In our case, we'll want to handle cases like [], or [Nothing], or [Nothing, Nothing], etc. where there's no good answer to return. What should we return if that happens?

One simple and quite common choice is to change our type from

getStuff :: [Maybe a] -> a

to

getStuff :: [Maybe a] -> Maybe a

but I think that's a bit short-sighted. Ignoring for the moment the inputs we know we're going to call this thing on, we've observed already that there's times when there's no good answer to return, and there's times when there is a good answer to return, so Maybe a seems like a good start, but there's also times when there are two good answers -- or more! So let's use a type that reflects this scenario instead:

getStuff :: [Maybe a] -> [a]

It's not too hard to fix up the code. First we'll just fix the type errors:

getStuff (x:xs) = if isJust x || null xs
 then [fromJust x]
 else getStuff xs

This isn't obviously better, since it still fails in all the same situations it used to fail, and it never returns multiple answers. So we should differentiate the two cases that lead us to the then branch:

getStuff (x:xs) = if isJust x
 then fromJust x : if null xs
 then []
 else getStuff xs
 else getStuff xs

Now, we have this if null xs branch primarily because getStuff still isn't total (it can't handle an empty input list). Instead of protecting ourselves from calling getStuff in this case, we should just let getStuff deal with empty lists correctly. So:

getStuff [] = []
getStuff (x:xs) = if isJust x
 then fromJust x : getStuff xs
 else getStuff xs

Actually, using isJust and fromJust is also a code smell, for the same reason as the rest of the changes so far: fromJust is partial. Instead of protecting ourselves from calling fromJust on inputs it can't handle, we should write our code in a way that avoids partial functions. Here's how:

getStuff [] = []
getStuff (Just x : xs) = x : getStuff xs
getStuff (Nothing : xs) = getStuff xs

(I've added a little creative whitespace to show parallels between the branches.) The only thing I'd change now is to pick a better name. For example, catMaybes might be an okay name for this. I'll mention one more thing, which is that this can also be implemented quite beautifully as a list comprehension:

catMaybes xs = [x | Just x <- xs]

By the way, this function is available from Data.Maybe.

base10IntTOstring

base10IntTOstring num =
 let chars = [ (1, '1'), (2, '2'), (3, '3'), (4, '4'), (5, '5'), (6, '6'), (7, '7'), (8, '8'), (9, '9'), (0, '0') ]
 numbahs = sepInt num in
 map getStuff ( map (\a -> (map (\(x,y) -> if a == x then Just y else Nothing ) chars ) ) numbahs )

There are better ways to construct that lookup table! For example, I might choose

chars = zip [0..9] ['0'..'9']

(If you haven't seen zip before, I encourage you to try to code it up yourself! Then check the Report and compare answers.) Additionally, we're going to have to change things up a little, since we've changed how getStuff works and base10IntTOstring calls getStuff. Before, we had getStuff :: [Maybe a] -> a and hence map getStuff :: [[Maybe a]] -> [a]. Now, we have catMaybes :: [Maybe a] -> [a] and hence map catMaybes :: [[Maybe a]] -> [[a]]. Since we expect each of the lists in the output of that to be singleton lists, we can smash them all together with concat:

base10IntTOstring num =
 let chars = zip [0..9] ['0'..'9']
 numbahs = sepInt num in
 concat (map catMaybes ( map (\a -> (map (\(x,y) -> if a == x then Just y else Nothing ) chars ) ) numbahs ))

Actually, this whole process at the very end is quite roundabout! If you squint, it looks like what we're really trying to implement here is a little function

lookupList :: Eq k => [(k, v)] -> k -> [v]

which we can use to index into our lookup table with the digits of our integer. So let's try to write this directly! Taking a cue from the final implementation of catMaybes above, we can write

lookupList table k = [v | (k', v) <- table, k == k']

Now our implementation can look like this:

base10IntTOstring num =
 let chars = zip [0..9] ['0'..'9']
 numbahs = sepInt num in
 concat (map (lookupList chars) numbahs)

In fact, there's even a function concatMap that squashes those two things together. Veteran Haskellers will prefer to spell this function in its infix, polymorphic form as (>>=)

base10IntTOstring num =
 let chars = zip [0..9] ['0'..'9']
 numbahs = sepInt num in
 numbahs >>= lookupList chars

though this spelling is optional. In fact, everything is short enough now that I would even feel comfortable inlining the definitions:

base10IntTOstring num = sepInt num >>= lookupList (zip [0..9] ['0'..'9'])

My only complaint now is the name, for two reasons. The first is that string isn't capitalized, which is inconsistent with the naming of the remainder of the file. The other one is more of a philosophical one: our input is an integer, not a base-ten integer. If anything, the base-ten-ness is being imposed on the output. So:

intTOBase10String num = sepInt num >>= lookupList (zip [0..9] ['0'..'9'])

Let's test it:

*Main Test.QuickCheck> quickCheck (\n -> base10IntTOstring n == intTOBase10String n)
+++ OK, passed 100 tests.

(By the way, a variant of lookupList that I have always felt has the wrong type, lookup, is available from Prelude.)

Finally, I would be remiss without pointing out that there are several good functions that already exist for doing conversions like this:

*Main Test.QuickCheck> let checkPosBase10 f = quickCheck (\(NonNegative n) -> f n == intTOBase10String n)
*Main Test.QuickCheck> checkPosBase10 show
+++ OK, passed 100 tests.
*Main Test.QuickCheck Numeric Data.Char> checkPosBase10 (\n -> showIntAtBase 10 intToDigit n "")
+++ OK, passed 100 tests.

The difference here is that showIntAtBase can be used for any base, and show is specific to base 10.

charTOBase10Int

charTOBase10Int char =
 let chars = [ ('1', 1), ('2', 2), ('3', 3), ('4', 4), ('5', 5), ('6', 6), ('7', 7), ('8', 8), ('9', 9), ('0', 0) ] in
 let charslist = ( map (\(a,x) -> if char == a then Just x else Nothing) chars ) in
 getStuff charslist

Actually, most of the changes we made to base10IntTOstring can be done here, as well. In the interest of totality, we'll change the type, too; it will return a [Char] (which we happen to know will be a singleton list, if anything) instead of a Char.

base10CharTOInt char = lookupList (zip ['0'..'9'] [0..9]) char

It's common in cases like this where the trailing arguments to the function you're defining are also trailing arguments to a function in the definition to omit the arguments entirely. The technical term for this is eta reduction, I think. Whether you choose to do this yourself is primarily a stylistic choice.

base10CharTOInt = lookupList (zip ['0'..'9'] [0..9])

The test for this one is a bit complicated; since the old implementation is partial, we have to restrict ourselves to those inputs that work.

*Main Test.QuickCheck> quickCheck (\n -> n >= '0' && n <= '9' ==> [charTOBase10Int n] == base10CharTOInt n)
*** Gave up! Passed only 67 tests.

The report here says that it passed the test, but that QuickCheck didn't run as many tests as it wanted to because most of the random inputs it generated weren't in the desired range. (In fact, perhaps it's questionable to use QuickCheck at all for this, since there's only ten inputs of interest anyway!)

By the way, this function (a partial version! boooo) exists also in Data.Char:

*Main Test.QuickCheck Data.Char> quickCheck (\n -> n >= '0' && n <= '9' ==> charTOBase10Int n == digitToInt n)
*** Gave up! Passed only 54 tests.

stringTOBase10Int

stringTOBase10Int string =
 let integers = ( map charTOBase10Int string ) in
 let multByBase i (x:xs) = if null xs
 then (10^i)*x
 else (10^i)*x + multByBase ( i-1 ) xs
 in multByBase ( (length integers)-1 ) integers

We first need to fix up some typing issues, since we've changed the interface to base10CharTOInt and this is a caller. As before, we can do that just by putting in a concat; as before, we'll spell the combination of concat and map as (>>=).

stringTOBase10Int string =
 let integers = string >>= base10CharTOInt in
 let multByBase i (x:xs) = if null xs
 then (10^i)*x
 else (10^i)*x + multByBase ( i-1 ) xs
 in multByBase ( (length integers)-1 ) integers

As with sepInt waaaay back at the beginning, I find the choice of base case a bit odd. Let's try the trick from before of letting the "loop" run one more iteration (and this time hopefully the refactoring isn't wrong!).

stringTOBase10Int string =
 let integers = string >>= base10CharTOInt in
 let multByBase i [] = 0
 multByBase i (x:xs) = (10^i)*x + multByBase ( i-1 ) xs
 in multByBase ( (length integers)-1 ) integers

Also, let's eliminate unnecessary parentheses.

stringTOBase10Int string =
 let integers = string >>= base10CharTOInt in
 let multByBase i [] = 0
 multByBase i (x:xs) = 10^i*x + multByBase (i-1) xs
 in multByBase (length integers-1) integers

Now, I wonder whether recomputing the power of ten each time is really the right thing to do. One thing we could do is to use 10^(length integers - 1) and divide by 10 in each recursion. But division is slow, so let's take another plan: instead of computing the length of the list explicitly, let's do it implicitly by having multByBase also compute the appropriate power of ten.

stringTOBase10Int string =
 let integers = string >>= base10CharTOInt in
 let multByBase [] = (1, 0)
 multByBase (x:xs) = let (pow, n) = multByBase xs in (pow*10, pow*x+n)
 in snd (multByBase integers)

This now has the magical special form of recursion that can be turned into a foldr. Let's do so! See if you can spot where each piece of code from the above ends up in the below.

stringTOBase10Int string =
 let integers = string >>= base10CharTOInt in
 snd (foldr (\x (pow, n) -> (pow*10, pow*x+n)) (1, 0) integers)

Personally, I often prefer where to let, and the foldr is complicated enough that I feel like it should be named, so I'd write it as follows. But this is an aesthetic choice that you may or may not agree with.

stringTOBase10Int string = snd (go integers) where
 integers = string >>= base10CharTOInt
 go = foldr (\x (pow, n) -> (pow*10, pow*x+n)) (1, 0)

And finally, fix up the name:

base10StringTOInt string = snd (go integers) where
 integers = string >>= base10CharTOInt
 go = foldr (\x (pow, n) -> (pow*10, pow*x+n)) (1, 0)

As usual, the tests. Since the old function was pretty partial, we'll arrange to have inputs it knows how to handle, though our new one tries to give an answer even when you feed it garbage.

*Main Test.QuickCheck> quickCheck (\(NonNegative n) -> base10StringTOInt (show n) == stringTOBase10Int (show n))
+++ OK, passed 100 tests.

By the way, there are functions for this available, too; take a look at reads from Prelude (base-10 specific) and readInt from Numeric (pick your favorite base). I won't try to write tests here, because the types of these functions are more informative (and more correct in many ways).

Final result

Barring the reuse of already-written functions, here's the final versions of all the functions.

sepInt 0 = [0]
sepInt n = reverse . go $ n where
 go 0 = []
 go n = let (d, m) = n `divMod` 10 in m : go d
lookupList table k = [v | (k', v) <- table, k == k']
intTOBase10String num = sepInt num >>= lookupList (zip [0..9] ['0'..'9'])
base10CharTOInt = lookupList (zip ['0'..'9'] [0..9]) 
base10StringTOInt string = snd (go integers) where
 integers = string >>= base10CharTOInt
 go = foldr (\x (pow, n) -> (pow*10, pow*x+n)) (1, 0)

Keep at it; I look forward to many more questions from you!

Answer 2

Ok, so here are some comments while I'm fixing up your code:

• In sepInt, you can combine div and mod into one computation using quotRem

• An efficient trick for building up a list in the "wrong order" is to build it up in reverse and then reverse it.

• Don't write partial functions like getStuff. That usually indicates a flaw in your code. getStuff is partial because the list could be empty or full of Nothings, in which case there is no way you could possibly retrieve an a from it. Idiomatic Haskell code should never need partial functions.

• You can replace base10IntTOstring with the show function, which converts any integer to its String representation. However, if you still want to write the function yourself without using show, then it's much more efficient to use the ord and chr functions from Data.Char and do simple arithmetic to convert them to to the equivalent ASCII characters.

• You shouldn't check things using functions like null or isJust. Use case statements to pattern match on them.

For example, this is NOT idiomatic Haskell:

foo :: Maybe Int -> Int
foo m = if (isJust m)
 then fromJust m
 else 0

Instead you would do:

foo = case m of
 Just n -> n
 Nothing -> 0

Same thing with list operations. You do NOT do this:

bar :: [Int] -> Int
bar xs = if (null xs)
 then head xs
 else 0

Instead you do this:

bar xs = case xs of
 x:_ -> x
 [] -> 0

case statements are more efficient, safer, and they are statically checked by the compiler to make sure you don't extract a variable on the wrong branch.

• When you combine a list into a single value, you probably want a strict left fold like foldl'.

When I combine all of those fixes, I get this:

import Data.Char (chr, ord)
import Data.List (foldl')
sepInt :: Int -> [Int]
sepInt n = reverse (go n)
 where
 go n = if n >= 10
 then let (q, r) = quotRem n 10 in r:go q
 else [n]
base10IntTOstring :: Int -> [Char]
base10IntTOstring = map (\n -> chr (ord '0' + n)) . sepInt
charTOBase10Int :: Char -> Int
charTOBase10Int c = ord c - ord '0'
stringTOBase10Int :: [Char] -> Int
stringTOBase10Int cs = foldl' step 0 (map charTOBase10Int cs)
 where
 step acc elem = 10 * acc + elem

Answer 3

The other answers are excellent, I just want to point out a handy way to split positive numbers to digits:

sepInt = reverse . map (`mod` 10) . takeWhile (> 0) . iterate (`div` 10)