# replacing every pair in a list

I need a function (I named it applyToEveryPair) that works on lists, e.g. [x0,x1,x2,x3,...], and uses a function f:: (a,a) -> [(a,a)]. For every (distinct) pair (xi,xj), i/=j of the list I want all lists where xi is replaced by yik and xj is replaced by yjk where xik is the output of f.

This visualizes input and output

[a0, a1 ,a2 ,a3 ]  -- input to applyToEveryPair
|   |
|   |
v   v
f(a0, a1) =[(b0,b1),(c0,c1)]
|   |
v   v
[b0, b1, a2, a3]  -- to be included in output
[c0, c1, a2, a3]  -- to be included in output
...            -- more output
|      |    -- now combine (a3,a1)
\    /
\  /
\/
/\
/  \
f(a3, a1) =
[(d3, d1)]
\  /
\/
/\
/  \
/    \
[a0, d1 ,a2 ,d3 ]  -- to be included in output

A use case would be to input a matrix and compute all resulting matrices for every (pairwise) line swap (f swaps lines), or, in my case, all possible move in a solitaire game from one stack of cards to another.

Long story, short code; This is how I do it so far:

applyToEveryPair :: ((a,a) -> [(a,a)]) -> [a] -> [[a]]
applyToEveryPair f (xs) = do i<-[0..length xs - 1]
j<-[0..length xs - 1]
guard (i /= j)
(x',y') <- f (xs !! i, xs !! j)
return . setList i x' . setList j y' $xs -- | setList n x xs replaces the nth element in xs by x setList :: Int -> a -> [a] -> [a] setList = go 0 where go _ _ _ [] = [] go i n x' (x:xs) | i == n = x':xs | otherwise = x:(go (i+1) n x' xs) I think comonads are overkill here, and I have not understood Lenses (yet), but have a vague feeling lenses apply here. The solution I use feels not very haskellish. I want to know if this is a good way to write it, but especially the double use of setList looks terrible to me. How to speed up / beautify this code? • can you please provide example of f :: (a,a) -> [(a,a)]? how it can swap lines? – max taldykin Apr 14 '14 at 7:01 • I think an example would be return . swap, when a is [b]. – bartavelle Apr 14 '14 at 9:14 • I can't find a much better way to do this, but I would suggest using Vector instead of [], as it has much better indexed access performance, and you wouldn't have to implement setList. – bartavelle Apr 14 '14 at 10:38 ## 2 Answers You can use the lens library to remove the need for the setList function. The ix lens does this, giving read+write access to an element at an index. The type of this is: ix :: Index m -> Traversal' m (IxValue m) Or, for lists in particular: ix :: Int-> Traversal' [a] a Using the .~ operator, the value of a lens can be set. So to remove need for the setList funtion, just use this: applyToEveryPair2 :: ((a,a) -> [(a,a)]) -> [a] -> [[a]] applyToEveryPair2 f (xs) = do i<-[0..length xs - 1] j<-[0..length xs - 1] guard (i /= j) (x',y') <- f (xs !! i, xs !! j) return . (ix i .~ x') . (ix j .~ y')$ xs

The other thing to notice about your code is it will call every pair of elements twice: eg it will call the supplied function with the item at index 2 and 5, then with the items at indexes 5 and 2. I'm not sure if this is intended.

I don't think there is a much nicer way to do this. However, on the performance side, you should definitely use a data structure with constant time random access, such as Vector. That would save you from writing the setList function.