列表到递归调用中的列表。

Question

这是我的代码：

findY mnozP a = 
    if null(Set.toList $ mnozP)==False
        then (
            if (((null(intersect ( Set.toList $ head $ Set.toList $ mnozP) (a))==False) && (null(( Set.toList $ head $ Set.toList $ mnozP) \\ (a))==False)))
                then (((intersect ( Set.toList $ head $ Set.toList $ mnozP) (a)) ++ (( Set.toList $ head $ Set.toList $ mnozP) \\ (a))) ++ findY ( Set.fromList $ tail $ Set.toList $ mnozP) (a))
                else findY ( Set.fromList $ tail $ Set.toList $ mnozP) (a)
            )
        else []
findY _ a = []
findY _ _ = []

此函数检查list mnozP是否为空，如果不是，则接受第一项，并检查其与list a的交集是否为空and --差异不是空的。在条件为真的情况下，实现这两个操作，并将其递归地调用为list b的尾部。我其实有两个问题：

1. 让我们假设以下列表：a = ["3","4"]和mnozP = [["1","6"],["2","4","3","5"]]。输出为["3","4","2","5"]。是否有任何函数可以根据每次迭代将此列表拆分为列表？预期的输出应该类似于[["3","4"],["2","5"]]。
2. 在编译GHCi时，说明如下： 警告:模式匹配(Es)在“findY”：findY_a=.findY _=. 我不知道我的模式有什么问题。我试图涵盖所有可能发生的情况。有什么不对吗？

编辑：(简短摘要：)函数findY应该返回列表列表。每个内部列表都与一个具体的递归迭代相关(在条件为真的情况下)。

Answer 1

您要查找的函数是list构造函数。在你的归纳案例中，你

(((intersect ( Set.toList $ head $ Set.toList $ mnozP) (a)) ++ (( Set.toList $ head $ Set.toList $ mnozP) \\ (a))) ++ findY ( Set.fromList $ tail $ Set.toList $ mnozP) (a))

这才是

as ++ bs ++ cs

其中cs是递归调用的结果。如果findY返回列表列表，则整个表达式也必须返回。根据归纳假设，cs是一个列表列表。换句话说，exp ++ cs中左边的表达式(即as ++ bs)也必须是列表列表。但事实并非如此！intersect和\\返回平面列表，您可以将它们连接在一起，从而获得一个新的平面列表。

要解决这个问题，只需将左表达式封装在列表中即可。

[as ++ bs] ++ cs

或者使用列表构造函数。

(as ++ bs) : cs

如果你能从中得到什么，那就是，如果代码是以一种更惯用的方式编写的，你可以自己发现这一点。我将试着向您介绍我如何“解压”您的代码。

首先，我添加了一个与您描述相匹配的类型签名。

findY :: Eq a => [[a]] -> [a] -> [[a]]

有趣的是，仅这一变化就会指出归纳案例中的表述是不正确的。

然后，我去掉了Set <-> []转换。您可以要求您的输入设置，或只是简单的列表，并确保没有重复。我采用后一种方法：

findY :: Eq a => [[a]] -> [a] -> [[a]]
findY mnozP a = 
if null(mnozP)==False
    then (
        if (((null(intersect (head mnozP) (a))==False) && (null(( head mnozP) \\ (a))==False)))
            then (((intersect ( head mnozP) (a)) ++ (( head mnozP) \\ (a))) ++ findY ( tail mnozP) (a))
            else findY ( tail mnozP) (a)
        )
    else []
findY _ a = []
findY _ _ = []

已经越来越清楚了。你也可以摆脱大量的()。在Haskell中，函数应用只是空格字符。因此，您不必像在许多语言中那样编写f(x)，而是编写f x并使用括号来消除表达式的歧义：

findY :: Eq a => [[a]] -> [a] -> [[a]]
findY mnozP a = 
if (null mnozP) == False
    then
        if (null (intersect (head mnozP) a) == False) && (null (head mnozP \\ a) == False)
            then (intersect (head mnozP) a) ++ (head mnozP \\ a) ++ findY (tail mnozP) a
            else findY (tail mnozP) a
    else []
findY _ a = []
findY _ _ = []

接下来，注意head和tail的多次重复。您可以使用let表达式将这些变量绑定到变量，但是有更好的方法。Haskell允许您对参数进行模式匹配，以便根据输入选择应该计算哪个分支。在这里，我们只需要知道列表是否有头和尾，这恰好是匹配非空列表的模式：

findY :: Eq a => [[a]] -> [a] -> [[a]]
findY (xs : xss) a = 
    if (null (intersect xs a) == False) && (null (xs \\ a) == False)
        then (intersect xs a) ++ (xs \\ a) ++ findY xss a
        else findY xss a
findY _ _ = []

看看这样做是如何让我摆脱了第一个if语句的吗？(我还删除了额外的模式匹配)。仍然有一些冗余，让我们去掉它：

findY :: Eq a => [[a]] -> [a] -> [[a]]
findY (xs : xss) a =
  let as = intersect xs a
      bs = xs \\ a
  in
    if (null as == False) && (null bs == False)
        then as ++ bs ++ findY xss a
        else findY xss a
findY _ _ = []

在这一点上，这个问题是突出的。

findY :: Eq a => [[a]] -> [a] -> [[a]]
findY (xs : xss) a =
  let as = intersect xs a
      bs = xs \\ a
  in
    if (null as == False) && (null bs == False)
        then (as ++ bs) : findY xss a
        else findY xss a
findY _ _ = []

现在这是一个风格问题，但我个人认为使用模式匹配比大多数时候使用if语句更优雅。不过，这里的情况并非如此：

findY :: Eq a => [[a]] -> [a] -> [[a]]
findY (xs : xss) a =
  let as = intersect xs a
      bs = xs \\ a
  in case (as, bs) of
    ((_ : _), (_ : _)) -> (as ++ bs) : findY xss a
    _                  -> findY xss a
findY _ _ = []

但是在Haskell 2010中，您可以使用模式保护，这是一个更强大的模式匹配版本。它使您的代码更加清晰：

findY :: Eq a => [[a]] -> [a] -> [[a]]
findY (xs : xss) a 
  | as@(_ : _) <- intersect xs a
  , bs@(_ : _) <- xs \\ a = (as ++ bs) : findY xss a
  | otherwise             = findY xss a
findY _ _ = []

最后，程序的形状是典型的结构递归。这通常是您将使用foldr的目的。

findY :: Eq a => [a] -> [[a]] -> [[a]]
findY a = foldr build []
  where 
    build xs yss
      | as@(_ : _) <- intersect xs a
      , bs@(_ : _) <- xs \\ a = (as ++ bs) : yss
      | otherwise             = yss