Geek asks and answers

Haskell Inserstion Sort Account

My problem is to do 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

To the solution that tracks the number of comparison attempts, here is the skeleton of the code I need to create:

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

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

I tried a lot of what the let, wheres, monad writer used, creating my own type, state monad, and I seem to just redefine something because I keep running into the problem: "y: ins x ys", because what this function returns must be (Int, [a]) and: does not work on the tuple. I tried to break it to do something like this

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

, , , ins , , . - ? , , ...

Ezra:

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  =     y : ins' (x,i+1) ys

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

, :

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

. , , . 1, , .

, "", , . , snd, , sum.

+2

, , :

  • . Sum, .

  • : ? ins , , iSort ins, , .

  • , , , . , ; , >>=, .

  • , : . tempVar <- ins foo do-block , .

  • ! case case .

!

, unsafePerformIO.

+10

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

+4
source

Try the following:

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 note that this is pretty inefficient.

+3
source

More articles:


All Articles