Haskell Inserstion sort count

My problem is to turn this:

 iSort :: Ord a => [a] -> [a]
 iSort [] = []
 iSort (x:xs) = ins x (iSort xs)

 ins x [] = [x]
 ins x (y:ys)
   | x <= y    = x : y : ys
   | otherwise = y : ins x ys

Into a solution that keeps track of the number of times it makes a comparison, here a skeleton of the code I need to produce:

 iSortCount :: Ord a => [a] -> (Integer, [a])
 iSortCount [] = ...
 iSortCount (x:xs) = ...

 insCount x (k, [])     = ... 
 insCount x (k, (y:ys)) -- Count the times when it reach's here     
   | x <= y    =  ...
   | otherwise = ...
   where ... 

I've tried a lot of things from using lets, wheres, writer monad, making my own type, the state monad, and I seem to just be over looking something because I keep running into the problem with "y : ins x ys" because what that function returns should be (Int, [a]) and : does not work on a tuple. I tried to split it up to do something like this

do
(a,b) <- ins x (k+1, ys)
return (k, (y : b))

but it seems to not think that ins returns a tuple when it did in that version so it just wasn't pattern matching on it i guess. My main question is where I should look now? I worked on this for a long time and this problem is starting to frustrate me cause it look so easy...

Answer with Ezra help:

iSort' [] = []
iSort' (x:xs) = ins' x (iSort' xs)

ins' x [] = [x]
ins' (x,i) (y:ys)
    | x <= fst y = (x,i+1) : y : ys
    | otherwise  =开发者_如何学Python     y : ins' (x,i+1) ys

countInsertions x = sum $ map snd $ iSort' $ zip x $ repeat 0 

---

Conversion of pure code to monadic code can be tricky, hopefully these tips can give you the right idea:

• Pick a monad. You could also use writer on the Sum monoid, but you may find the state-based code more straight-forward.

• Consider all of the expressions in your code: which expressions could cause the state variable to increment? ins makes a comparison, but more subtly, because the recursive call to iSort could call ins, it also one of these expressions you'll have to keep in mind.

• Remember that the idea behind a monad is to hide the plumbing of passing the count behind the scenes. So the wrapped return types of your functions don’t change; they just grow a monadic skin which you can use >>= to get them out.

• Recall all of the expressions that could cause the state variable to increment: those are your monadic calls. Rewrite them into tempVar <- ins foo form inside a do-block, and replace the old locations with the temporary variables you allocated.

• Use your monad! Float your guard into an inner case statement, and before performing the case-match, increment the state variable.

And that should do it!

There's also an evil way to do it, which involves unsafePerformIO.

---

This looks like the perfect job for the writer monad. See http://learnyouahaskell.com/for-a-few-monads-more#writer

---

Try this one:

import Control.Monad.State

type Counter = State Int

incr :: Counter ()
incr = modify (+1)

ins :: Ord a => a -> [a] -> Counter a
ins x [] = return [x]
ins x (y:ys)
  | x <= y    = incr >> return $ x : y : ys
  | otherwise = incr >> ins x ys >>= (y :)

iSort :: Ord a => [a] -> Counter [a]
iSort [] = return []
iSort (x:xs) = iSort xs >>= ins x

cSort :: Ord a => [a] -> ([a],Int)
cSort = flip runState 0

But please notice, that this is rather inefficient.

---

Another approach would to just add an accumulator to the solution that you already have:

iSort' [] = []
iSort' (x:xs) = ins' x (iSort' xs)

ins' x [] = [x]
ins' (x,i) (y:ys)
    | x <= fst y = (x,i) : y : ys
    | otherwise  =     y : ins' (x,i+1) ys

countInsertions x = sum $ map snd $ iSort' $ zip x $ repeat 1 

This solution has the benefit of being familiar. I just replaced each item in the list with a tuple representing the item and the number of times it's been shuffled. They're initialized to 1 because I count everything as having been shuffled at least once.

The sort routine is largely the same, but a "setup" function is now needed, so you won't want to provide the list of tuples, but the list of items. Since it's the second item in the tuple, we need snd, and since we want the total we use sum.