1

I want to write a function which takes a list of elements l, a list of indices i, and a list of replacement values v. The function will replace the values in l corresponding to the indices in i with the corresponding value in v.

Example: If l = [1,2,3,4,5,6], i = [0,2], and v = [166,667], then replaceValues l i v == [166,2,667,4,5,6]

My function:

--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)

This function manages to correctly replace the value at the first index in i, but it misplaces all of the following values. In the example above, it would give the output [166,667,3,4,5,6].

Improve this question

3 Answers 3

Reset to default
3

The problem with your implementation is that you aren't keeping track of which index you're currently at.

First of all, you're better off considering using [(Int,a)] rather than [Int] and [a] arguments separate to ensure that the "lists" are equal in length.

An alternate implementation is as follows:

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

What's happening here:

  • Tag each value with its index

  • See if there's a replacement value for that index: if there is, use it; otherwise, use the original value.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

This is a very terse implementation. However, I get a type error on the rs of the function rep (i,a)
@kienjakenobi: whoops, forgot the extra import! (i.e. fromMaybe) and it should use rsM, not rs :s Fixed that now.
Thank you very much. This does indeed work. I will think about it more to see that I understand it entirely.
This will break up if you will tend to use replacement on large collections of data, it also will consume more memory. On 1M of items it probably will die :)
@jdevelop: True, but I figured that that wouldn't be the case here ;-) In that case, barsoap's implementation would work, assuming both lists are lazily created (though I would wonder what you were doing that you wanted to do index-based replacement with such a large number of items to replace that memory is an issue).
|
2

The first thing that springs to mind is that you should use a list of tuples to specify the replacement, that is, work with

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

... you can use zip to convert your two lists into that format. Then I'm going to stipulate that that list is sorted by the first element of the tuple (sortBy), and that there are no duplicate indices in it (nubBy). The rest is a simple recursion, replacing as you go, with linear complexity and being maximally lazy:

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"

Beware of the code, though, I have only proven it to be correct, not actually tried it.

Using a map works too, of course, but then you're dealing with an complexity of O(m log m + n log m) (construct map + n times lookup) instead of O(n), or, taking sorting into account, O(n + m log m), as well as lose the capability of being lazy in case your list is already sorted and have the replacements incrementally garbage collected while you traverse.

nubBy from the library has quadratic complexity, but as the list is sorted it can be dealt with in linear time, too, just replace the call to error with a recursive call throwing away superfluous (i,r)s.

Improve this answer

1 Comment

Thank you very much for this alternate solution. Must sleep now, but I will evaluate it and think about it, too.
0

as said before, use tuples - but don't forget about pattern matching. Or use Map if you are not dealing with large collections

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
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.