CODEWITHSUNDEEP
listhaskellswap
Alan Kantserov
Alan Kantserov

Reputation: 37

How to swap last 2 elements in Haskell?

I need to swap last 2 elements of a list in Haskell

Here is what I've got so far and it doesn't compile.

swapLastTwo :: [a] -> Maybe [a]
swapLastTwo list = case list of
    xs:x:y -> Just (xs:y:x)
    _ -> Nothing

However this one compiles:

swapFirstTwo :: [a] -> Maybe [a]
swapFirstTwo list = case list of
    x:y:xs -> Just (y:x:xs)
    _      -> Nothing

What is the difference? I guess there is a problem with these x y xs etc. I am not quite certain with them.

Compiler gives this error

 • Couldn't match expected type ‘[[a]]’ with actual type ‘a’
       ‘a’ is a rigid type variable bound by
         the type signature for:
           swapLastTwo :: forall a. [a] -> Maybe [a]
         at BuiltInList.hs:69:16
     • In the second argument of ‘(:)’, namely ‘x’
       In the second argument of ‘(:)’, namely ‘y : x’
       In the first argument of ‘Just’, namely ‘(xs : y : x)’
     • Relevant bindings include
         y :: [a] (bound at BuiltInList.hs:71:10)
         x :: a (bound at BuiltInList.hs:71:8)
         xs :: a (bound at BuiltInList.hs:71:5)
         list :: [a] (bound at BuiltInList.hs:70:13)
         swapLastTwo :: [a] -> Maybe [a] (bound at BuiltInList.hs:70:1) Failed, modules loaded: none.

Thank you.

Upvotes: 1

Views: 1497

Answers (4)

leftaroundabout
leftaroundabout

Reputation: 120711

First, note that there's no reason to use case for this kind of pattern-matching – just match right in the function arguments:

swapFirstTwo :: [a] -> Maybe [a]
swapFirstTwo (x:y:xs) = Just (y:x:xs)
swapFirstTwo _ = Nothing

Now... Haskell lists aren't symmetric. At all. Anything you do with pattern-matching will always focus on the left end on the list, that's why your swapLastTwo doesn't work. You can only get at the right end by disassembling the whole list (if at all, namely, this only works for finite lists). This can be done through recursion. First write out the base cases:

swapLastTwo [] = Nothing
swapLastTwo [_] = Nothing
swapLastTwo [x,y] = Just [y,x]

For any list longer than that, you need to first pop off elements and then later put them back. Hence the recursive clause

swapLastTwo (x:xs) = (x:) <$> swapLastTwo xs

In case you're wondering what <$> is: in this case, it simply prepends x to whatever Just result the recursive call may yield.

An alternative, kind of brute-force solution would be

swapLastTwo = fmap reverse . swapFirstTwo . reverse

This actually has much worse runtime characteristics in this example, butSee Luke's comment generally, such “compose simple functions instead of doing manual recursion” solutions are often much more effective.

Upvotes: 8

luqui
luqui

Reputation: 60463

Here's the productive version I mentioned for fun.

swapLastTwo :: [a] -> [a]
swapLastTwo [] = []
swapLastTwo [x] = [x]
swapLastTwo [x,y] = [y,x]
swapLastTwo (x:xs) = x : swapLastTwo xs

It's lazy:

ghci> swapLastTwo [1,2,3,4,5]
[1,2,3,5,4]
>>> swapLastTwo (1:2:3:4:5:undefined)
[1,2,3*** Exception: Prelude.undefined

And you can also do it with Maybe (which is why I wrote this answer, because I enjoy the asJust pattern, and the way it can make strict things productive when properly placed — essentially we are codifying some extra structural information that is not clear from the types alone).

swapLastTwo' :: [a] -> Maybe [a]
swapLastTwo' [] = Nothing
swapLastTwo' [x] = Nothing
swapLastTwo' [x,y] = Just [y,x]
swapLastTwo' (x:xs) = (x:) <$> asJust (swapLastTwo' xs)
    where
    assertJust ~(Just x) = Just x

Which is also lazy

ghci> swapLastTwo' (1:2:3:4:5:undefined)
Just [1,2,3*** Exception: Prelude.undefined
ghci> swapLastTwo [1]
Nothing

In a lazy dependent-typed world, would swapLastTwo' (with an appropriately accurate type) be lazy without any extra effort, the way swapLastTwo is here?

Upvotes: 3

Redu
Redu

Reputation: 26161

I can not make sure if this more efficient than @leftaroundabout solution but just for a variety you may use lists as an applicative functor such as;

swapLastTwo :: [a] -> Maybe [a]
swapLastTwo []  = Nothing
swapLastTwo [_] = Nothing
swapLastTwo xs  = Just (concat $ [reverse . drop 2 . reverse, take 2 . reverse] <*> [xs])

*Main> swapLastTwo []
Nothing
*Main> swapLastTwo [1]
Nothing
*Main> swapLastTwo [1,2,3,4,5]
Just [1,2,3,5,4]

Upvotes: 0

Chad Gilbert
Chad Gilbert

Reputation: 36375

When using the cons operator :, the last item on the right of the colon is a list, while everything to the left is a single item in the list. That is why swapFirstTwo compiles successfully: the x and y from x:y:xs are individual items, while xs is a list.

You can confine a pattern match to a two element List by either of these methods:

x:y:[] -> ...
-- or
[x,y] -> ...

Upvotes: 1

Related Questions