3

我的问题是转这个：

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

我已经尝试了很多东西，从使用lets，wheres，writer monad，制作我自己的类型，state 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
4

4 回答 4

10

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

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

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

  • 请记住，monad 背后的想法是隐藏在幕后传递计数的管道。所以你的函数的包装返回类型不会改变；他们只是长出一个单子皮肤，你可以用它>>=来把它们弄出来。

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

  • 使用你的单子！将你的守卫浮动到一个内部 case 语句中，在执行 case-match 之前，增加 state 变量。

那应该这样做！

还有一种邪恶的方法，它涉及unsafePerformIO.

于 2011-03-07T19:59:58.387 回答
4

这看起来是作家 monad 的完美工作。见http://learnyouahaskell.com/for-a-few-monads-more#writer

于 2011-03-07T19:57:08.820 回答
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

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

于 2011-03-07T19:57:28.223 回答
2

另一种方法是将累加器添加到您已有的解决方案中：

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。

于 2011-03-07T21:16:59.937 回答