строка для мульти установить Haskell строка

Question

Преобразовать в мульти установлен как на примере ниже:

"bacaba" -> [(Ь, 2), (а, 3), (с, 1)]

type MSet a = [(a,Int)] 

convert :: Eq a => [a] -> MSet 

Что не так с моим кодом и что это лучший способ сделать это? ty

convert :: Eq a => [a] -> MSet a 
convert [] = [] 
convert (x:xs) = ((x,1+count x xs) : converte xs) 
    where count x [] = 0 
     count x (y:ys) = if (x == y) then 1 + count x ys else count x ys 

Answer 1

что является лучший способ сделать это?

Ваш код выполняет O(n^2); Если тип является экземпляром Ord класса типа (как в вашем примере), с помощью Data.Map вы можете получить O(n log n) производительность:

import Data.Map (toList, fromListWith) 

convert :: (Ord a) => [a] -> [(a, Int)] 
convert xs = toList . fromListWith (+) . zip xs $ repeat 1 

Это приведет к нужным пунктам, но список будет отсортирован по ключам:

\> convert "bacaba" 
[('a',3),('b',2),('c',1)] 

Если необходимо сохранить порядок, то

import qualified Data.Map as M 
import Data.Map (delete, fromListWith) 

convert :: (Ord a) => [a] -> [(a, Int)] 
convert xs = foldr go (const []) xs . fromListWith (+) . zip xs $ repeat 1 
    where 
    go x f cnt = case M.lookup x cnt of 
     Just i -> (x, i): f (x `delete` cnt) 
     Nothing -> f cnt 

, который выведет:

\> convert "bacaba" 
[('b',2),('a',3),('c',1)] 

Answer 2

Вы почти находитесь.

Проблема заключается в вашем рекурсивном вызове функции convert. Поскольку вы уже вычислили количество символов для определенного символа, вам не нужно их снова вычислять. Просто используйте filter функцию, чтобы удалить этот персонаж при звонке convert:

convert :: Eq a => [a] -> MSet a 
convert [] = [] 
convert (x:xs) = (x,1+count x xs) : convert (filter (\y -> y /= x) xs) 
    where count x [] = 0 
     count x (y:ys) = if (x == y) then 1 + count x ys else count x ys 

Или написал более лаконично:

convert :: Eq a => [a] -> MSet a 
convert [] = [] 
convert (x:xs) = (x,1+count x xs) : convert (filter (/= x) xs) 
    where count x [] = 0 
     count x (y:ys) = if (x == y) then 1 + count x ys else count x ys 

Demo в GHCI:

ghci| > convert "bacaba" 
[('b',2),('a',3),('c',1)]