Haskell: come semplificare o eliminare liftM2?

Question

Si consideri il seguente codice che ho scritto:

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] 

Dove 'increasing n' dovrebbe restituire un elenco di numeri di n cifre il cui numero aumenta (o rimanere lo stesso) da sinistra a destra.

C'è un modo per semplificare questo? L'uso di 'let' e 'liftM2' mi sembra dappertutto brutto. Penso che mi manchi qualcosa di vitale nella lista della monade, ma non riesco a liberarmene.

Answer 1

Penso che quello che si sta cercando di fare è questo:

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 

Oppure, utilizzando una "lista di comprensione", che è solo la sintassi monade speciale per le liste:

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'idea in la lista è che si usa "bind" (<-) per iterare su un elenco di valori, e let per calcolare un singolo valore in base a ciò che si ha finora nell'iterazione corrente. Quando si utilizza il binding una seconda volta, le iterazioni vengono nidificate da quel punto in poi.

Answer 2

Bene, per quanto riguarda le funzioni liftM, il mio modo preferito per utilizzarle è i combinatori definiti in Control.Applicative. Usando quelli, saresti in grado di scrivere last = mod <$> ps <*> [10]. La funzione ap da Control.Monad fa la stessa cosa, ma preferisco la versione infissa.

Cosa (<$>) e (<*>) va in questo modo: liftM2 trasforma una funzione a -> b -> c in una funzione m a -> m b -> m c. Semplice liftM è solo (a -> b) -> (m a -> m b), che è lo stesso di fmap e anche (<$>).

Cosa succede se lo si fa a una funzione a più argomenti? Trasforma qualcosa come a -> b -> c -> d in m a -> m (b -> c -> d). Qui entra in gioco ap o (<*>): quello che fanno è trasformare qualcosa come m (a -> b) in m a -> m b. Quindi puoi continuare a metterlo in fila in quel modo per tutti gli argomenti che vuoi.

---

Detto questo, Travis Brown ha ragione che, in questo caso, sembra che tu non abbia davvero bisogno di nessuno dei precedenti. Infatti, è possibile semplificare notevolmente la funzione: ad esempio, sia last sia next possono essere scritti come funzioni a argomento singolo mappate sullo stesso elenco, ps e zipWith è uguale a zip e a map. Tutte queste mappe possono essere combinate e spostate verso il basso nella funzione alts. Questo rende alts una funzione a singolo argomento, eliminando anche lo zip. Infine, lo concat può essere combinato con o, se si preferisce, (>>=). Ecco cosa finisce:

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

notare che tutte le refactoring che ho fatto per arrivare a tale versione dal vostro è stato puramente sintattico, applicando solo le trasformazioni che dovrebbero avere alcun impatto sul risultato della funzione. Ragionamento equo e trasparenza referenziale sono carini!

Answer 3

Mi sembra molto strano usare liftM2 (o <$> e <*>) quando uno degli argomenti è sempre un elenco di singleton. Perché non usare solo map? Di seguito fa la stessa cosa il tuo codice:

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

Ecco come mi piacerebbe scrivere il vostro codice:

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) 

sono arrivato in questo codice come segue. La prima cosa che ho fatto è stata utilizzare la corrispondenza del modello invece delle guardie, poiché qui è più chiaro.La prossima cosa che ho fatto è stata eliminare il liftM2 s. Non sono necessari qui, perché vengono sempre chiamati con una lista di una dimensione; in tal caso, equivale a chiamare map. Quindi liftM2 (*) ps [10] è solo map (* 10) ps e, analogamente, per gli altri siti di chiamata. Se si desidera una sostituzione generale per liftM2, però, è possibile utilizzare Control.Applicative s' <$> (che è solo fmap) e <*> per sostituire liftMn per qualsiasi n: liftMn f a b c ... z diventa f <$> a <*> b <*> c <*> ... <*> z. Che sia più bello o meno è una questione di gusti; Mi piace piacermi. Ma qui, possiamo eliminarlo completamente.

Il prossimo luogo che ho semplificato il codice originale è do .... Non si può mai realmente sfruttare il fatto che si trovi in ​​una do -block, e in modo che il codice possa diventare

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

Da qui, arrivando al mio codice di scrittura essenzialmente coinvolto fondendo tutto il vostro map s insieme. Una delle uniche chiamate rimanenti che non era uno map era zipWith. Ma poiché hai effettivamente zipWith alts next last, lavori solo con 10*p e p `mod` 10 allo stesso tempo, così possiamo calcolarli nella stessa funzione. Questo porta a

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

E questo è fondamentalmente il mio codice: concat $ map ... deve sempre diventare concatMap (che, per inciso, è =<< nella lista Monade), usiamo solo ps una volta in modo che possiamo piegarlo in, e preferisco let a where.

---

1: Tecnicamente, questo funziona solo per Applicative s, quindi se vi capita di essere utilizzando una monade che non è stato fatto uno, <$> è `liftM` e <*> è `ap`. Comunque tutte le monadi possono essere fatte funtori applicativi, e molti di loro lo sono stati.

Answer 5

Penso che sia più pulito passare l'ultima cifra in un parametro separato e utilizzare le liste.

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