haskell, как проверить, равны ли два списка кортежей и принять объединение

Question

Я новый самообладатель в Хаскеле.во-первых, я хочу написать функцию, чтобы проверить, равны ли два списка кортежей.Каждый кортеж имеет ключ и значение

. Во-вторых, я хочу, чтобы функция объединила два списка кортежей

. Я пробовал несколько способов и пробовал много раз, но, кажется, не смог удовлетворить мои требования.кто-нибудь может мне помочь?заранее спасибо.

Answer 1

Поскольку a является только членом Eq, сортировка или группировка невозможны.

import Data.List(nub, (\\))
import Data.Monoid(getSum)

type Times = Int
type Lis a = [(a,Times)]

lisEqual :: Eq a => Lis a -> Lis a -> Bool
lisEqual xs xs' = length xs == length xs' && xs \\ xs' == []

lisSum :: Eq a => Lis a-> Lis a-> Lis a
lisSum xs xs' = fmap f $ getKeys l 
  where
    f x = (,) x (getSum . foldMap (pure . snd) . filter ((x ==) . fst) $ l)                         
    l = xs ++ xs'
    getKeys = nub . fst . unzip

Answer 2

Мое решение довольно простое.Для того, чтобы сравнить такие списки, вам нужно сначала заказать их.Суммирование двух списков по ключам может быть выполнено рекурсивно, если ключ имеет тип Ord и вы заказываете по ключу оба списка.Я не использую ваши псевдонимы просто для того, чтобы сделать их примитивными, но вы можете легко адаптировать их

eqList xs vs = xs' == vs' 
                 where xs' = sortOn fst xs
                       vs' = sortOn fst vs

sumKeyValue' :: [(Char, Integer)] -> [(Char, Integer)] -> [(Char, Integer)]
sumKeyValue' [] v  = v
sumKeyValue' x  [] = x
sumKeyValue' x@((a, c):xs) v@((b,d):vs) 
  | a == b = (a, c + d):sumKeyValue xs vs
  | a < b  = (a,c):sumKeyValue xs v
  | a > b  = (b,d):sumKeyValue x vs

sumKeyValue xs vs = sumKeyValue' xs' vs' 
  where xs' = sortOn fst xs
        vs' = sortOn fst vs

Answer 3

Это версия, которую я предложил в комментариях.Сначала проверьте списки на дубликаты ключей и одинаковую длину, чтобы убедиться, что нам нужно только проверить, все ли ключи l1 являются ключами l2.Затем выполните поиск и проверьте, равны ли значения:

lisEqual l1 l2 =
  (nodups $ map fst l1) &&
  (nodups $ map fst l2) &&
  length l1 == length l2 &&
  and (map (\ (x,k) -> case (occOfA x l2) of
                    Just n -> n == k
                    Nothing -> False
                  ) l1)

Поиск возвращает Maybe b, чтобы указать на неудачный поиск с Nothing.

occOfA :: Eq a => a -> [(a,b)] -> Maybe b
occOfA a []   = Nothing
occOfA a ((x,n):xs) =
  if a == x then Just n
            else occOfA a xs

Проверка дубликатовпросто рекурсия

nodups :: Eq a => [a] -> Bool
nodups [] = True
nodups (x:xs) = not (x `elem` xs) && (nodups xs)

Некоторые тестовые случаи

t :: Int -> Bool
t 0 = lisEqual [(2,3), (1,2)] [(1,2), (2,3)] == True
t 1 = lisEqual [(2,3), (1,2)] [(1,3), (2,3)] == False
t 2 = lisEqual [(2,3), (1,2), (1,3)] [(1,3), (2,3)] == False
t 3 = lisEqual [(2,3)] [(1,3), (2,3)] == False

можно проверить как

*Main> and $ map t [0..3]
True

Я немного ленив для вычисления сумм, я определяюфункция lisSum1, которая собирает все ключи из списка и соответственно суммирует значения.Для lisSum мне просто нужно объединить два списка:

lisSum l1 l2 = lisSum1 $ l1 ++ l2

lisSum1 :: Eq a => [(a,Int)] -> [(a,Int)]
lisSum1 list =
   reverse $ foldl (\acc k ->  (k, sumList $ map snd (select k list) ) : acc ) -- create pairs (k, ksum) where ksum is the sum of all values with key k
   [] (rdups $ map fst list)

С некоторыми вспомогательными функциями:

rdups :: Eq a => [a] -> [a]
rdups [] = []
rdups (x:xs) = x : rdups (filter (/= x) xs)

