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比較しますが、より微妙に、への再帰呼び出しはを呼び出すことiSortができるため、insこれらの式の1つでもあることに注意する必要があります。

  • モナドの背後にある考え方は、舞台裏でカウントを渡す配管を隠すことであることを忘れないでください。したがって、関数のラップされた戻り型は変更されません。>>=彼らはあなたがそれらを取り出すために使用できるモナディックスキンを成長させるだけです。

  • 状態変数をインクリメントさせる可能性のあるすべての式を思い出してください。これらはモナディック呼び出しです。それらをdo-block内の形式に書き直しtempVar <- ins foo、古い場所を割り当てた一時変数に置き換えます。

  • あなたのモナドを使ってください！ガードを内側のcaseステートメントにフロートさせ、case-matchを実行する前に、状態変数をインクリメントします。

そしてそれはそれをするべきです！

それを行うための邪悪な方法もあります。これにはが含まれunsafePerformIOます。

于 2011-03-07T19:59:58.387 に答える
4

これは作家モナドにとって完璧な仕事のように見えます。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すべてが少なくとも1回シャッフルされたと見なされるため、これらはに初期化されます。

ソートルーチンはほとんど同じですが、「セットアップ」機能が必要になったため、タプルのリストではなく、アイテムのリストを提供する必要があります。タプルの2番目の項目であるため、が必要です。snd合計が必要なため、を使用しますsum。

于 2011-03-07T21:16:59.937 に答える