Haskell:列表创建的评估列表元素 [英] Haskell: List Created Evaluating List Elements

问题描述

我正在尝试编写一个列表函数，该函数采用一个简单的列表并反馈一个列表列表，后者的所有元素都与前一个元素具有相同的关系.

I am trying to write a list function that takes a simple list and feeds back a list of lists, all of the latter's elements having the same relationship with the previous one.

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

In more concrete terms, the function should be doing this:

1. 列出清单； let 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.

1. take a list; let xs = [1,2,3,4,5,6,8,9,10]
2. look at two elements from the head and, if the second one equals to the first one plus one (i.e., xs!!0 = xs!!1 - 1), create a list-within-a-list out of them.
3. The list takes elements while the last of them have the same relationship with the element, newly fed from the main list. When there is a hiatus, the sublist closes but the function should make a new sublist, based on the same condition all the way through.
4. So, the final outcome should be, [[1,2,3,4,5,6],[8,9,10]] The absent 7 divides the main list into two sublists. Both of them are arithmetic progressions with the common difference being 1.

在阅读了《 学到一个伟大的Haskell》 到第7章之后，我以为我真的有个好主意，尝试失败了.非常欢迎您的帮助！

After reading Learn You a Haskell for Great Good till chapter 7, I thought I really had a great idea and tried and ingloriously failed. Help is most welcome, please!

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

推荐答案

这是我针对此问题的思考过程...我们希望将列表分成链". (因此为列表列表)，并进行了测试以查看是否有两个元素链接起来.

Here's my thought process for this problem... We want to chop a list into ‘chains’ (so a list of lists), given a test to see if two elements link up.

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

我不记得库中有任何这样的东西，所以我决定自己动手.我想确定一种合适的递归策略来处理列表.

I don't remember any such thing in the library, so I decide to roll my own. I want to identify a suitable recursion strategy for processing the list.

我可以考虑一下元素吗?否:我很快排除了map和foldMap，因为在此问题中元素似乎并没有彼此独立对待.

Can I just think about elements? No: I quickly rule out map and foldMap, as elements don't seem to be treated independently of each other in this problem.

接下来，我问输出类型是否具有列表代数?".用这种方式表达，这听起来似乎不是一件显而易见的事情，但它可以解决以下明智的问题.有零"吗?和缺点"建立输出(链列表)而不是输入(列表)的操作?如果是这样，我可以使用foldr像这样将输入nil-cons转换为输出nil-and-cons.

Next, I ask ‘Does the output type have a list algebra?’. That may not sound like an obvious thing to think, phrased that way, but it unpacks to the following sensible question. Are there ‘nil’ and ‘cons’ operations that build up outputs (lists of chains), instead of inputs (lists)? If so, I can use foldr to transform input nil-and-cons into output nil-and-cons, like this.

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

很明显，chNil必须是什么，因为我正在对原始元素进行分组.空进去吗?清空！

It's clear what chNil has to be, as I'm grouping the original elements. Empty in? Empty out!

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

我可以写chCons吗?假设我得到一个链列表:如何添加一个新元素?好吧，如果有我可以链接的前链，那么我应该增加该链，否则我应该开始一个新的链.因此，在非空链列表的开头，我对非空链有一个特殊的情况，默认情况下为cons singleton.

Can I write chCons? Suppose I get a list of chains: how do I add a new element? Well, if there's a front chain I can link to then I should grow that chain, otherwise I should start a new chain. So I have a special case for a nonempty chain at the start of a nonempty list of chains, and a default to cons a singleton.

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的要点是捕获此查找代数".模式，就可以解决这个问题.

A bunch of operators has an algebra for a given type if you can implement those operators for values of that type. The constructors of a datatype are just one algebra, one implementation of a bunch of operators, building values in that very datatype. A good way to compute with inputs from a datatype is to implement its algebra for your desired type of outputs. The point of foldr is to capture this ‘find the algebra’ pattern, and it's right on the money for this problem.

这篇关于Haskell:列表创建的评估列表元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！