replacing every pair in a list

Question

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?

• max taldykin: can you please provide example of f :: (a,a) -> [(a,a)]? how it can swap lines?
• bartavelle: I think an example would be return . swap, when a is [b].
• bartavelle: 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.

Answer 1

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.

Answer 2

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.