如何通过删除特定的分隔(Haskell)将列表拆分为列表

Question

我是Haskell的新手,我有一个问题.我需要编写一个函数,将列表拆分为列表中的"分离".

Answer 1

我将尝试帮助您了解如何通过递归开发在列表上工作的函数.学习如何以"低级"方式首先完成它是有帮助的,这样您就可以更好地理解在实际代码中更常见的"高级"方式发生的事情.

首先,您必须考虑要使用的数据类型的性质.该列表在某种意义上是Haskell中递归定义类型的规范示例:列表是空列表,[]或者是列表元素a与列表通过组合a : list.这是唯一的两种可能性.我们将空列表称为基本情况,因为它是在其定义中不引用自身的那个.如果没有基本情况,递归将永远不会"触底"并将无限期地继续!

列表定义中有两种情况这一事实意味着您必须在使用列表的函数定义中考虑两种情况.在Haskell中考虑多个案例的规范方法是模式匹配.Haskell语法提供了许多方法来进行模式匹配,但我case现在只使用基本表达式:

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

这是列表必须考虑的两种情况.第一个匹配文字空列表构造函数; 第二匹配元素添加的构造:,并且还结合两个变量,x并且xs',在列表中的第一个元素和包含的元件的其余部分的子列表.

如果你的函数传递了一个与第一个案例匹配的列表,那么你知道初始列表是空的,或者你已经完成了列表中的最后一个元素的递归.无论哪种方式,都没有更多的清单要处理; 你要么完成了(如果你的调用是尾递归的),要么你需要将你的答案结构的基本元素传递给调用它的函数(通过返回它).如果您的答案是列表,则基本元素通常将再次为空列表[].

如果你的函数传递一个第二情况下匹配列表,那么你知道它是通过一个非空列表,而且你有一对夫妇必然有用值的新变量.基于这些变量,您需要决定两件事:

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') -> ...

希望这些提示可以帮助您在问题上取得一些进展!