Come scrivere questa funzione in modo idiomatico?

Question

Sto cercando una funzione che verifica un predicato sugli elementi di una lista, crea un nuovo elenco per ogni elemento che soddisfa il predicato e si applica una funzione solo per quell'elemento.

Esempio:

someFunction :: (a -> Bool) -> (a -> a) -> [a] -> [[a]] 
someFunction = ... 

let ys = someFunction isOdd (* 2) [1..10] 
    {- ys == [[2, 2, 3, 4, 5, ...], 
       [1, 2, 6, 4, 5, ...], 
       [1, 2, 3, 4, 10, ...], 
       ...] -} 

In ys, la prima lista è uguale a quello originale, eccetto il primo elemento, che soddisfa il predicato ed è moltiplicato per 2. Anche la seconda lista è uguale a quella originale, tranne il terzo elemento e così via.

ho potuto scrivere tale funzione prendendo gli indici dei valori che soddisfano il predicato e poi mappatura attraverso gli indici. Tuttavia, questo non sembra molto funzionale e mi piacerebbe vedere un approccio più idiomatico.

Answer 1

È puoi usare un dito (come un zipper: D muovi il dito su ogni oggetto: D come quando si legge)

someFunction :: (a -> Bool) -> (a -> a) -> [a] -> [[a]] 
someFunction check f xs = r [] xs 
    where r _ []  = [] 
     r ps (y:ys) = let rs = r (ps ++ [y]) ys 
         in if check y then [ps ++ [f y] ++ ys] ++ rs 
            else rs 

r funzione prendere ps "elementi lavorati" e (y:ys) "elementi in sospeso".

Se avete bisogno di costo lineare (ps ++ [y] operazione farlo cuadratic) uso efficiente struct inserimento coda.

Usando splitAt è possibile scrivere

someFunction check f xs = map (\(a,(x:b)) -> a ++ [f x] ++ b) $ 
          filter (check.head.snd) 
          [splitAt n xs | n <- [0..length xs - 1]] 

o utilizzando di lista

someFunction check f xs = 
    [ a ++ [f x] ++ b | n <- [0..length xs - 1] 
         , let (a, (x:b)) = splitAt n xs 
         , check x] 

Utilizzando zip suggerito dal @chi la soluzione prendere costo lineare (la generazione di liste, infine, è O (n^2))

someFunction check f xs = 
    [ a ++ [f x] ++ b | (a, (x:b)) <- init $ zip (inits xs) (tails xs) 
         , check x] 

Infine (?) @ ØrjanJohansen nota per rimuovere init $ (lascio entrambe le versioni, credo sia un grande esempio)

Evitare init $

someFunction check f xs = 
    [ a ++ [f x] ++ b | (a, (x:b)) <- zip (inits xs) (tails xs) 
         , check x] 

ultimo elemento (xs, []) "zip", viene evitato l'elenco di comprensione, @ ØrjanJohansen ha sottolineato here come è tradotta

[e | p <- l, Q] = let ok p = [e | Q] 
         ok _ = [] 
        in concatMap ok l 

(thx @WillNess)

Answer 2

Che ne dici:

Inizia con un elenco:

[1,2,3,4] 

copia della lista n volte, dove n è la sua dimensione (:: [[]]):

[ 
[1,2,3,4], 
[1,2,3,4], 
[1,2,3,4], 
[1,2,3,4] 
] 

Split le liste su ogni elemento (più o meno "diagonale") (:: [([], [])]):

[ 
([],[1,2,3,4]), 
([1],[2,3,4]), 
([1,2],[3,4]), 
([1,2,3],[4]) 
] 

filtrare le linee su cui head . snd non soddisfa il vostro predicato

[ 
([], [1,2,3,4]), 
([1,2], [3,4]) 
] 

Applicare la funzione sui restanti teste

[ 
([], [2,2,3,4]) 
([1,2], [6,4]), 
] 

concatenare le coppie posteriori

[ 
[2,2,3,4], 
[1,2,6,4] 
] 

Answer 3

È possibile assemblare questa funzione da pezzi che sono standard o dovrebbero essere. La risposta accettata ha il giusto indizio sulle chiusure lampo. La mia risposta about differentiation and comonads fornisce un trattamento generale delle operazioni pertinenti, ma vorrei essere specifico qui.

ho definire il tipo di "liste con un foro elemento" come segue:

data Bwd x = B0 | Bwd x :< x deriving Show 
type HoleyList x = (Bwd x, [x]) 

A rigor di termini, non ho bisogno di presentare le liste arretrate per farlo, ma ho così facilmente confuso se io devo invertire le cose nella mia testa. (Accade così che HoleyList è la derivata formale [].)

ora posso definire ciò che significa essere un elemento di lista nel suo contesto.

type InContext x = (HoleyList x, x) 

L'idea è che il secondo componente della coppia appartenga tra la lista a ritroso e quella in avanti. Posso definire la funzione che si inserisce l'elenco di nuovo insieme (chiamato upF nel trattamento generico.)

plug :: InContext x -> [x] 
plug ((B0, xs), y)  = y : xs 
plug ((xz :< x, xs), y) = plug ((xz, y : xs), x) 

posso definire anche la funzione che dà tutti i modi per fare una lista a parte (downF genericamente).

selections :: [x] -> [InContext x] 
selections = go B0 where 
    go xz [] = [] 
    go xz (x : xs) = ((xz, xs), x) : go (xz :< x) xs 

Nota che

map snd (selections xs) = xs 
map plug (selections xs) = map (const xs) xs 

e ora siamo bene seguire la ricetta di Bartek.

selectModify :: (a -> Bool) -> (a -> a) -> [a] -> [[a]] 
selectModify p f = map (plug . (id *** f)) . filter (p . snd) . selections 

Cioè: filtrare le selezioni dal test, applicare la funzione all'elemento a fuoco, ricollegarlo insieme. Se si ha a che fare con l'attrezzatura per cerniere, si tratta di una fodera singola, e dovrebbe funzionare per qualsiasi functor differenziabile, non solo per le liste! Lavoro fatto!

> selectModify ((1 ==) . (`mod` 2)) (2*) [1..10] 
[[2,2,3,4,5,6,7,8,9,10] 
,[1,2,6,4,5,6,7,8,9,10] 
,[1,2,3,4,10,6,7,8,9,10] 
,[1,2,3,4,5,6,14,8,9,10] 
,[1,2,3,4,5,6,7,8,18,10]] 

Answer 4

Guardando attraverso tutte le soluzioni belle e soprattutto un po 'di fantasia qui pubblicato (che includono @ ultimo zip una basata su di josejuan, che è essenzialmente il linguaggio userei io in fretta), non posso fare a sentire il lista manca davvero il diretto, ma ancora soluzione idiomatica con ricorsione esplicita, pigra - il tipo di codice che probabilmente vedresti nelle librerie standard se someFunction fosse stata una funzione standard. Quindi, ecco una versione di che (tra cui il lavoratore go avvolgendo devi anche vedere):

someFunction :: (a -> Bool) -> (a -> a) -> [a] -> [[a]] 
someFunction p f xs = go xs where 
    go [] = [] 
    go (x:xs) 
     | p x   = (f x : xs) : rest 
     | otherwise = rest 
     where 
     rest = map (x :) (go xs)