Haskell: Comment simplifier ou éliminer liftM2?

Question

Consultez le code suivant je l'ai écrit:

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] 

Où increasing n 'doit retourner une liste de numéros n chiffres dont le nombre augmentation (ou restent les mêmes) de gauche à droite.

Existe-t-il un moyen de simplifier cela? L'utilisation de 'let' et 'liftM2' partout me semble moche. Je pense qu'il me manque quelque chose de vital au sujet de la liste monad, mais je n'arrive pas à m'en débarrasser.

Answer 1

Je pense que ce que vous essayez de faire est la suivante:

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 

Ou, en utilisant une « compréhension de la liste », qui est juste la syntaxe monade spéciale pour les listes:

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] 
       ] 

L'idée la liste monad est que vous utilisez "bind" (<-) pour itérer sur une liste de valeurs, et let pour calculer une seule valeur basée sur ce que vous avez jusqu'à présent dans l'itération en cours. Lorsque vous utilisez bind une deuxième fois, les itérations sont imbriquées à partir de ce point.

Answer 2

Eh bien, en ce qui concerne les fonctions liftM, ma méthode préférée pour les utiliser est les combinateurs définis dans Control.Applicative. En utilisant ceux-ci, vous seriez en mesure d'écrire last = mod <$> ps <*> [10]. La fonction ap de Control.Monad fait la même chose, mais je préfère la version infixe.

Qu'est-ce (<$>) et (<*>) va comme ceci: liftM2 transforme une fonction a -> b -> c en fonction m a -> m b -> m c. Plain liftM est juste (a -> b) -> (m a -> m b), qui est le même que fmap et aussi (<$>). Que se passe-t-il si vous faites cela avec une fonction multi-arguments? Il tourne quelque chose comme a -> b -> c -> d en m a -> m (b -> c -> d). C'est où ap ou (<*>) entrent: ce qu'ils font est tourner quelque chose comme m (a -> b) en m a -> m b. Donc, vous pouvez continuer à le faire ainsi pour autant d'arguments que vous le souhaitez. Cela dit, Travis Brown a raison de dire que, dans ce cas, il semble que vous n'ayez pas vraiment besoin de ce qui précède. En fait, vous pouvez beaucoup simplifier votre fonction: Par exemple, last et next peuvent être écrits en tant que fonctions à un seul argument mappées sur la même liste, ps, et zipWith est identique à zip et map. Toutes ces cartes peuvent être combinées et poussées vers le bas dans la fonction alts. Cela fait alts une fonction à un seul argument, en éliminant le zip ainsi. Enfin, le concat peut être combiné avec le map en tant que concatMap ou, si préféré, (>>=). Voici ce qu'il finit par:

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

Veuillez noter que tous refactoring je l'ai fait pour se rendre à cette version de la vôtre était purement syntaxique, que l'application de transformations qui devraient avoir aucun impact sur le résultat de la fonction. Le raisonnement équationnel et la transparence référentielle sont agréables!

Answer 3

Il me semble très inhabituel d'utiliser liftM2 (ou <$> et <*>) lorsque l'un des arguments est toujours une liste singleton. Pourquoi ne pas simplement utiliser map? Ce qui suit fait la même chose que votre code:

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 4

Voilà comment j'écrire votre code:

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) 

Je suis arrivé à ce code comme suit. La première chose que j'ai faite a été d'utiliser un motif plutôt que des gardes, car c'est plus clair ici.La prochaine chose que j'ai faite était d'éliminer le liftM2 s. Ils sont inutiles ici, parce qu'ils sont toujours appelés avec une liste de taille unique; dans ce cas, c'est la même chose que d'appeler le map. Donc, liftM2 (*) ps [10] est juste map (* 10) ps, et de même pour les autres sites d'appel. Si vous voulez un remplaçant pour liftM2, cependant, vous pouvez utiliser l » <$>Control.Applicative (qui est juste fmap) et <*> pour remplacer liftMn pour tout n: liftMn f a b c ... z devient f <$> a <*> b <*> c <*> ... <*> z. Que ce soit ou non est une question de goût; Je l'aime bien. Mais ici, nous pouvons l'éliminer entièrement.

L'endroit suivant où j'ai simplifié le code original est le do .... Vous ne prenez jamais réellement profiter du fait que vous êtes dans une do -bloc, et que le code peut devenir

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

De là, en arrivant à mon code écrit essentiellement impliqué fusionnant tous vos map s ensemble. L'un des seuls appels restants qui n'était pas un map était zipWith. Mais parce que vous avez effectivement zipWith alts next last, vous ne travaillez qu'avec 10*p et p `mod` 10 en même temps, donc nous pouvons les calculer dans la même fonction. Cela conduit à

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

C'est essentiellement mon code: concat $ map ... devrait toujours être concatMap (qui, soit dit en passant, est =<< dans la liste monade), nous utilisons uniquement ps une fois pour que nous puissions plier, et je préfère let à where.

---

1: Techniquement, cela ne fonctionne que pour Applicative s, donc si vous arrive d'utiliser une monade qui n'a pas été fait l'un, <$> est `liftM` et <*> est `ap`. Toutes les monades peuvent être faites foncteurs applicatifs, cependant, et beaucoup d'entre eux ont été.

Answer 5

Je pense qu'il est plus propre de passer le dernier chiffre dans un paramètre séparé et d'utiliser des listes.

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