Использование алгебраического типа данных для объединения списков - PullRequest
Новая
       28

Использование алгебраического типа данных для объединения списков

0 голосов
/ 27 марта 2019

Я пытаюсь понять синтаксис созданных алгебраических типов данных. Тип, который я создал, это [Int] или Empty, аналогично Maybe с Just и Nothing, за исключением того, что Just должен быть списком Int. У меня возникают проблемы с пониманием манипулирования созданным типом, когда он принимает два входа и дает вывод того же типа. 

data Example = Arg [Int]
         | Empty
    deriving Show

Я использую сопоставление с образцом и понимаю, что каждый случай должен быть рассмотрен; однако моя проблема связана с синтаксисом окончательного шаблона, где ни один не равен Empty. Я пытаюсь написать две функции: одну, которая объединяет оба списка [Int] из конструктора Example, и я хочу создать функцию, которая показывает только набор [Int], который совместно использует оба, вместо объединения.

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

combine :: Example -> Example -> Example
combine Empty Empty = Empty
combine (Arg xs) Empty = (Arg xs)
combine Empty (Arg ys) = (Arg ys)
combine (Arg xs) (Arg ys) = Arg xs ++ ys

same :: Example -> Example -> Example
same _ Empty = Empty
same Empty _ = Empty
same (Arg x : xs) (Arg y : ys)
  | x == y    = x
  | otherwise = same (Arg xs) (Arg ys)

Вывод combine должен представлять собой список [Int], содержащий все Int s из обоих списков; если один список пуст, он должен вернуть весь набор непустого списка.

Вывод same должен содержать список [Int], содержащий только числа, общие для обеих групп, без повторов; если один набор пуст, выход пуст.

Ответы [ 2 ]

1 голос
/ 27 марта 2019 
combine :: Example -> Example -> Example
combine x Empty = x
combine Empty x = x
combine (Arg xs) (Arg ys) = Arg $ union xs ys

union xs ys = nub $ xs ++ ys
nub [] = []
nub (x:xs) = if x `elem` xs then nub xs else x : nub xs

same :: Example -> Example -> Example
same _ Empty = Empty
same Empty _ = Empty
same (Arg xs) (Arg ys) = Arg $ intersect xs ys

intersect _ [] = [] -- unnecessary but practical!
intersect [] _ = []
intersect (x:xs) ys = if x `elem` ys then x : intersect xs ys else intersect xs ys

Как комментирует Робин, у вас есть пара разных проблем. Во-первых, вам нужно сопоставить все случаи, во-вторых, вам нужно снова обернуть результаты в ваш тип данных, в-третьих, вам нужно удалить дубликаты в объединении, в-четвертых, ваша операция «установить пересечение» будет работать только с некоторыми очень сильными предположениями о структура входных списков. union, intersect (также доступно в Data.List) достаточно хороши для демонстрационных целей без вызова, например. Data.IntSet.toList . Data.IntSet.fromList хотя это было бы быстрее. Ваша версия (если ее немного исправить) выведет элементы, которые находятся в одной и той же позиции в обоих списках.

Общие учебники по функторам часто начинаются с вида Maybe, что может помочь вам понять это, поскольку Example изоморфно Maybe [Int].

Примером, где вы можете использовать деконструктор Arg (x : xs), может быть функция, которая берет меньший элемент в каждом индексе из двух списков. Не могли бы вы попробовать написать это самостоятельно, т.е. без использования zip?

РЕДАКТИРОВАТЬ: серьезные изменения и исправления

0 голосов
/ 27 марта 2019

Используя концепцию подъема , я пришел с этим решением: 

import Data.List (nub)

data Example = Arg [Int]
         | Empty
    deriving Show

combine :: Example -> Example -> Example
combine Empty Empty = Empty
combine x Empty = x
combine Empty x = x
combine (Arg xs) (Arg ys) = Arg $ nub $ xs ++ ys

same :: Example -> Example -> Example
same arg1 arg2 = lift nub $ same' arg1 arg2
    where
        same' _ Empty = Empty
        same' Empty _ = Empty
        same' (Arg []) y = Arg []
        same' (Arg (x : xs)) (Arg (ys))
            | x `elem` ys = lift (x : ) $ same' (Arg xs) (Arg ys)
            | otherwise  = same' (Arg xs) (Arg ys)

lift :: ([Int] -> [Int]) -> Example -> Example
lift _ Empty = Empty
lift f (Arg x) = Arg (f x)

Что lift делает, чтобы применить функцию к «содержимому» Arg,Если у вас есть выражение same (Arg [1, 2, 4, 3]) (Arg [3,1,4]), рекурсия превратит его в: 

lift nub $ lift (1 : ) $ lift (4 : ) $ lift (3 : ) $ Arg []

, который оценивает как: 

lift nub $ lift (1 : ) $ lift (4 : ) $ Arg (3:[])
lift nub $ lift (1 : ) $ Arg (4:3:[])
lift nub $ Arg (1:4:3:[])
Arg (nub $ 1:4:3:[])

, а затем: 

Arg [1,4,3]
...