3

我是 Haskell 的新手，我有一个问题。我需要编写一个函数，在出现“分隔”的任何地方将列表拆分为列表列表。

4

3 回答 3

7

我将尝试帮助您了解如何通过递归开发在列表上工作的函数。首先学习如何以“低级”方式进行操作会很有帮助，这样您就可以更好地理解在实际代码中更常见的“高级”方式中发生的事情。

首先，您必须考虑要使用的数据类型的性质。列表在某种意义上是 Haskell 中递归定义类型的典型示例：列表要么是空列表，[]要么是某个列表元素a与列表通过a : list. 这是仅有的两种可能性。我们称空列表为基本情况，因为它在定义中不引用自身。如果没有基本情况，递归将永远不会“触底”并且会无限期地继续下去！

列表定义中有两种情况意味着您必须在使用列表的函数的定义中考虑两种情况。在 Haskell 中考虑多种情​​况的规范方法是模式匹配。Haskell 语法提供了许多进行模式匹配的方法，但我case现在只使用基本表达式：

case xs of
  []    ->  ...
  x:xs' ->  ...

这是列表中必须考虑的两种情况。第一个匹配文字空列表构造函数；第二个匹配添加元素的构造函数，并将两个变量和,:绑定到列表中的第一个元素和包含其余元素的子列表。xxs'

如果您的函数传递了一个与第一种情况匹配的列表，那么您就知道初始列表是空的，或者您已经完成了对列表的递归，直到它的最后一个元素。无论哪种方式，都没有要处理的列表；您要么完成（如果您的调用是尾递归的），要么您需要将答案构造的基本元素传递回调用它的函数（通过返回它）。如果您的答案是一个列表，那么基本元素通常又是一个空列表[]。

如果您的函数传递了一个与第二种情况匹配的列表，那么您就知道它传递了一个非空列表，而且您还有一些绑定到有用值的新变量。基于这些变量，您需要决定两件事：

  1. 假设我在列表的其余部分上执行它得到正确答案，我该如何在那个元素上执行我的算法的一步？
  2. 我如何将这一步的结果与在列表的其余部分上执行的结果结合起来？

一旦你想出了这些问题的答案，你就需要构建一个组合它们的表达式；获得列表其余部分的答案只需对列表的其余部分调用递归调用，然后您需要执行第一个元素和组合的步骤。

这是一个查找列表长度的简单示例

listLength :: [a] -> Int
listLength as =
  case as of
    []    -> 0                  -- The empty list has a length of 0
    a:as' -> 1 + listlength as' -- If not empty, the length is one more than the
                                -- length of the rest of the list

这是另一个从列表中删除匹配元素的示例

listFilter :: Int -> [Int] -> Int
listFilter x ns =
  case ns of
    []    -> []                            -- base element to build the answer on
    n:ns' -> if n == x
               then listFilter x ns'       -- don't include n in the result list
               else n : (listFilter x ns') -- include n in the result list

现在，您提出的问题有点困难，因为它涉及辅助“列表匹配”递归，以识别列表上基本递归中的分隔符。有时向递归函数添加额外的参数会很有帮助，以便保存有关您在问题中所处位置的额外信息。也可以通过将它们放在一个元组中来同时对两个参数进行模式匹配：

case (xs, ys) of
  ([]   , []   ) -> ...
  (x:xs', []   ) -> ...
  ([]   , y:ys') -> ...
  (x:xs', y:ys') -> ...

希望这些提示能帮助您在问题上取得一些进展！

于 2013-08-25T22:43:08.150 回答
3

让我们看看是否可以通过明显的方式减少问题。

假设调用 splitList 时用 xs 进行拆分，用 ys 作为分隔符。如果 xs 为空，则问题最小，那么该问题的答案是什么？这里有正确的答案很重要，因为归纳解决方案取决于这个决定。但我们可以稍后做出这个决定。

好的，所以要简化问题，列表 xs 不为空。所以，它至少有一个头元素 h 和较小的问题 t，列表的尾部：你可以匹配 xs@(h:t)。如何获得较小问题的解决方案？好吧， splitList 可以通过函数的定义来解决这个问题。所以现在的诀窍是弄清楚如何为更大的问题 (h:t) 构建解决方案，当我们知道较小问题的解决方案 zs=splitList t ys 时。这里我们知道 zs 是列表的列表，[[a]]，并且因为 t 可能是最小的问题，zs 很可能是最小问题的解决方案。所以，无论你用 zs 做什么，即使是最小问题的解决方案，它也必须是有效的。

  splitList [] ys = ... -- some constant is the solution to the smallest problem
  splitList xs@(h:t) ys = let zs = splitList t ys
                          in ... -- build a solution to (h:t) from solution to t
于 2013-08-26T08:32:49.373 回答
1

我不知道如何测试它。有人告诉我如何将函数写入 .hs 文件并使用 winGHCi 运行此函数吗？

WinGHCi 自动与 .hs 文件关联，因此只需双击该文件，ghci 就会启动。使用您喜欢的编辑器对文件进行一些更改后，您可以编写使用:rghci 中的命令重新加载文件。

要在修复拼写错误、类型错误并确保正确缩进后测试程序，请尝试使用不同的输入调用您定义的函数（或使用 QuickCheck）。注意Maybe定义为Just x或Nothing。您可以使用fromMaybe提取x（并为 Nothing 情况提供默认值）。

还要尝试确保模式匹配是详尽的。

于 2013-08-26T21:53:07.870 回答