4
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ can you please provide example of f :: (a,a) -> [(a,a)]? how it can swap lines? \$\endgroup\$ – max taldykin Apr 14 '14 at 7:01
  • \$\begingroup\$ I think an example would be return . swap, when a is [b]. \$\endgroup\$ – bartavelle Apr 14 '14 at 9:14
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – bartavelle Apr 14 '14 at 10:38
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.