Счетчик вставок в 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, writad monad, создавая свой собственный тип, монаду состояния, и я, кажется, просто перебрал что-то, потому что продолжаю сталкиваться с проблемой с "y: ins x ys "потому что то, что возвращает эта функция, должно быть (Int, [a]) и: не работает с кортежем.Я пытался разделить его, чтобы сделать что-то вроде этого

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 

Answer 1

Преобразование чистого кода в монадический код может быть сложным, надеюсь, эти советы могут дать вам правильную идею:

• Выберите монаду.Вы также можете использовать Writer на моноиде Sum, но вы можете найти код на основе состояния более простым.

• Рассмотрите все выражения в вашем коде: какие выражения могут вызватьпеременная состояния для увеличения?ins делает сравнение, но более тонко, потому что рекурсивный вызов iSort может вызвать ins, это также одно из этих выражений, которое вы должны иметь в виду.

• Помните, что идея монады в том, чтобы спрятать трубку прохождения графа за кулисами.Таким образом, возвращаемые типы ваших функций не изменяются;они просто вырастают монадический скин, который вы можете использовать >>=, чтобы вывести их.

• Напомним все выражения, которые могут привести к увеличению переменной состояния: это ваши монадические вызовы.Перепишите их в форму tempVar <- ins foo внутри do-блока и замените старые местоположения временными переменными, которые вы выделили.

• Используйте свою монаду!Переместите вашу охрану во внутренний оператор case, и перед выполнением case-match увеличивайте переменную состояния.

И это должно быть сделано!

Есть и злоспособ сделать это, который включает в себя unsafePerformIO.

Answer 2

Это похоже на идеальную работу для писателя монады.Смотри http://learnyouahaskell.com/for-a-few-monads-more#writer

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.