6
\$\begingroup\$

I'm a beginner to Haskell (intermediate in web-dev stuff and JavaScript) and I'm not really sure what I could do better for Homework 1 of CIS194 that I'm taking online.

The problem statement is as follows (shortened):

Validate a credit card number by the following steps:

  1. Double the value of every second digit from the right
  2. Take the sum of the digits of the new values
  3. Check whether the sum modulo 10 is 0.

Write the functions toDigits, toDigitsRev and doubleEveryOther for the first task, sumDigits for the second, and validate for the third.

toDigits :: Integer -> [Integer]
toDigits x
    | x <= 0       = []
    | divBy10 < 10 = [divBy10, remainder]
    | otherwise    = toDigits divBy10 ++ [remainder]
    where remainder = x `mod` 10
        divBy10   = x `div` 10

toDigitsRev :: Integer -> [Integer]
toDigitsRev x = reverse (toDigits x)

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther xs = reverse $ doubleEveryOther' (reverse xs)
    where   doubleEveryOther' []       = []
            doubleEveryOther' (x:[])   = [x]
            doubleEveryOther' (x:y:[]) = [x, y*2]
            doubleEveryOther' (x:y:xs) = [x, y*2] ++ doubleEveryOther' xs

sumDigits :: [Integer] -> Integer
sumDigits xs = sum $ map sum $ map toDigits xs

validate :: Integer -> Bool
validate x = ((sumDigits (doubleEveryOther (toDigits x))) `mod` 10) == 0
\$\endgroup\$
  • \$\begingroup\$ What is your main concern? \$\endgroup\$ – Mast Jul 28 '18 at 12:04
  • \$\begingroup\$ Welcome to Code Review. Your code contains currently two tasks: credit card validation, as well as the towers of Hanoi. Your question would would be better received if you split it into two with short problem statements. \$\endgroup\$ – Zeta Jul 28 '18 at 12:05
  • 5
    \$\begingroup\$ I took the curtesy to remove the towers of Hanoi and include a problem statement. Please post a new question for the towers and include a problem statement there. \$\endgroup\$ – Zeta Jul 28 '18 at 12:12
  • \$\begingroup\$ Thanks Zeta, I'll try and add a problem statement next time I ask a question. \$\endgroup\$ – Joshua Rowe Jul 28 '18 at 13:02
  • 1
    \$\begingroup\$ As an aside, this is called the Luhn algorithm \$\endgroup\$ – CSM Jul 28 '18 at 16:46
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you very much! I'll go implement and synthesise these changes now \$\endgroup\$ – Joshua Rowe Jul 28 '18 at 13:03
  • \$\begingroup\$ I'm kinda just curious tho, with the way that you refactored the pattern matches in doubleEveryOther' , I feel like theres a case for mine being more explicit and readable, whereas the doubleEveryOther' xs = xs doesn't really explain whats going on that well. I dunno \$\endgroup\$ – Joshua Rowe Jul 28 '18 at 13:12
  • 2
    \$\begingroup\$ go is zipWith (*) (cycle [1,2]). \$\endgroup\$ – Gurkenglas Jul 29 '18 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.