クレジットカード番号の Check Digit

Haskell

クレジットカード番号の最後の桁はチェック用の桁です．チェックは，クレジット番号を一桁おきに倍にして（10以上の場合は9を引いて）足し合せそれが10で割り切れるかどうかを知らべるものです．ただし，最後のチェック用の桁を倍にすることがないように，番号の桁数に応じて(13〜16桁)に応じて奇数桁目を倍にするか，偶数桁目を倍にするかを決定する必要があるというところがミソ．さっそくHaskellで書いてみます．

isValid :: [Int] -> Bool
isValid = (0==) . (`mod` 10) . checksum

dbl :: Int -> Int                          -- 倍する関数
dbl x = let x2 = x * 2
        in if x2 < 10 then x2 else x2 - 9

checksum :: [Int] -> Int

checksum はいろいろ考えられて面白そうなのでちょっと考えてみましょう．

その１

ナイーブに手続的に考えれば，奇数桁目と偶数桁目を別々に収集しておいて，全体の桁数が奇数なら，偶数桁目を倍にし，そうでなければ奇数桁目を倍にします．

checksum xs | odd len   = sum os + sum (map dbl es)
            | otherwise = sum es + sum (map dbl os)
  where
    len       = length xs                  -- 桁数
    ixs       = zip [1..] xs               -- インデックス付け
    (ios,ies) = partition (odd.fst) ixs    -- 奇数桁目と偶数桁目を分離
    [os,es]   = map (map snd) [ios,ies]    -- インデックス除去

その２

後ろから処理すれば明示的に桁数を数えなくてもよいことはすぐに分かります．

checksum xs = checksum' (reverse xs)

checksum' :: [Int] -> Int
checksum' (x:y:zs) = x + dbl y + checksum' zs
checksum' []       = 0
checksum' [x]      = x

その３

逆順にならべ変えるのと，和をとる処理で２回もとのリストをたどるのはちょっと悔しい気がする．頭から処理してしまいたい．そこで，蓄積変数を2つ使って，奇数桁目を倍して全体の和をとるのと，偶数桁目を倍して全体の和をとるのを同時進行ですすめてみる．

checksum xs = checksum' 0 0 xs

checksum' :: Int -> Int -> [Int] -> Int
checksum' a b (x:xs) = checksum' (b+x) (a+dbl x) xs
checksum' a _ _      = a

その４

明示的に再帰を書くのも敗北感があるので，畳み込みを使います．

checksum = fst . foldl' k (0,0)
  where 
    k (a,b) x = (b+x, a+dbl x)

その５

後ろから処理すれば2つの処理を同時進行しなくてよい．というわけで foldr を使うことにしよう．

checksum = fst . foldr k (0,(id,dbl))
  where
    k x (y,(f,g)) = (f x + y,(g,f))