Swap two items in a list by its indices

Question

Is there a way to swap two elements in a list if the only thing I know about the elements is the position at which they appear in the list.

To be more specific, I am looking for something like this:

swapElementsAt :: Int -> Int -> [Int] -> [Int] 

which will behave as follows:

 > swapElementsAt 1 3 [5,4,3,2,1] -- swap the first and third elements [3,4,5,2,1] 

I thought a built-in function for this could exist in Haskell, but I could not find it.

Answer 1

Haskell does not have such a function, mainly because it does not work a bit. What are you really trying to achieve?

You can implement your own version (perhaps there is a more idiomatic way to write this). Note that I am assuming i < j , but it would be trivial to extend the function to handle other cases correctly:

 swapElementsAt :: Int -> Int -> [a] -> [a] swapElementsAt ij xs = let elemI = xs !! i elemJ = xs !! j left = take i xs middle = take (j - i - 1) (drop (i + 1) xs) right = drop (j + 1) xs in left ++ [elemJ] ++ middle ++ [elemI] ++ right 

Answer 2

Warning: differential calculus. I do not consider this answer completely seriously, since it is rather a sledgehammer. But this is a sledgehammer that I support, so why not play sports? Besides the fact that he is more likely than the investigator wanted to know what I apologize for. This is an attempt to dig a deeper structure for the reasonable answers that have already been proposed.

The class of differentiable functors offers at least the following bits and fragments.

 class (Functor f, Functor (D f)) => Diff (f :: * -> *) where type D f :: * -> * up :: (I :*: D f) :-> f down :: f :-> (f :.: (I :*: D f)) 

I guess I better unpack some of these definitions. They are the basic kit for combining functors. This thing

 type (f :-> g) = forall a. fa -> ga 

abbreviation for polymorphic types of functions for operations with containers.

It shows the constant, identity, composition, amount and product for the containers.

 newtype K ax = K a deriving (Functor, Foldable, Traversable, Show) newtype I x = I x deriving (Functor, Foldable, Traversable, Show) newtype (f :.: g) x = C {unC :: f (gx)} deriving (Functor, Foldable, Traversable, Show) data (f :+: g) x = L (fx) | R (gx) deriving (Functor, Foldable, Traversable, Show) data (f :*: g) x = fx :*: gx deriving (Functor, Foldable, Traversable, Show) 

D computes the derivative of the functor by the usual calculus rules. It describes how to present a sibling context for an element. Let's read the types of these operations again.

 up :: (I :*: D f) :-> f 

says we can make an integer f from a pair of one element and context for that element in f . It is “up” because we are moving up in the hierarchical structure, focusing on the whole, and not on one element.

 down :: f :-> (f :.: (I :*: D f)) 

In the meantime, we can decorate each element in a differentiable functional structure with its context, calculating all the ways of going down to one element in particular.

I will leave Diff instances for the base components until the end of this answer. For lists we get

 instance Diff [] where type D [] = [] :*: [] up (I x :*: (xs :*: ys)) = xs ++ x : ys down [] = C [] down (x : xs) = C ((I x :*: ([] :*: xs)) : fmap (id *:* ((x :) *:* id)) (unC (down xs))) 

Where

 (*:*) :: (fa -> f' a) -> (ga -> g' a) -> (f :*: g) a -> (f' :*: g') a (ff' *:* gg') (f :*: g) = ff' f :*: gg' g 

So for example

 > unC (down [0,1,2]) [I 0 :*: ([] :*: [1,2]),I 1 :*: ([0] :*: [2]),I 2 :*: ([0,1] :*: [])] 

selects each item in context in turn.

If f also Foldable , we get a generalized operator !! ...

 getN :: (Diff f, Foldable f) => fx -> Int -> (I :*: D f) x getN fn = foldMap (: []) (unC (down f)) !! n 

... with an added bonus, which we get both the context of the element and the element itself.

 > getN "abcd" 2 I 'c' :*: ("ab" :*: "d") > getN ((I "a" :*: I "b") :*: (I "c" :*: I "d")) 2 I "c" :*: R ((I "a" :*: I "b") :*: L (K () :*: I "d")) 

If we want the functor to propose a replacement of two elements, it would be better to differentiate twice, and its derivative would fold better. Here it goes.

 swapN :: (Diff f, Diff (D f), Foldable f, Foldable (D f)) => Int -> Int -> fx -> fx swapN ijf = case compare ij of { LT -> go ij ; EQ -> f ; GT -> go ji } where go ij = up (I y :*: up (I x :*: f'')) where I x :*: f' = getN fi -- grab the left thing I y :*: f'' = getN f' (j - 1) -- grab the right thing 

Now it’s easy to remove the two elements and reconnect them again. If we number the positions, we just need to be careful about how to remove the elements of the renumbers of the position.

 > swapN 1 3 "abcde" "adcbe" > swapN 1 2 ((I "a" :*: I "b") :*: (I "c" :*: I "d")) (I "a" :*: I "c") :*: (I "b" :*: I "d") 

As always, you cannot dig too far below the ridiculous editing operation to find some kind of differential structure at work.

