Sostituire un elemento in un elenco solo una volta - Haskell

Question

Desidero sostituire un elemento in un elenco con un nuovo valore solo al primo occorrenza. Ho scritto il codice qui sotto ma usandolo, tutti gli elementi abbinati cambieranno.

replaceX :: [Int] -> Int -> Int -> [Int] 
replaceX items old new = map check items where 
check item | item == old = new 
      | otherwise = item 

Come posso modificare il codice in modo che la modifica avvenga solo al primo articolo abbinato?

Grazie per l'aiuto!

Answer 1

Il punto è che map e f (check nel tuo esempio) comunicare solo su come trasformare i singoli elementi. Non comunicano su quanto in fondo alla lista trasformare gli elementi: map porta sempre fino alla fine.

map :: (a -> b) -> [a] -> [b] 
map _ []  = [] 
map f (x:xs) = f x : map f xs 

Scriviamo una nuova versione di map --- chiamerò mapOnce perché non riesco a pensare a un nome migliore.

mapOnce :: (a -> Maybe a) -> [a] -> [a] 

Ci sono due cose da notare su questo tipo di firma:

1. Perché possiamo interrompere l'applicazione f parte a senso unico verso il basso l'elenco, la lista di input e la lista di uscita devono avere lo stesso tipo di . (Con map, perché l'intero elenco sarà sempre mappato, il tipo può cambiare.)

2. Il tipo di f non è cambiato a -> a, ma a -> Maybe a.

   • Nothing significherà "lasciare questo elemento immutato, proseguire verso il basso la lista"
   • Just y significherà "cambiare questo elemento, e lasciare i restanti elementi inalterati"

Quindi:

mapOnce _ []  = [] 
mapOnce f (x:xs) = case f x of 
     Nothing -> x : mapOnce f xs 
     Just y -> y : xs 

Il tuo esempio è ora:

replaceX :: [Int] -> Int -> Int -> [Int] 
replaceX items old new = mapOnce check items where 
    check item | item == old = Just new 
       | otherwise = Nothing 

Answer 2

Si può facilmente scrivere questo come una ripetizione ricorsiva in questo modo:

rep :: Eq a => [a] -> a -> a -> [a] 
rep items old new = rep' items 
    where rep' (x:xs) | x == old = new : xs 
         | otherwise = x : rep' xs 
      rep' [] = [] 

Answer 3

Un'implementazione diretta sarebbe

rep :: Eq a => a -> a -> [a] -> [a] 
rep _ _ [] = [] 
rep a b (x:xs) = if x == a then b:xs else x:rep a b xs 

Mi piace lista come ultimo argomento di fare qualcosa di simile

myRep = rep 3 5 . rep 7 8 . rep 9 1 

Answer 4

non

Forse la soluzione più veloce, ma facile da capire:

rep xs x y = 
    let (left, (_ : right)) = break (== x) xs 
    in left ++ [y] ++ right 

[Edi t]

Come ha commentato Dave, questo non funzionerà se x non è nell'elenco. Una versione sicura sarebbe:

rep xs x y = 
    let (left, right) = break (== x) xs 
    in left ++ [y] ++ drop 1 right 

[Edit]

Arrgh !!!

rep xs x y = left ++ r right where 
    (left, right) = break (== x) xs 
    r (_:rs) = y:rs 
    r [] = [] 

Answer 5

Per essere sincero, non mi piace la maggior parte delle risposte finora. dave4420 presenta alcune belle idee su map che io secondo, ma anche la sua soluzione non mi piace.

Perché non mi piacciono queste risposte? Perché dovresti imparare a risolvere problemi come questi abbattendoli in problemi più piccoli che possono essere risolti con funzioni più semplici, preferibilmente con funzioni di libreria. In questo caso, la libreria è Data.List, e la funzione è break:

break, applicato ad un predicato p e un elenco xs, restituisce una tupla cui primo elemento è lungo prefisso (eventualmente vuoto) di xs di elementi che non soddisfano p e il secondo elemento è il resto dell'elenco.

Armati di che, possiamo attaccare il problema come questo:

1. Spalato la lista in due pezzi: tutti gli elementi prima della prima occorrenza di old, e il resto.
2. L'elenco "resto" sarà vuoto oppure il suo primo elemento sarà la prima occorrenza di old. Entrambi questi casi sono facili da gestire.

Quindi abbiamo questa soluzione:

import Data.List (break) 

replaceX :: Eq a => a -> a -> [a] -> [a] 
replaceX old new xs = beforeOld ++ replaceFirst oldAndRest 
    where (beforeOld, oldAndRest) = break (==old) xs 
      replaceFirst [] = [] 
      replaceFirst (_:rest) = new:rest 

Esempio:

*Main> replaceX 5 7 ([1..7] ++ [1..7]) 
[1,2,3,4,7,6,7,1,2,3,4,5,6,7] 

Quindi il mio consiglio per voi:

1. Scopri come importare le librerie.
2. Documentazione della biblioteca di studio e apprendimento delle funzioni standard. Data.List è un ottimo punto di partenza.
3. Provare a utilizzare quelle funzioni di libreria il più possibile.
4. Come esercizio di autoapprendimento, è possibile selezionare alcune delle funzioni standard da Data.List e scrivere le proprie versioni di esse.
5. Quando si incontra un problema che non può essere risolto con una combinazione di funzioni di libreria, provare a inventare la propria funzione generica che sarebbe utile.

EDIT: Ho appena capito che break è in realtà una funzione Prelude, e non ha bisogno di essere importati. Ancora, Data.List è una delle migliori librerie da studiare.

Answer 6

Un'alternativa che utilizza Lens library.

>import Control.Lens 
>import Control.Applicative 

>_find :: (a -> Bool) -> Simple Traversal [a] a         
>_find _ _ [] = pure []               
>_find pred f (a:as) = if pred a             
>      then (: as) <$> f a          
>      else (a:) <$> (_find pred f as) 

Questa funzione richiede un (a -> Bool), che è una funzione che deve restituire vero su un tipo 'a' che si wan per modificare.

Se il primo numero maggiore di 5 ha bisogno di essere raddoppiato, allora potremmo scrivere:

>over (_find (>5)) (*2) [4, 5, 3, 2, 20, 0, 8] 
[4,5,3,2,40,0,8] 

La cosa grandiosa di lente è che si possono combinare tra loro da li compongono (.). Quindi, se vogliamo a zero il primo numero < 100 nella lista dei sub 2 ° che potevamo:

>over ((element 1).(_find (<100))) (const 0) [[1,2,99],[101,456,50,80,4],[1,2,3,4]] 
[[1,2,99],[101,456,0,80,4],[1,2,3,4]] 

Answer 7

Ecco un modo imperativo per farlo, usando State Monade:

import Control.Monad.State             

replaceOnce :: Eq a => a -> a -> [a] -> [a] 
replaceOnce old new items = flip evalState False $ do 
    forM items $ \item -> do 
    replacedBefore <- get 
    if item == old && not replacedBefore 
     then do 
     put True 
     return new 
     else 
     return old 

Answer 8

replaceValue :: Int -> Int -> [Int] -> [Int] 
replaceValue a b (x:xs) 
     |(a == x) = [b] ++ xs 
     |otherwise = [x] ++ replaceValue a b xs