Haskell replaceValues関数

Question

要素l、インデックスiのリスト、および置換値のリストを取る関数を書いてみたい。関数は、iのインデックスに対応するlの値を、 vの対応する値

例：l = [1,2,3,4,5,6]、i = [0,2]、v = [166,667]の場合、 replaceValues liv == [166,2,667,4,5,6]

My機能：

--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]となります。

Answer 1

あなたの実装での問題は、あなたが現在どのインデックスを追跡していないことです。

まず第一に、あなたは[(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 

ここで何が起こっている：

• そのインデックスとタグの各値を

• そのインデックスの置換値があるかどう参照してください。存在する場合はそれを使用する。それ以外の場合は、元の値を使用します。

Answer 2

心にバネ最初の事はあなたが交換を指定するタプルのリストを使用する必要があること、それは、

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

との仕事です...あなたはあなたを変換するzipを使用することができますそのフォーマットに2つのリストがあります。次に、そのリストがタプルの最初の要素（sortBy）によってソートされ、重複するインデックスがないことを指定します（nubBy）。残りは、単純な再帰、あなたが行くように線形複雑で、交換し、最大限に怠けている：

replaceValues :: [a] -> [(Int, a)] -> [a] 
replaceValues xs rs = f 0 xs rs 
    where 
    f _ xs [] = xs 
    f _ [] _ = [] 
    f n (x:xs) is@((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（n）の代わりに複雑なO（m log m + n log m）（マップの構築+ n回のルックアップ）を処理している、ソートを考慮して、O（n + m log m）だけでなく、あなたのリストが既にソートされている場合には怠け者であり、トラバース中にインクリメンタルにガベージコレクションが行われます。ライブラリーから

nubByは二次複雑さを持っていますが、リストがソートされているとして、それだけで余分(i,r) Sを捨てる再帰呼び出しでエラーに呼び出しを置き換える、あまりにも、線形時間で対応することができます。

Answer 3

前述のように、タプルを使用しますが、パターンマッチングについては忘れないでください。大規模なコレクションを扱っていない場合は、マップを使用してください。

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) s2@((j,y):ys) | i == j = (y,i) : f xs ys 
            | otherwise = (x,i) : f xs s2