sum l = foldl (+) 0 l

select k list = filter (\ (x,_) -> k == x) list

Некоторые тесты снова:

s :: Int -> Bool
s 0 = lisSum [('a',1), ('a',2)] [('a',3)] == [('a',6)]
s 1 = lisSum [(1,2), (2,3)] [(2,4),(3,1)] == [(1,2),(2,7),(3,1)]
s 2 = lisSum [(1,2), (2,3), (2,4), (3,1)] [] == [(1,2),(2,7),(3,1)]
s 3 = lisSum [(1,2), (2,3), (3,1)] [] == [(1,2),(2,3),(3,1)]


*Main> map s [0..3]
[True,True,True,True]

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

*Main> lisEqual [(1,1),(1,2)] [(1,1),(1,2)]
False

Если мы исправим рефлексивность, мы можем просто удалить исходное ограничение на дубликаты и определить:

lisEqualD [] []    = True
lisEqualD (_:_) [] = False
lisEqualD [] (_:_) = False
lisEqualD (x:xs) ys =
    case (remFirst x ys) of
        Nothing -> False
        Just zs -> lisEqualD xs zs

remFirst x [] = Nothing
remFirst x (y:ys) =
  if x == y then Just ys
            else case (remFirst x ys) of
                    Just zs -> Just (y:zs)
                    Nothing -> Nothing

Давайте расширим тестовые случаи:

t :: Int -> Bool
t 0 = lisEqualD [(2,3), (1,2)] [(1,2), (2,3)] == True
t 1 = lisEqualD [(2,3), (1,2)] [(1,3), (2,3)] == False
t 2 = lisEqualD [(2,3), (1,2), (1,3)] [(1,3), (2,3)] == False
t 3 = lisEqualD [(2,3)] [(1,3), (2,3)] == False
t 4 = lisEqualD [(2,3), (1,2), (2,3)] [(1,2), (2,3),(2,3)] == True
t 5 = lisEqualD [(1,1),(1,2)] [(1,1),(1,2)] == True


*Main> map t [0..5]
[True,True,True,True,True,True]

Answer 4

Мое предложение: начните с функции, которая извлекает комбинированные клавиши из двух списков:

allKeys :: Eq a => Lis a -> Lis a -> [a]

Итак, allKeys [('a',2),('b',2),('c',3)] [('b',2),('a',1),('d',3)] равно ['a','b','c','d'].Подсказка: извлеките все ключи из обоих списков, объедините их в один список, затем удалите дубликаты из этого списка (для всех этих задач есть стандартные функции).

Функция полезна как для проверки равенства, так и для вычисления сумм:

• Чтобы проверить равенство, просто убедитесь, что поиск каждой клавиши в первом списке дает тот же результат, что и поисквверх во втором списке.
• Чтобы вычислить суммы, просто соедините каждый ключ с суммой поисков в обоих исходных списках.

Следует учитывать одну вещь: список [('a',0)] идентичен []?В противном случае вы должны использовать функцию поиска, которая возвращает Maybe Int и дает Just 0 для клавиши 'a' в первом случае и Nothing во втором случае.

Дайте мне знать, если это не домашнее задание, и я могу дать вам код.

Редактировать: Код!:)

Приведенный ниже код немного упрощен по сравнению с тем, как я обычно его пишу, но ненамного.Вероятно, есть несколько библиотечных функций, с которыми вы не знакомы, включая nub (для удаления дубликатов), который импортирован из Data.List.

import Data.List(nub)

type Times = Int
type Lis a = [(a,Times)] 

count :: Eq a => Lis a -> a -> Times
count xs x = case lookup x xs of
  Nothing -> 0 -- x is not in the list
  Just n  -> n -- x is in the list associated with n

-- Extract all keys by taking the first value in each pair
keys :: Lis a -> [a]
keys xs = map fst xs 

-- Extract the union of all keys of two lists
allKeys :: Eq a => Lis a -> Lis a -> [a]
allKeys xs ys = nub (keys xs ++ keys ys)

lisEquals :: Eq a=> Lis a -> Lis a -> Bool
lisEquals xs ys = all test (allKeys xs ys) 
  where
    -- Check that a key maps to the same value in both lists
    test k = count xs k == count ys k

lisSum :: Eq a => Lis a -> Lis a -> Lis a
lisSum xs ys = map countBoth (allKeys xs ys)
  where
    -- Build a new list element from a key
    countBoth k = (k,count xs k + count ys k)