Haskell: list created. Rating list items.

Question

I am trying to write a list function that takes a simple list and returns a list of lists, with all the last elements having the same relationship with the previous one.

In more specific terms, a function should do this:

• take a list; let xs = [1,2,3,4,5,6,8,9,10]
• Look at the two elements from the head, and if the second is equal to the first plus one (i.e. xs!!0 = xs!!1 - 1 ), create a list-in-list from them.
• The list accepts items, while the last of them have the same relationship with the item recently loaded from the main list. When a break occurs, the sublist closes, but the function should create a new sublist based on the same condition throughout.
• So, the end result should be, [[1,2,3,4,5,6],[8,9,10]] The absence of 7 divides the main list into two sub-lists. Both of them are arithmetic progressions with a total difference of 1.

After reading Learn Haskell for Great Good before chapter seven, I thought I had a really great idea, and I tried and unceremoniously failed. Help is welcome, please!

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

Answer 1

Here is my thought process for this problem ... We want to slice the list into & zquo; chain & rsquo; (so a list of lists), given the test, to see if the two elements are connected.

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

I don’t remember anything like that in the library, so I decided to quit my own. I want to determine the appropriate recursion strategy to handle the list.

Can I just think about the elements? Not. I quickly rule out map and foldMap , since the elements do not seem to be considered independently of each other in this issue.

Next, I ask & lsquo; Does output type have list algebra? & rsquo ;. This may not seem like an obvious thought formulated in this way, but it breaks down into the next reasonable question. Does nil & rsquo; and & lsquo; cons & rsquo; operations that form outputs (lists of circuits) instead of inputs (lists)? If so, I can use foldr to convert input nil-and-cons to output nil-and-cons, like this.

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

Clearly, there should be chNil as I group the source elements. Empty? It's empty!

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

Can I write chCons ? Suppose I get a list of nets: how to add a new element? Well, if there is a cross chain to which I can connect, then I have to develop this chain, otherwise I have to start a new chain. Therefore, I have a special case for a non-empty circuit at the beginning of a non-empty circuit list, and by default - minus one.

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

And we are at home!

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

The letter of operators has algebra for a given type, if you can implement these operators for values ​​of this type. Constructors of a data type are just one algebra, one implementation of many operators, the construction of values ​​in this very data type. A good way to compute with inputs from a data type is to implement your algebra for the desired type of outputs. The point of foldr is to fix this: find the algebra & rsquo; template, and it’s right for the money for this problem.

Answer 2

Unfortunately, using groupBy for pmr will not work, as it compares with the first element of each group, rather than comparing adjacent elements. This is because groupBy assumes that the equality predicate is transitive. You can get the desired behavior using this modified version:

 groupBy rel [] = [] groupBy rel (x:xs) = (x:ys) : groupBy rel zs where (ys,zs) = groupByAux x xs groupByAux x0 (x:xs) | rel x0 x = (x:ys, zs) where (ys,zs) = groupByAux x xs groupByAux y xs = ([], xs) 

See also: Data.List.groupBy with a non-transitive equality predicate .

Answer 3

Ok, put your comparison function in GHCi and see what it gives you for a type:

 Prelude> :t (\xy -> x + 1 == y) (\xy -> x + 1 == y) :: Num a => a -> a -> Bool 

But the filter predicate is of type (a -> Bool) ; this will not work because it only looks at one element at a time. You need something like a filter, but with type (a -> a -> Bool) -> [a] -> [[a]]

Hoogle time. (or Hayoo if you want)

The first Google match for this signature is of type Data.List.groupBy , which is only the function you are looking for.

Unfortunately, groupBy not quite right as you discovered. The problem is that it compares each new element with the first element that it tested, so when you enter [1,2,3] test function returns True when comparing 1 and 2, but False when comparing 1 and 3. However, if you look implementation, perhaps it will be possible to change a little.

 groupBy :: (a -> a -> Bool) -> [a] -> [[a]] groupBy _ [] = [] groupBy eq (x:xs) = (x:ys) : groupBy eq zs where (ys,zs) = span (eq x) xs 

Hm. This uses a span to split the list, which will not work here, because the span only considers one argument at a time. You can change groupBy as the hammar suggests, but you could write it in other ways, for example, this version using foldr :

  myGroupBy _ [] = [] myGroupBy eq (x:xs) = (\(_,t1,t2) -> init $ t1:t2) $ foldr (\el (el2,t1,t2) -> if eq el el2 then (el,el:t1,t2) else (el,[el],t1:t2)) (x,[],[]) (x:xs) 

Answer 4

For your error: filter type (a -> Bool) -> [a] -> [a] . Your lambda takes two arguments, filter expects a unary function.

The function you want (as far as I can see) groupBy :: (a -> a -> Bool) -> [a] -> [[a]] .