4
\$\begingroup\$

I am working through UPenn CIS 194: Introduction to Haskell (Spring 2013). Since I am not able to take the course for real I am asking for CR (feedback) as it could be from teacher in that course.

HW1 - Validating Credit Card Numbers - Full description

A shortened problem statement:

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.

toDigitsRev :: Integer -> [Integer]
toDigitsRev 0 = []
toDigitsRev n
  | n < 0 = []
  | n < 10 = [n]
  | otherwise = n `mod` 10 : toDigitsRev (n `div` 10)

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

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther [] = []
doubleEveryOther (x:[]) = [x]
doubleEveryOther (x:y:zx)
  | length (x:y:zx) `mod` 2 == 0 = 2*x : y : doubleEveryOther zx
  | otherwise = x : 2*y : doubleEveryOther zx

sumDigits :: [Integer] -> Integer
sumDigits [] = 0
sumDigits (x:[]) = x
sumDigits (x:xs)
  | x < 10 = x + sumDigits xs
  | otherwise = sumDigits (toDigits x) + sumDigits xs

validate :: Integer -> Bool
validate 0 = False
validate n = (sumDigits (doubleEveryOther (toDigits n))) `mod` 10 == 0

type Peg = String
type Move = (Peg, Peg)
hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]
hanoi n a b c
  | n == 0 = []
  | n == 1 = (a, b) : hanoi 0 a b c
  | otherwise =  hanoi (n-1)  a c b ++ [(a, b)] ++  hanoi (n-1) c b a
\$\endgroup\$
3
\$\begingroup\$

toDigitsRev

You can combine these two cases:

toDigitsRev 0 = []
toDigitsRev n
  | n < 0 = []

I think having one case makes the code clearer:

toDigitsRev
  | n <= 0 = []

doubleEveryOther

You are correct to write doubleEveryOther as a recursive function, but ... you don't need to call length on every call!

Think of a way to writing doubleEveryOther but with calling length at most once.

length and reverse

As you become more familiar with Haskell you learn that you should be wary of calling length and reverse on lists. In this case it is not a big deal because the lists involved are very short, but, in general, if you find yourself using these functions a lot it's an indication that you are using the wrong data structure.

As a bonus exercise, see if you can figure out a way to implement the validate function without using length or reverse.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the input, I will try to get rid of length \$\endgroup\$ – drets Sep 17 '15 at 8:54
  • \$\begingroup\$ Updated doubleEveryOther is available at: public gist file \$\endgroup\$ – drets Sep 17 '15 at 18:37
4
\$\begingroup\$

You're on the right track, I think. If I had to pick one general criticism, it would be to watch out for redundant special cases.

In my opinion, the exercise guides you towards making an unnecessary complication in toDigits and doubleEveryOther. Actually, the list of digits from right to left, as produced by toDigitsRev, is the more natural representation to work with. If you work with the list in left-to-right order, then doubleEveryOther needs to look ahead to see whether the list has an odd or even digit count, which is awkward. Therefore, if given free reign, I'd define a doubleEveryOther' that expects right-to-left input instead.

toDigitsRev does not need special cases for 0 and for n < 10. Instead of calling div and mod, use the divMod function to capture both pieces of information from the same calculation.

toDigitsRev :: Integer -> [Integer]
toDigitsRev n
  | n <= 0    = []
  | otherwise = m : toDigitsRev d
  where
    (d, m) = n `divMod` 10

As mentioned above, we can simplify doubleEveryOther by working right-to-left:

-- Doubles the second, fourth, sixth… numbers in the list
doubleEveryOther' :: [Integer] -> [Integer]
doubleEveryOther' (x:y:zs) = x : 2 * y : doubleEveryOther' zs
doubleEveryOther' (x:[])   = [x]
doubleEveryOther' []       = []

You don't need a case for sumDigits (x:[]) — it's already covered by sumDigits (x:xs), where xs is the empty list. The way you wrote it is fine, but personally I'd prefer to write it as sum . map sumDigits' so that you can see at a glance that it's performing a sum of some transformed values.

sumDigits :: [Integer] -> Integer
sumDigits = sum . map sumDigits'
  where
    sumDigits' n
      | n < 10    = n
      | otherwise = sumDigits $ toDigitsRev n

The validate function does not need a special case for 0. It's also more idiomatic to set up a "pipeline" of function calls using $ than to use nested parentheses.

validate :: Integer -> Bool
validate n = 0 == (sumDigits $ doubleEveryOther' $ toDigitsRev n) `mod` 10
\$\endgroup\$

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.