Using Algebraic Data Type to combine lists

Question

I'm trying to understand the syntax of created algebraic data types. The type I've created is either an [Int] or Empty, similar to Maybe with Just and Nothing except the Just has to be a list of Int. I'm having trouble understanding manipulating the created type when it accepts two inputs and gives an output of the same type.

data Example = Arg [Int]
         | Empty
    deriving Show

I use pattern matching and understand that every case must be addressed; however, my issue comes from the syntax of the final pattern where neither is Empty. I'm trying to write two functions: one that combines both [Int] lists from the Example constructor, and I want to create a function that only shows a set of [Int] that both share, instead of combining.

The first issue is combining two sets. I can do it in a normal function but somewhere, using the Example data type, the syntax is off and I'm unfamiliar with it. The biggest issue in the second is the same: I understand recursion but I don't understand the syntax of recursion in a created data type. I was also thinking of using a where statement in the second function but if I can't get the syntax of basic recursion right then I doubt it'd be successful.

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)

The output of combine should be an [Int] list containing all Ints from both lists; if one list is empty, it should return the entire set of the non-empty list.

The output of same should contain an [Int] list containing only the numbers shared by both groups, with no repeats; if one set is empty, the output is empty.

Answer 1

Using the concept of lifting, I came ou with this solution:

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)

What lift do is to apply a function to the "content" of Arg. If you have the expression same (Arg [1, 2, 4, 3]) (Arg [3,1,4]) the recursion will turn it into:

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

wich evaluates like:

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:[])

then finally:

Arg [1,4,3]