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

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开发者_JAVA百科. 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.

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.

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]]

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]]

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

And we're home!

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

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.

Sadly, using groupBy as pmr suggested won't work as it does the comparison 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 by using this altered 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 non-transitive equality predicate.

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

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

But filter's predicate has the type (a -> Bool); that won't work because it only looks at one element at a time. You need something like filter, but with the type (a -> a -> Bool) -> [a] -> [[a]]

Hoogle time. (or Hayoo, if you prefer)

Hoogle's first match for this type signature is Data.List.groupBy, which is just the function you're looking for.

Unfortunately groupBy isn't quite right, as you've discovered. The problem is that it compares each new element against the first element it was testing, so with input [1,2,3], the test function returns True when comparing 1 and 2, but False when comparing 1 and 3. However, if you look at the implementation it may be possible to modify it a bit.

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

Hmm. This uses span to divide the list, which won't work here because span only looks at one argument at a time. You could modify groupBy as hammar suggests, but you could write it in other ways too, like this version with 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)

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

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