list - Haskell:创建列表评估列表元素

Question

我正在尝试编写一个列表函数，它接受一个简单列表并反馈一个列表列表，后者的所有元素与前一个元素具有相同的关系。

更具体地说，函数应该这样做:

1. 列一个 list ； 让 xs = [1,2,3,4,5,6,8,9,10]
2. 查看头部的两个元素，如果第二个元素等于第一个元素加一(即，xs!!0 = xs!!1 - 1)，创建一个列表-在他们的列表中。
3. 列表接受元素，而最后一个元素与元素具有相同的关系，是从主列表新提供的。当出现中断时，子列表会关闭，但函数应该根据相同的条件创建一个新的子列表。
4. 因此，最终结果应该是，[[1,2,3,4,5,6],[8,9,10]] 缺席的 7 将主列表分为两个子列表。两者都是等差级数，公差为1。

读完 Learn You a Haskell for Great Good 直到第 7 章，我认为我真的有一个好主意并且尝试过并且可耻地失败了。非常欢迎您提供帮助!

ghci> filter (\x y -> x + 1 == y) xs

"<"interactive">":1:8:
    The lambda expression `\ x y -> x + 1 == y' has two arguments, 
    but its type `a -> Bool' has only one 
    In the first argument of `filter', namely `(\ x y -> x + 1 == y)' 
    In the expression: filter (\ x y -> x + 1 == y) xs 
    In the definition of `it': it = filter (\ x y -> x + 1 == y) xs

Answer 1

这是我对这个问题的思考过程......我们想将一个列表分成“链”(因此列表的列表)，并进行测试以查看两个元素是否链接。

chains :: (x -> x -> Bool) -> [x] -> [[x]]

我不记得图书馆里有这样的东西，所以我决定自己动手。我想确定一个合适的递归策略来处理列表。

我可以只考虑元素吗？否:我很快排除了 map 和 foldMap，因为在这个问题中，元素似乎没有被相互独立对待。

接下来，我会问“输出类型是否有列表代数？”。以这种方式措辞，这听起来不像是一件显而易见的事情，但它解开了以下一个明智的问题。是否存在构建输出(链列表)而不是输入(列表)的“nil”和“cons”操作？如果是这样，我可以使用 foldr 将输入 nil-and-cons 转换为输出 nil-and-cons，就像这样。

chains :: (x -> x -> Bool) -> [x] -> [[x]]
chains link = foldr chCons chNil where
  -- chNil :: [[x]]
  -- chCons :: x -> [[x]] -> [[x]]

很清楚 chNil 必须是什么，因为我正在对原始元素进行分组。空在？清空!

chains :: (x -> x -> Bool) -> [x] -> [[x]]
chains link = foldr chCons [] where
  -- chCons :: x -> [[x]] -> [[x]]

我可以写chCons吗？假设我得到一个链表:如何添加新元素？好吧，如果有一个我可以链接到的前链，那么我应该增加那个链，否则我应该开始一个新链。所以我在非空链列表的开头有一个非空链的特殊情况，并且默认为 cons 单例。

chains :: (x -> x -> Bool) -> [x] -> [[x]]
chains link = foldr chCons [] where
  chCons y (xs@(x : _) : xss) | link y x  = (y : xs) : xss
  chCons y xss                            = [y] : xss

我们到家了!

> chains (\ x y -> x + 1 == y) [1,2,3,4,5,6,8,9,10]
[[1,2,3,4,5,6],[8,9,10]]

如果您可以为该类型的值实现这些运算符，则一堆运算符对给定类型具有代数。数据类型的构造函数只是一个代数，是一堆运算符的一个实现，在该数据类型中构建值。使用数据类型的输入进行计算的一种好方法是为所需的输出类型实现其代数。 foldr 的目的是捕捉这个“找到代数”模式，而且它对这个问题来说是正确的。