哈斯克尔:如何简化或消除升降机2?

我想你想做的是:

increasing :: Integer -> [Integer]
increasing 1 = [1..9]
increasing n = do p <- increasing (n - 1)
                  let last = p `mod` 10
                      next = p * 10
                  alt <- [last .. 9]
                  return $ next + alt

或者,使用“列表理解”,这只是列表的特殊monad语法:

increasing2 :: Integer -> [Integer]
increasing2 1 = [1..9]
increasing2 n = [next + alt | p <- increasing (n - 1),
                              let last = p `mod` 10
                                  next = p * 10,
                              alt <- [last .. 9]
                ]

单子列表中的想法是使用“bind”( <- )循环访问值列表,以及 let 根据当前迭代中的内容计算单个值。当您第二次使用bind时,迭代将从该点嵌套。

嗯,到目前为止 liftM 函数go,我使用这些函数的首选方法是 Control.Applicative . 使用这些,你就可以写 last = mod <$> ps <*> [10] . 这个 ap 函数从 Control.Monad 做同样的事情,但我更喜欢中缀版本。

什么 (<$>) 和 (<*>) 像这样: liftM2 打开一个函数 a -> b -> c 变为函数 m a -> m b -> m c . 平原 利夫特 只是 (a -> b) -> (m a -> m b) ,与 fmap 而且 (& lt;$& gt;) .

如果对一个多参数函数这样做会发生什么?它变成了 a -> b -> c -> d 进入之内 m a -> m (b -> c -> d) . 这里就是 AP 或 (& lt;*& gt;) 进来:他们所做的就是 m (a -> b) 进入之内 m a -> m b . 所以你可以一直用这种方式来进行你喜欢的各种论证。

也就是说,特拉维斯·布朗是对的,在这种情况下,你似乎并不真正需要上述任何一个。事实上,您可以大大简化您的函数:例如,两者都可以 last 和 next 可以作为映射到同一列表上的单参数函数写入, ps 和 zipWith 与A相同 zip 和A map . 所有这些地图都可以组合并下推到 alts 功能。这使得 阿尔茨 单参数函数,消除 拉链 也。最后, concat 可以与 地图 作为 concatMap 或者,如果愿意, (>>=) . 结果是:

increasing' :: Integer -> [Integer]
increasing' 1 = [1..9]
increasing' n = increasing' (n - 1) >>= alts
    where alts x = map ((x * 10) +) [mod x 10..9]

请注意,我从您的版本中得到的所有重构都是 纯粹的句法 ,只应用对函数结果没有影响的转换。等式推理和参考透明性很好!

我觉得用起来很不寻常 liftM2 (或) <$> 和 <*> )当其中一个参数总是单例列表时。为什么不只用 map ?以下操作与您的代码相同:

increasing :: Integer -> [Integer]
increasing n
  | n == 1    = [1..9]
  | otherwise = do let ps = increasing (n - 1)
                   let last = map (flip mod 10) ps
                   let next = map (10 *) ps
                   alternateEndings next last
  where alternateEndings xs ys = concat $ zipWith alts xs ys
        alts x y = map (x +) [y..9]

以下是我如何编写您的代码:

increasing :: Integer -> [Integer]
increasing 1 = [1..9]
increasing n = let allEndings x = map (10*x +) [x `mod` 10 .. 9]
               in concatMap allEndings $ increasing (n - 1)

我得出的代码如下。我做的第一件事是使用模式匹配而不是防护,因为这里更清楚。接下来我要做的就是消除 liftM2 S.这里不需要它们,因为它们总是用一个大小一个的列表来调用;在这种情况下,它与调用相同 map . 所以 liftM2 (*) ps [10] 只是 map (* 10) ps 以及其他呼叫站点。如果你想要一个 电梯2 但是,您可以使用 Control.Applicative 的 <$> (只是 fmap ) <*> 替代 liftMn 对于任何 n : liftMn f a b c ... z 变成 f <$> a <*> b <*> c <*> ... <*> z . 它是否更好是一个品味问题,我恰好喜欢它。 ^一 但在这里,我们可以完全消除这一点。

下一个简化原始代码的地方是 do ... . 你从来没有真正利用你在 do -块,这样代码就可以

let ps   = increasing (n - 1)
    last = map (`mod` 10) ps
    next = map (* 10)     ps
in alternateEndings next last

从这里,到达我的代码基本上涉及到编写融合您所有 地图 在一起。唯一剩下的电话之一不是 地图 是 zipWith . 但因为你实际上 zipWith alts next last ,您只与 10*p 和 p `mod` 10 同时,我们可以用同样的函数计算它们。这导致

let ps = increasing (n - 1)
in concat $ map alts ps
where alts p = map (10*p +) [y `mod` 10..9]

这基本上是我的代码: concat $ map ... 应该永远变成 concatMap (顺便说一下,这是 =<< 在单子列表中),我们只使用 ps 一次,这样我们就可以折叠起来,我更喜欢 let 到 where .

1: 从技术上讲,这只适用于 Applicative S,所以如果你碰巧用的是一个单子,它不是单子, <$GT; 是 `liftM` 和 <* 是 `ap` . 但是,所有单子都可以成为应用函数,其中很多都是。

我认为在一个单独的参数中传递最后一个数字并使用列表更简单。

f a 0 = [[]]
f a n = do x <- [a..9]
           k <- f x (n-1)
           return (x:k)

num = foldl (\x y -> 10*x + y) 0

increasing = map num . f 1