使用代数数据类型组合列表

Question

我试图理解创建的代数数据类型的语法。我创造的类型是[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]列表，其中包含来自两个列表的所有Ints;如果一个列表为空，则应返回非空列表的整个集合。

same的输出应该包含一个[Int]列表，其中只包含两个组共享的数字，没有重复;如果一个集合为空，则输出为空。

Answer 1

使用lifting的概念，我推出了这个解决方案：

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]

Answer 2

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）足以用于演示目的而无需调用eg。 Data.IntSet.toList . Data.IntSet.fromList虽然那会更快。您的版本（如果略微更正）将输出出现在两个列表中相同位置的元素。

关于仿函数的常见教程通常从Maybe类开始，这可能对你有所帮助，因为Example与Maybe [Int]是同构的。

您可能希望使用Arg (x : xs)解构函数的示例将是一个函数，它从两个列表中获取每个索引处的较小元素。你能尝试递归地写这个吗，即。没有使用zip？

编辑：重大变化和更正