hw1/credit-card.hs

   1 {-# OPTIONS_GHC -Wall #-}
   2 module CreditCard where
   3
   4 {-| reverse list of the digits in a given number n.
   5 >>> toDigitsRev 1234
   6 [4,3,2,1]
   7 >>> toDigitsRev 0
   8 []
   9 >>> toDigitsRev (-20)
  10 []
  11 -}
  12
  13 toDigitsRev :: Integer -> [Integer]
  14 toDigitsRev n | n <= 0 = []
  15            | n < 10 = [n]
  16            | otherwise = let (d, m) = n `divMod` 10 in
  17                          m : toDigitsRev d
  18 {-| list of the digits in a given number n.
  19 >>> toDigits 1234
  20 [1,2,3,4]
  21 >>> toDigits 0
  22 []
  23 >>> toDigits (-10)
  24 []
  25 -}
  26
  27 toDigits :: Integer -> [Integer]
  28 toDigits = reverse . toDigitsRev
  29
  30 {-| double every other digit in a list (from the right).
  31 >>> doubleEveryOther [8, 7, 6, 5]
  32 [16,7,12,5]
  33 >>> doubleEveryOther [1, 2, 3]
  34 [1,4,3]
  35  -}
  36 doubleEveryOther :: [Integer] -> [Integer]
  37 doubleEveryOther = reverse . doubleEveryOther' . reverse
  38     where
  39       doubleEveryOther' :: [Integer] -> [Integer]
  40       doubleEveryOther' [] = []
  41       doubleEveryOther' [x] = [x]
  42       doubleEveryOther' (x:y:ys) = x : 2 * y : doubleEveryOther' ys
  43
  44 doubleEveryOther'' :: [Integer] -> [Integer]
  45 doubleEveryOther'' xs | even (length xs) = doubleEven xs
  46                       | otherwise = doubleOdd xs
  47                       where doubleEven [] = []
  48                             doubleEven [x] = [2*x]
  49                             doubleEven (x:y:ys) = (2*x):y:doubleEven ys
  50                             doubleOdd [] = []
  51                             doubleOdd (y:ys) = y:doubleEven ys
  52 {-| sum all the 'digits' in a list.
  53 >>> sumDigits [16,7,12,5]
  54 22
  55 -}
  56 sumDigits :: [Integer] -> Integer
  57 sumDigits xs = let pairs = map (`divMod` 10) xs in
  58                sum $ map (\(x,y) -> (x + y)) pairs
  59 {-| sum all the 'digits' in a list.
  60 >>> sumDigits' [16,7,12,5]
  61 22
  62 -}
  63
  64 sumDigits' :: [Integer] -> Integer
  65 sumDigits' xs = foldr (\x acc -> let (q,r) = x `divMod` 10 in acc + q + r) 0 xs
  66
  67 {-| validate
  68 >>> validate 4012888888881881
  69 True
  70 >>> validate 4012888888881882
  71 False
  72 -}
  73 validate :: Integer -> Bool
  74 validate n = (== 0) ((`rem` 10) (sumDigits (doubleEveryOther (toDigits n))))
  75
  76 {-| validate'
  77 >>> validate' 4012888888881881
  78 True
  79 >>> validate' 4012888888881882
  80 False
  81 -}
  82 validate' :: Integer -> Bool
  83 validate' = (== 0) . (`rem` 10) . sumDigits . doubleEveryOther . toDigits
  84
  85 -- tower of hanoi
  86 type Peg = String
  87 type Move = (Peg, Peg)
  88 hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]
  89 hanoi 0 _ _ _ = []
  90 hanoi n a b c = hanoi (n - 1) a c b ++ [(a, c)] ++ hanoi (n - 1) b a c