Haskell的replaceValues起作用

我想要寫一個函數，它接受元件L的列表，指數i的列表，和替換的列表值v。該函數將與所述替換i的升對應於索引值如果l = [1,2,3,4,5,6]，i = [0,2]和v = [166,667]，則替換值liv == [166,2,667,4,5,6]Haskell的replaceValues起作用

我的功能：

--Replace the values in list l at indices in i with the 
-- corresponding value in v 
replaceValues :: [a] -> [Int] -> [a] -> [a] 
replaceValues l [] [] = l 
replaceValues l i v = x ++ [head v] ++ (replaceValues (tail y) shiftedIndices (tail v)) 
    where 
     (x,y) = splitAt (head i) l 
     --The indices must be shifted because we are changing the list 
     shiftedIndices = map ((-)((head i) + 1)) (tail i)

此功能法力ges正確地替換i中第一個索引處的值，但它錯位了以下所有值。在上面的例子中，它會給出輸出[166,667,3,4,5,6]。

來源

2011-11-08 Xander Dunn

與實現的問題是，你是不是跟蹤哪些指數的您當前所處。

首先，您最好考慮使用[(Int,a)]而不是[Int]和[a]參數分開以確保「列表」的長度相等。

另一種實現方式如下：

import Data.Maybe(fromMaybe) 
import qualified Data.IntMap as M 

replaceValues :: [a] -> [(Int,a)] -> [a] 
replaceValues as rs = map rep $ zip [0..] as 
    where 
    rsM = M.fromList rs 

    rep (i,a) = fromMaybe a $ M.lookup i rsM

這裏發生了什麼：

標籤，其索引的每個值
看看是否有該指標替代值：如果有，請使用它;否則，請使用原始值。

來源

2011-11-08 07:19:58 ivanm

這是一個非常簡潔的實現。但是，我在函數rep（i，a）上得到了一個類型錯誤： –

@ kienjakenobi：哎呀，忘了額外的導入！（即從可能），它應該使用'rsM'，而不是'rs'：s現在修復。 – ivanm

非常感謝。這確實有效。我會更多地考慮它，看看我完全理解它。 –

是彈簧想到的第一件事是，你應該使用一個元組列表與

l = [1,2,3,4,5,6] 
r = [(0,166),(2,667)]

指定替換，也就是工作......你可以用zip來轉換兩種列表格式。然後，我會規定該列表由元組（sortBy）的第一個元素進行排序，並有在它（nubBy）沒有重複的指標。剩下的就是一個簡單而又重複，替代，當您去，具有線性複雜情況，並且最大限度地懶：

replaceValues :: [a] -> [(Int, a)] -> [a] 
replaceValues xs rs = f 0 xs rs 
    where 
    f _ xs [] = xs 
    f _ [] _ = [] 
    f n (x:xs) [email protected]((i,r):is') 
     | n < i = x:f (n+1) xs is 
     | n == i = r:f (n+1) xs is' 
     | otherwise = error "Can't happen"

當心碼的，不過，我只證明它是正確的，沒有真正嘗試過。

當然，使用地圖也是有效的，但是你要處理O（m log m + n log m）（構造地圖+ n次查找）而不是O（n）的複雜度，或者，考慮到排序問題，O（n + m log m），並且在你的列表已經排序的情況下失去了懶惰的能力，並且在你遍歷時增加了垃圾收集的替換。

nubBy來自庫具有二次複雜性，但是當列表排序時，它也可以在線性時間內處理，只需用遞歸調用將錯誤替換爲錯誤，即可省去多餘的(i,r) s。

來源

2011-11-08 07:29:27 barsoap

非常感謝你爲這個替代解決方案。現在必須睡覺，但我會評估它，並考慮它。 –

如前面所說的，使用元組 - 但不要忘了模式匹配。或者使用地圖，如果你不處理大集合

replaceValues :: [a] -> [Int] -> [a] ->[a] 
replaceValues a b i = map fst $ f (zip a [0..]) (zip b i) 
    where 
     f [] _ = [] 
     f xs [] = xs 
     f ((x,i):xs) [email protected]((j,y):ys) | i == j = (y,i) : f xs ys 
            | otherwise = (x,i) : f xs s2

來源

2011-11-08 07:43:27 jdevelop

Haskell的replaceValues起作用

回答

相關問題