2

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. 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
Improve this question
1
  • note: ghci> let xs = [1,2,3,4,8,5,10] ghci> [x | x <- myGroupBy (\x y -> x*2==y) xs, length x > 1] [[1,2],[4,8],[5,10]] never mind. Commented Aug 6, 2011 at 13:31

4 Answers 4

Reset to default
5

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Hmm, I got a different result set: ghci> chains (\ x y -> x + 1 == y) [1,2,3,4,5,6,8,9,10] [[1],[2],[3],[4],[5],[6],[8],[9],[10]] Just in case it's due to an outdated version, mine is GHCi, version 6.8.2.
my bad: I got the x and the y backwards, copying the code across; editing now.
Now the function works fine. I am still struggling with it because the left element of : seems to be String in three places ([y]:xss etc.). Wasn't cons to be used as in a:[a] whether it is used for pattern matching or for constructing a list?
Ah, but here, we're working with lists of lists of things. So, in (y : xs) : xss, the inner : is consing an x to a [x] to make a [x], then the outer : is consing that very [x] to a [[x]] to make a [[x]]. The two :s are being used in that a:[a] pattern, but for different instance of a. Similarly, [y] : xss is consing a thing to a list of things (where the things are themselves lists). It's a good exercise to push a type like [[x]] into a pattern like (xs@(x : _) : xss), according to the type of :, and figure out the types of x, xs and xss.
Something clicked just when I realised that the Haskell list is a specialised application of foldr, and that's what I need when I define a new set of rules for creating [[1,2,3,4,5,6],[8,9,10]], which is another kind of list. THANK YOU!
4

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.

Improve this answer

6 Comments

I remember that thread; I thought this change had already been made in base for H2010. It should probably go back to libraries@.
Thanks, hammar. Works just fine! [Still don't know how to RETURN in the comment box] The type inference is: groupByMe :: (a -> a -> Bool) -> [a] -> [[a]] So, this is a function that checks a list on a binary predicate to yield a list-of-lists. I'll start reading your link too. [Still don't know if there is a private message system here]. Thanks dave for fixing the format of my very first post above.
What are | and x0? Besides them, your code seems to me the simplest one, so I'll tackle this first. Thanks.
| starts a guard, meaning that the pattern on the left will only match if the guard on the right evaluates to True. x0 is just a variable name like any other.
So, groupByAux x0 (x:xs) | rel x0 x = (x:ys, zs) means this? "First of the two patterns of groupByAux returns a binary tuple if predicate 'rel x0 x' returns True." Sometimes a function is a function but other times it is the output....
|
3

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)
Improve this answer

Comments

0

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

Improve this answer

1 Comment

Hey, I realised that just a minutes after I posted. Then again, ghci> groupBy (\x y -> x + 1 == y) xs [[1,2],[3,4],[5,6],[8,9],[10]]

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.