For completeness. The following are other examples described above.

 instance Diff (K a) where -- constants have zero derivative type D (K a) = K Void up (_ :*: K z) = absurd z down (K a) = C (K a) instance Diff I where -- identity has unit derivative type DI = K () up (I x :*: K ()) = I x down (I x) = C (I (I x :*: K ())) instance (Diff f, Diff g) => Diff (f :+: g) where -- commute with + type D (f :+: g) = D f :+: D g up (I x :*: L f') = L (up (I x :*: f')) up (I x :*: R g') = R (up (I x :*: g')) down (L f) = C (L (fmap (id *:* L) (unC (down f)))) down (R g) = C (R (fmap (id *:* R) (unC (down g)))) instance (Diff f, Diff g) => Diff (f :*: g) where -- product rule type D (f :*: g) = (D f :*: g) :+: (f :*: D g) up (I x :*: (L (f' :*: g))) = up (I x :*: f') :*: g up (I x :*: (R (f :*: g'))) = f :*: up (I x :*: g') down (f :*: g) = C (fmap (id *:* (L . (:*: g))) (unC (down f)) :*: fmap (id *:* (R . (f :*:))) (unC (down g))) instance (Diff f, Diff g) => Diff (f :.: g) where -- chain rule type D (f :.: g) = (D f :.: g) :*: D g up (I x :*: (C f'g :*: g')) = C (up (I (up (I x :*: g')) :*: f'g)) down (C fg) = C (C (fmap inner (unC (down fg)))) where inner (I g :*: f'g) = fmap wrap (unC (down g)) where wrap (I x :*: g') = I x :*: (C f'g :*: g') 

Answer 3

Here's how I solved it:

 swapElementsAt :: Int -> Int -> [a] -> [a] swapElementsAt ab list = list1 ++ [list !! b] ++ list2 ++ [list !! a] ++ list3 where list1 = take a list; list2 = drop (succ a) (take b list); list3 = drop (succ b) list 

Here I used the convention that position 0 is first. My function expects <= b.

In my program, I like the line take a list most.

Edit: if you want to get cooler lines, look at this code:

 swapElementsAt :: Int -> Int -> [a] -> [a] swapElementsAt a another list = list1 ++ [list !! another] ++ list2 ++ [list !! a] ++ list3 where list1 = take a list; list2 = drop (succ a) (take another list); list3 = drop (succ another) list 

Answer 4

This is a strange thing, but it should work, except for errors that you can fix, because I write it on my phone. This version does not allow you to go through the same segments of the list more than necessary.

 swap' :: Int -> Int -> [a] -> [a] swap' first second lst = beginning ++ [y] ++ middle ++ [x] ++ end where (beginning, (x : r)) = splitAt first lst (middle, (y : end)) = splitAt (second - first - 1) r swap xy | x == y = id | otherwise = swap' (min xy) (max xy) 

Answer 5

There are some working answers here, but I thought a more idiomatic haskell example would be useful.

In essence, we write an infinite sequence of natural numbers with the original list to include the ordering information in the first element of the resulting pairs, and then we use a simple right fold (catamorphism) to consume the list on the right and create a new list, but this time replacing the correct ones elements. Finally, we retrieve all the other elements, discarding the first element containing the order.

Indexing in this case is based on zero (congruent with typical Haskell indexes), and the pointers must be in a range or you will get an exception (this can easily be prevented if you change the resulting type to Maybe [a]).

 swapTwo :: Int -> Int -> [a] -> [a] swapTwo fs xs = map snd . foldr (\xa -> if fst x == f then ys !! s : a else if fst x == s then ys !! f : a else x : a) [] $ ys where ys = zip [0..] xs 

And one liner performing a swap in just one pass (combining the functionality of foldr and cards in zipWith):

 swapTwo' fs xs = zipWith (\xy -> if x == f then xs !! s else if x == s then xs !! f else y) [0..] xs 

Answer 6

first-order replacement

 swap 1 jl = let (jth,ith:l') = swapHelp jl ith in jth:l' swap j 1 l = swap 1 jl swap ij (h:t) = h : swap (i-1) (j-1) t swapHelp 1 (h:t) x = (h,x:t) swapHelp n (h:t) x = (y,h:t') where (y, t') = swapHelp (n-1) tx 

• now with a precondition in accordance with the original question, that is, relaxed to 1 <= i, j <= length l for swap i jl
• relies heavily on @dfeuer's idea to reduce the problem, to replace the first element of the list with another from a given position.

Answer 7

There is also a recursive solution:

 setElementAt :: a -> Int -> [a] -> [a] setElementAt a 0 (_:tail) = a:tail setElementAt a pos (b:tail) = b:(setElementAt a (pred pos) tail) swapElementsAt :: Int -> Int -> [a] -> [a] swapElementsAt 0 b list@ (c:tail) = (list !! b):(setElementAt c (pred b) tail) swapElementsAt ab (c:tail) = c:(swapElementsAt (pred a) (pred b) tail) 

Answer 8

I really like @dfeuer's solution. However, there is still room for optimization through deforestation:

 swap' :: Int -> Int -> [a] -> [a] swap' first second lst = beginning $ [y] ++ (middle $ [x] ++ end) where (beginning, (x : r)) = swapHelp first lst (middle, (y : end)) = swapHelp (second - first - 1) r swapHelp :: Int -> [a] -> ([a] -> [a],[a]) swapHelp 0 l = ( id , l) swapHelp n (h:t) = ((h:).f , r) where ( f , r) = swapHelp (n-1) t