初学者 |用于整数列表的 luhn 算法

Question

我已经看过这个解决方案：

doubleAndSum :: [Int] -> Int
doubleAndSum = fst . foldr (\i (acc, even) -> (acc + nextStep even i, not even)) (0,False)
  where 
    nextStep even i
        | even      = (uncurry (+) . (`divMod` 10) . (*2)) i
        | otherwise = i 

myLuhn :: Int -> Bool
myLuhn = (0 ==) . (`mod` 10) . doubleAndSum . (map (read . (: ""))) . show

testCC :: [Bool]
testCC = map myLuhn [49927398716, 49927398717, 1234567812345678, 1234567812345670]
-- => [True,False,False,True]

但是，我不明白，因为我是Haskell的新手。

luhn :: [Int] -> Bool
luhn w x y z = (luhnDouble w + x + luhnDouble y + z) `mod` 10 == 0

luhnDouble :: Int -> Int
luhnDouble x | 2* x <= 9 = 2*x
             | otherwise = (2*x)-9

我理解这个简化版的算法只有四位数。

但是，我不知道如何为任意长度的数字列表编写算法版本。

Answer 1

老实说，这个例子很晦涩。它过度使用 point-free 风格 ，即省略显式函数参数。这有时可以使代码简洁明了，但也可能使代码变得晦涩难懂。

让我们从这里开始：

     (uncurry (+) . (`divMod` 10) . (*2)) i

首先，由于您只是将所有内容应用到参数 i，因此没有真正需要 合成管道 – 您不妨编写它

     uncurry (+) $ (`divMod` 10) $ (*2) i
   ≡ uncurry (+) $ (`divMod` 10) $ i*2
   ≡ uncurry (+) $ (i*2)`divMod`10
   ≡ let (d,r) = (i*2)`divMod`10
     in d+r

所以，nextStep可以写成

    nextStep isEven i
        | isEven     = d+r
        | otherwise  = i
     where (d,r) = (i*2)`divMod`10

（我避开了变量名even，这也是检查一个数是否为偶数的标准函数的名称！）

或者，您可以在这里调用您的 luhnDouble 函数，它实际上计算相同的东西，只是以更详细的方式：

    nextStep isEven i
        | isEven     = luhnDouble i
        | otherwise  = i

那么你就弃牌了。它基本上做了三件互锁的事情： 1. 在偶数和奇数之间切换 2. 将 nextStep 应用于每个列表元素，连同even-ness3.总结结果

我不同意一次折叠就完成所有这些是个好主意^†；写出来更清楚：

doubleAndSum = sum
              . map (\(isEven, i) -> nextStep isEven i)  -- or `map (uncurry nextStep)`
              . zip (cycle [False, True])   -- or `iterate not False`
              . reverse

需要 reverse 只是为了将 False 与输入列表的 last 元素对齐，而不是它的头部；这有点丑陋但不重要。

map 和 zip 的组合有一个标准的快捷方式，可以一步完成：

doubleAndSum = sum
              . zipWith nextStep (cycle [False, True])
              . reverse

至于myLuhn：IMO实际上可以用point-free风格来写，但我会稍微分解一下。具体来说，

decimalDigits :: Int -> [Int]
decimalDigits = map (read . (: "")) . show

(:"")所做的是，它将单个字符放入singleton-strings。也可以写成 read . pure.

然后，

myLuhn = (0 ==) . (`mod` 10) . doubleAndSum . decimalDigits

或

myLuhn x = doubleAndSum (decimalDigits x)`mod`10 == 0

^†_{可能会有这样的情况，即一次遍历对性能有好处，但是如果你从那个层面考虑，那么它几乎肯定不会是对列表进行惰性右折叠，而是对未装箱的向量进行严格的左折叠。无论如何，GHC 通常可以将单独的 fold-y 操作融合到单个遍历中。}

初学者 |用于整数列表的 luhn 算法

for beginners | luhn algorithm for list of integers

haskell

luhn