リスト内の要素をInt（Haskell）のリストで削除する

Question

私は、Intのリストと一般的なタイプのリストaのリストを作成し、Intのリストにインデックスを持つすべての要素を削除する関数を書いています。

例えば：removeEl [1,3,4] [1,2,3,4,5,6]リターン[1,3,6] またはremoveEl [1,2] "Firefox"リターン"Fefox"

ここに私の試みです：

removeEl :: [Int] -> [a] -> [a] 
removeEl [] xs = [] 
removeEl ns [] = [] 
removeEl (n:ns) (x:xs) | n == 0 = removeEl ns xs 
         | n > 0 = x:removeEl (n-1) xs 

私はそれが失敗しない[Int]、(n-1)がIntで実現しています。使用する補助機能を記述する必要がありますか？

Answer 1

新しいリストを渡す必要がありますが、2番目の引数のすべての要素の位置がシフトされているため、リスト内のすべての項目を減らす必要があります。これは、実際にhead要素を削除したかどうかにかかわらず当てはまります。

removeEl (n:ns) (x:xs) | n == 0 = removeEl (map pred ns) xs 
         | n > 0 = x:removeEl (map pred (n:ns)) xs 

あり、これをリファクタリングする機会がたくさんですが、私がプレイしたものを大幅に簡素感じません。

はまた、あなたの最初の基本ケースは間違っている：

remove [] xs = xs 

は（覚えておいてください、これは場合にのみ機能します：インデックスリストにアイテムで、あなたはすべて、ない何を返すようにしたいです最初の引数は単調に増加している）

---

ます。また、リスト内包して明示的な再帰を避けることができ

：

removeEl ns xs = [x | (n,x) <- zip [0..] xs, not(n `elem` ns)] 

Answer 2

私はあなたのアルゴリズムはnは、リスト内の要素の数であるとmを削除するインデックスの数であるO(n*m)、であると考えています。また、インデックスのリストを注文する必要があるという不幸な要件もあります。インデックスの注文を必要としない~O(n*log(m))ソリューションがあります。

import qualified Data.Set as Set 

removeE1 indices xs = go 0 xs 
    where is = Set.fromList indices 
     go _ [] = [] 
     go n (y:ys) | n `Set.member` is = go (n+1) ys 
        | otherwise   = y : go (n+1) ys 

これは、ハッシュマップを使用して少し改善することができます。