Haskell: Как упростить или устранить liftM2?

Question

Рассмотрим следующий код, который я написал:

import Control.Monad

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

Где 'increasing n' должно возвращать список из n-значных чисел, чьи числа увеличиваются (или остаются прежними) слева направо.

Есть ли способ упростить это? Использование 'let' и 'liftM2' везде кажется мне безобразным.Я думаю, что упускаю что-то жизненно важное в монаде списка, но я не могу избавиться от них.

Answer 1

Что касается функций liftM, я предпочитаю использовать те комбинаторы, которые определены в Control.Applicative. Используя их, вы сможете написать last = mod <$> ps <*> [10]. Функция ap из Control.Monad делает то же самое, но я предпочитаю инфиксную версию.

Что (<$>) и (<*>) выглядит следующим образом: liftM2 превращает функцию a -> b -> c в функцию m a -> m b -> m c. Обычная liftM это просто (a -> b) -> (m a -> m b), что совпадает с fmap, а также (<$>).

Что произойдет, если вы сделаете это с функцией с несколькими аргументами? Это превращает что-то вроде a -> b -> c -> d в m a -> m (b -> c -> d). Вот где приходят ap или (<*>): они превращают что-то вроде m (a -> b) в m a -> m b. Таким образом, вы можете продолжать в том же духе столько аргументов, сколько захотите.

---

Тем не менее, Трэвис Браун прав, что в данном случае кажется, что вам не нужно ничего из вышеперечисленного. Фактически, вы можете значительно упростить вашу функцию: например, last и next могут быть записаны как функции с одним аргументом, отображенные в один и тот же список, ps, а zipWith совпадает с zip и map. Все эти карты могут быть объединены и помещены в функцию alts. Это делает alts функцией с одним аргументом, исключая также zip. Наконец, concat можно объединить с map как concatMap или, если предпочтительнее, (>>=). Вот чем это заканчивается:

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

Обратите внимание, что весь рефакторинг, который я сделал, чтобы получить эту версию от вашей, был чисто синтаксическим , применяя только преобразования, которые не должны влиять на результат функции. Эквациональные рассуждения и ссылочная прозрачность хороши!

Answer 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

Или, используя «понимание списка», которое является просто специальным монадным синтаксисом для списков:

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 для вычисления одного значения на основе того, что у вас есть в текущей итерации.Когда вы используете связывание во второй раз, итерации с этого момента вкладываются.

Answer 3

Вот как бы я написал ваш код:

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, и аналогично для других сайтов вызовов.Если вы хотите обычную замену liftM2, вы можете использовать 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

Отсюда, получение моего кода по сути связано с написанием слияния всех ваших map с вместе.Один из оставшихся вызовов, который не был map, был 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 с, так что если вы случитесьчтобы использовать монаду, которая не была сделана, <$> - это `liftM`, а <*> - `ap`.Все монады могут быть сделаны аппликативными функторами, и многие из них были.

Answer 4

Мне кажется очень необычным использовать 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]

Answer 5

Я думаю, что лучше передать последнюю цифру в отдельном параметре и использовать списки.

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