First of all, it's great that you've used type signatures. So let's have a look at the contents of your functions.
Use divMod
instead of div
and mod
In toDigits
, you both div
and mod
x
by 10
. However, there's a function that combines them both: divMod
. With that in mind, we can write
toDigits :: Integer -> [Integer]
toDigits x
| x <= 0 = []
| divBy10 < 10 = [divBy10, remainder]
| otherwise = toDigits divBy10 ++ [remainder]
where (divBy10, remainder) = x `divMod` 10
Avoid left-recursion on ++
However, your function is currently non-optimal. If you use x ++ [y]
repeatedly, you end up with \$\mathcal O(n^2) \$ instead of \$\mathcal O(n) \$, as ++
is \$\mathcal O(n) \$ (where \$n\$ denotes the length of the first list).
It's easier to write toDigitsRev
:
toDigitsRev :: Integer -> [Integer]
toDigitsRev x = case x `divMod` 10 of
(0, 0) -> []
(0, m) -> [m]
(d, m) -> m : toDigitsRev d
The case
is just a matter of preference, you can continue to use your guards. Note that we now use (:)
, which is alwas \$\mathcal O(1) \$. Our toDigits
is now only
toDigits :: Integer -> [Integer]
toDigits = reverse . toDigitsRev
Use simpler patterns where possible
Your patterns in doubleEveryOther
are a little bit contrived. If we look closely, we can see that we always return the input, except for the two-element case. Let's reorder the patterns first to see that:
doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther xs = reverse $ doubleEveryOther' (reverse xs)
where doubleEveryOther' (x:y:xs) = [x, y*2] ++ doubleEveryOther' xs
doubleEveryOther' [] = []
doubleEveryOther' (x:[]) = [x]
doubleEveryOther' (x:y:[]) = [x, y*2]
Now the first pattern handles both (x:y:xs)
and (x:y:[])
, so we can get rid of the last pattern:
doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther xs = reverse $ doubleEveryOther' (reverse xs)
where doubleEveryOther' (x:y:xs) = [x, y*2] ++ doubleEveryOther' xs
doubleEveryOther' [] = []
doubleEveryOther' (x:[]) = [x]
In our empty and single-element pattern we return our input, so we can combine both variants into a single pattern:
doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther xs = reverse $ doubleEveryOther' (reverse xs)
where doubleEveryOther' (x:y:xs) = x : y*2 : doubleEveryOther' xs
doubleEveryOther' xs = xs
Also, it's common to use short names for workers, so let's call the worker go
:
doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther = reverse . go . reverse
where go (x:y:xs) = x : y*2 : go xs
go xs = xs
The point-free definition of doubleEveryOther
is a matter of preference.
Other remarks
sumDigits
and validate
are fine, although I'd write them as follows
sumDigits :: [Integer] -> Integer
sumDigits = sum . map (sum . toDigits)
validate :: Integer -> Bool
validate x = checksum == 0
where
checksum = sumDigits (doubleEveryOther $ toDigits x) `mod` 10
That's only a matter of personal preference, though. The compiler will change map f $ map g
to map (f . g)
automatically, so your variant of sumDigits
didn't traverse the list twice.