Swapping the two halves of a list

Learn
1

Hello! I am working on a function that swaps the two halves of a list of numbers or a string. For example, the function, when applied to ‘subway’ should return ‘waysub.’ For a list with an odd length, it would act as follows [1,2,3,4,5,6,7] would become [5,6,7,4,1,2,3]. I have attached my code here, but I am running into issues.

I used the primitive functions drop to get the last nth part of a list, take to take the first nth part of a list, rem to denote remainder, and quot to be the quotient function.

switchHalves s =
    if (rem (length s) 2) == 0 then
        ((drop (quot (length s) 2) s) 
        ++ (take (quot (length s) 2) s))
    else ((drop (quot (length s) 2) s)
        ++ (head (drop (quot (length (s + 2)) 2) s))) 
        ++(take (quot ((length s)-1) 2) s)

As I have it now, the function keeps failing on basic test cases, but I am unsure why. Does anyone have advice for me? Thanks!

1 Like
2

What kind of basic test cases? A zero-length string? A length 1 string? Does it return any sort of result at all, or error out?

All those nested (quot (length s) 2)'s make your code hard to read, and will involve repeating calculations needlessly (unless the Common Subexpression Eliminator is really sharp). I suggest you look for function quotRem, then shape your code like this:

switchHalves :: [a] -> [a]
switchHalves s = case r of
    0 -> ...
    1 -> ...
    where l      = length s
          (q, r) = l `quotRem` 2

… and then you might see parallels in the two case branches, and take advantage of r being a number that can be an argument to drop or take, so actually you can collapse together those cases.

1 Like
3

You also might want to look at ‘splitAt’ instead of manually taking the first part of the list and then the second.

https://hackage.haskell.org/package/base-4.21.0.0/docs/Prelude.html#v:splitAt

1 Like
4

The o.p.'s code is rejected

    * No instance for (Num [Char]) arising from a use of `+'
    * In the first argument of `length', namely `(s + 2)'

That (s + 2) appears in the line below else. And, yes that message is entirely baffling. Consider:

  • what is the type of s?
  • what is the type of 2?
  • then what could (s + 2) mean?
  • the compiler assumes that because of the +, this is an attempt to add something.
  • that’s why it’s talking about Num.
5

Functional programming is about splitting your problem into small functions, that can be composed to the solution. Hence I suggest to first write a function that splits an input list into the parts you care about:

assemble :: ([a],Maybe a,[a]) -> [a]
assemble (left,mid,right) = left ++ maybe [] pure mid ++ right

halves :: [a] -> ([a],Maybe a,[a])
-- specification:
-- assemble . halves = id
-- (left,mid,right) = halves xs implies length xs == length ys

Can you see how your swapping function can be written as assemble . swp . halves for a suitable

swp :: ([a],Maybe a,[a]) -> ([a],Maybe a,[a])

and what would be its implementation?

6

(No further comment from o.p. “keeps failing on basic test cases” is a funny way to put ‘fails to compile’. It can’t have been getting as far as test cases.)

There’s plenty of similar exercises with questions on StackOverflow, mostly for Python or Java. Those are for Vectors/Arrays rather than lists, so the teachable moment for the exercise is: swapping is to be in situ, needing careful calculation of indices. A corner test case that might be a trap is a zero-length input. That should produce a zero-length output, not an index out of bounds.

Haskell lists have to access iteratively from the front, not direct by indexing. Presumably the intended teachable moment is that serial access like that is poor for performance. Avoid multiple scans of the list. We must scan once to get the length; then again to swop it about. o.p.'s code (as well as far too many calls to length and arithmetic over it) has repeated takes and drops.

So here’s my model answer. @ikervagyok’s suggestion is right on the money:

  • splitAt n s returns the same result as (take n s, drop n s), but scans s only once.
  • Note also the pro tip that splitAt 0 s is valid and returns ([], s).
  • So in effect a zero-length split achieves the same guardedness as @olf’s Maybe/maybe. (I suspect introducing pure would be rather advanced for this level of exercise.)
    switchHalves :: [a] -> [a]
    switchHalves s = su ++ (m ++ pre)         -- suffix ++ middle ++ prefix
        where l           = length s
              (q, r)      = l `quotRem` 2
              (pre, m_su) = splitAt q s
              (     m,su) = splitAt r m_su
  • You’ll note the lack of if/then/else or case of from my earlier suggestion or Maybe. Where did that go?
  • quotRem rounds down, so if the list is even length, q will point to the exact middle, if odd, it’ll point to just before the middle element.
  • splitAt q s will therefore, if even length give exactly the two halves, if odd length, the middle element will be at the head of m_suthe second of the pair.
  • If even length, the remainder r will be zero, so the second splitAt r m_su will give m empty, su the entire right hand half.
  • If odd length, r will be one, so the second splitAt snips off m as the middle element.
  • (In effect, r being zero or one is doing the same job as the if/case/Maybe. Because splitAt has a pattern guard on its arg being zero.)
  • One extra efficiency wrinkle: ++ also needs to scan down its left argument, to append at the end. m is at most length one, so appending to that (m ++ su) is preferable to appending (su ++ m) then appending pre to the result. ++ is right-associative anyway, but I’ve put explicit parens as belt and braces.
1 Like