Merge Sort: exercise
OK, so let's see. arr x = [x] is usually called wrap, or just the operator section (:[]) is used. But map can also be written with list comprehension, giving us

sort :: (Ord a) =&gt; [a] -&gt; [a]
sort xs = reduce True [[x] | x &lt;- xs]


I find it much more visually apparent that way. We usually use short variable names in Haskell, with the same goal. When I see a variable fw and then not fw I get it that it is a toggle, a flag of some sorts, I don't need to see the long name like forwardorbackwardsflag explaining it to me in words while at the same time obscuring this visually. So we get

  where
    reduce _ []    = []
    reduce fw [xs] = if fw then xs else reverse xs
    reduce fw s    = reduce (not fw) (combine fw [] s)


we make it an internal function to sort, because this is what it is. It has no otherwise uses on its own. It's too tailored for the specific use here. -- (x:[]) is written also [x], which is a lot simpler. -- We don't have to annotate types of everything. Here reduce is defined right under its use site, so we see that the initial value of fw is True. For me, it is self-documenting enough, but YMMV. Next, combine. There's no need to name all those interim entities. The name of the function itself isn't right, it's too generic. What it does, specifically, is process the elements of its input list in pairs:

    rpairs fw acc []       = acc
    rpairs fw acc [x]      = reverse x : acc
    rpairs fw acc (x:y:zs) = rpairs fw (merge fw x y : acc) zs


It also builds its result in reversed order. We can make it an internal function to reduce, so that its argument fw could be referred to in rpairs body. At the same time there is no need in the separate accumulator really, we can just build the result naturally, in lazy fashion:

  where
    reduce _ []    = []
    reduce fw [xs] = if fw then xs else reverse xs
    reduce fw s    = reduce (not fw) (reverse $ pairs s)
      where
        pairs []       = []
        pairs [x]      = [reverse x]
        pairs (x:y:zs) = merge fw x y : pairs zs


For merge to be able to refer to fw it too should be put here as an internal function to reduce. It is usual to split such functions into two like you did, the interface function ("the wrapper") and the internal "worker" function, except that normally the worker is made internal to the wrapper. But here the wrapper itself is too specialized, it reverses its result so is unlikely to be useable in general, so no need for the split. Thus we arrive at:

sort    :: (Ord a) =&gt; [a] -&gt; [a]
sort xs = reduce True [[x] | x &lt;- xs]
  where
    reduce _  []   = []
    reduce fw [xs] = if fw then xs else reverse xs
    reduce fw s    = reduce (not fw) . reverse . pairs $ s
      where
        pairs (x:y:t)     = rmerge [] x y : pairs t
        pairs [x]         = [reverse x]
        pairs []          = []

        rmerge acc [] []  = acc
        rmerge acc xs []  = reverse xs ++ acc
        rmerge acc [] ys  = reverse ys ++ acc
        rmerge acc (x:xs) (y:ys)
          | fw &amp;&amp; x &lt;= y || not fw &amp;&amp; x &gt; y
                          = rmerge (x:acc) xs (y:ys)
          | otherwise     = rmerge (y:acc) (x:xs) ys


There's no shame in calling rmerge with the initial value as we do here, it's just an internal function here, called from another internal function.



But actually the reversals that rmerge performs are unnecessary, because of Haskell's lazy evaluation. merge now becomes a general function, usable in general. pairs too. reduce performs the same processing step on its input iteratively until a condition is met - there's a higher order function until that already captures this pattern. This leads to some more simplification of the code:

sort    :: (Ord a) =&gt; [a] -&gt; [a]
sort [] = []
sort xs = head $ until (null . tail) (pairwise merge) [[x] | x &lt;- xs]
                                  -- (reverse . pairwise merge) 
pairwise f (x:y:t) = f x y : pairwise f t
pairwise _ t       = t

merge xs []        = xs
merge [] ys        = ys
merge (x:xs) (y:ys)
       | x &lt;= y    = x : merge  xs (y:ys)
       | otherwise = y : merge (x:xs) ys


I think we would need to toggle between &lt;= and &lt; in merge to ensure the sort's stability, if we were to proceed by (reverse . pairwise merge) steps. But, perhaps we can just throw that reverse away.