Haskell 插入排序计数

Question

我的问题是把它变成

 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

一个解决方案，跟踪它进行比较的次数，这里是我需要生成的代码的骨架：

 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 ... 

我已经尝试了很多使用 let、wheres、writer monad 的方法，制作我自己的类型，状态单子，我似乎只是忽略了一些东西，因为我一直遇到“y : ins x ys”的问题，因为该函数返回的应该是 (Int, [a]) 和：不适用于元组。我尝试将其拆分以执行类似的操作

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

，但似乎不认为 ins 在该版本中返回元组，因此我猜它只是没有模式匹配。我的主要问题是我现在应该看哪里？我在这个问题上工作了很长时间，这个问题开始让我感到沮丧，因为它看起来很简单......

在以斯拉的帮助下回答：

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 

Answer 1

将纯代码转换为单子代码可能很棘手，希望这些技巧能给您正确的想法：

• 选择一个单子。您还可以在 Sum monoid 上使用 writer，但您可能会发现基于状态的代码更直接。

• 考虑代码中的所有表达式：哪些表达式可能导致状态变量递增？ ins 进行了比较，但更巧妙的是，因为对 iSort 的递归调用可以调用 ins，它也是您将拥有的这些表达式之一请记住。

• 请记住，单子背后的想法是隐藏在幕后传递计数的管道。因此，函数的包装返回类型不会改变；它们只是长出一层单子皮肤，您可以使用 >>= 将它们取出。

• 回想一下所有可能导致状态变量递增的表达式：这些是您的单子调用。将它们重写为 do 块内的 tempVar <- ins foo 形式，并用您分配的临时变量替换旧位置。

• 使用你的单子！将您的防护浮动到内部 case 语句中，并在执行 case-match 之前，增加状态变量。

那应该可以了！

还有一种邪恶的方法可以做到这一点，其中涉及unsafePerformIO。

Answer 2

对于作家单子来说，这看起来是一份完美的工作。请参阅http://learnyouahaskell.com/for-a-few-monads-more#作家

Answer 3

试试这个：

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

但请注意，这是相当低效的。

Answer 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。