CODEWITHSUNDEEP
haskell
Oleg
Oleg

Reputation: 1559

Group consecutive alike elements

I'm new to Haskell and here's what I want to do : enter image description here

So far only compiler errors :

groupElems :: Eq a => [a] -> [[a]]
groupElems [] = []
groupElems (x:xs) = 
    let (a,b) = span (<= x) xs
    in a : (groupElems b)

Thank you.

Error :

Could not deduce (Ord a) arising from a use of ‘<=’
from the context (Eq a)
  bound by the type signature for groupElems :: Eq a => [a] -> [[a]]

Upvotes: 0

Views: 286

Answers (4)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476534

The compiler says:

Could not deduce (Ord a) arising from a use of ‘<=’
from the context (Eq a)
  bound by the type signature for groupElems :: Eq a => [a] -> [[a]]

What the Haskell compiler aims to say is that you use <= x om your code, but the <= function is not part of the Eq typeclass: if we ask where <= originates from, we get:

Prelude> :i (<=)
class Eq a => Ord a where
  ...
  (<=) :: a -> a -> Bool
  ...
    -- Defined in ‘GHC.Classes’
infix 4 <=

So we can solve the issue by using the Ord typeclass: it means that the elements are ordered. But based on your examples this is not what you want. If we use Ord a as type constraint, like:

groupElems :: Ord a => [a] -> [[a]]
groupElems [] = []
groupElems (x:xs) = 
    let (a,b) = span (<= x) xs
    in a : (groupElems b)

A second problem is that we *call span on the xs list. xs is the tail of the list. So that means we will not take the head into account. We can alter this by using an alias @ and process the entire list xa:

groupElems :: Ord a => [a] -> [[a]]
groupElems [] = []
groupElems xa@(x:_) = 
    let (a,b) = span (<= x) xa
    in a : (groupElems b)

we will obtain:

GHci > groupElems []
[]
GHci > groupElems [1,2]
[[1],[2]]
GHci > groupElems [1,2,2,2,4]
[[1],[2,2,2],[4]]
GHci > groupElems [1,2,3,2,4]
[[1],[2],[3,2],[4]]

Note that the last test case is not correct. That is because both 3 and 2 satisfy the <= 3 predicate.

In case you want to group by equality, you should use the (==) :: Eq a => a -> a -> Bool function:

groupElems :: Eq a => [a] -> [[a]]
groupElems [] = []
groupElems xa@(x:_) = 
    let (a,b) = span (== x) xa  -- use == instead of <=
    in a : (groupElems b)

which then produces:

GHci > groupElems []
[]
GHci > groupElems [1,2]
[[1],[2]]
GHci > groupElems [1,2,2,2,4]
[[1],[2,2,2],[4]]
GHci > groupElems [1,2,3,2,4]
[[1],[2],[3],[2],[4]]

Upvotes: 8

Redu
Redu

Reputation: 26161

I think what you are looking for is Data.List.group;

Prelude> Data.List.group [1,2,2,2,4]
[[1],[2,2,2],[4]]

Upvotes: 3

Igor Drozdov
Igor Drozdov

Reputation: 15045

The compiler says that a must be an instance of Ord typeclass, because of using <=. So you can correct your code to this:

groupElems :: Ord a => [a] -> [[a]]

But if you still need to use Eq, you can use == instead of <= and the code will work.

I also noticed, that your version of code returned [1, [], [3]] on [1,2,2,3,3] example, because you passed xs instead of the whole list.

groupElems :: Eq a => [a] -> [[a]]
groupElems [] = []
groupElems all@(x:xs) =
    let (a,b) = span (== x) all
    in a : (groupElems b)

By the way, there's group function in Data.List module that does exactly what you're going to achieve

Upvotes: 3

Chad Gilbert
Chad Gilbert

Reputation: 36375

You are constraining your function so that a must be of class Eq. However, the function <= belongs to the Ord typeclass. Try changing the function annotation to this:

groupElems :: Ord a => [a] -> [[a]]

Upvotes: 2

Related Questions