Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

[Haskell-cafe] groupBy huh?

50 views
Skip to first unread message

Jacek Generowicz

unread,
Mar 3, 2011, 7:23:43 PM3/3/11
to Haskell Cafe
Hi Cafe,

It seems that I don't understand what groupBy does.

I expect it to group together elements as long as adjacent ones
satisfy the predicate, so I would expect ALL four of the following to
give one group of 3 and a group of 1.

Prelude> :m + Data.List
Prelude Data.List> groupBy (<) "abcb"
["abcb"]
Prelude Data.List> groupBy (<) "abca"
["abc","a"]
Prelude Data.List> groupBy (<) [1,2,3,2]
[[1,2,3,2]]
Prelude Data.List> groupBy (<) [1,2,3,1]
[[1,2,3],[1]]

What am I missing?

Thanks.


_______________________________________________
Haskell-Cafe mailing list
Haskel...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Marc Weber

unread,
Mar 3, 2011, 7:45:00 PM3/3/11
to haskell-cafe
Excerpts from Jacek Generowicz's message of Fri Mar 04 00:18:07 +0000 2011:

> Prelude Data.List> groupBy (<) [1,2,3,2]
> [[1,2,3,2]]
This is wired. However if you think about the algorithm always using the
first element of a list and comparing it against the next elements you
get

1 < 2 ok, same group
1 < 3 dito
1 < 2 dito
Thus you get [[1,2,3,2]]

Marc Weber

Daniel Fischer

unread,
Mar 3, 2011, 7:52:11 PM3/3/11
to haskel...@haskell.org
On Friday 04 March 2011 01:18:07, Jacek Generowicz wrote:
> Hi Cafe,
>
> It seems that I don't understand what groupBy does.
>
> I expect it to group together elements as long as adjacent ones
> satisfy the predicate, so I would expect ALL four of the following to
> give one group of 3 and a group of 1.
>
> Prelude> :m + Data.List
> Prelude Data.List> groupBy (<) "abcb"
> ["abcb"]
> Prelude Data.List> groupBy (<) "abca"
> ["abc","a"]
> Prelude Data.List> groupBy (<) [1,2,3,2]
> [[1,2,3,2]]
> Prelude Data.List> groupBy (<) [1,2,3,1]
> [[1,2,3],[1]]
>
> What am I missing?
>

That groupBy expects an equivalence relation (iirc, that was documented
some time, seems to be gone, there's only a hint left at the docs for group
"equality test"). It tests subsequent elements against the first of the
group, not adjacent elements.

Jacek Generowicz

unread,
Mar 3, 2011, 8:17:13 PM3/3/11
to Daniel Fischer, Marc Weber, haskel...@haskell.org
On 2011 Mar 4, at 01:39, Marc Weber wrote:

> Excerpts from Jacek Generowicz's message of Fri Mar 04 00:18:07
> +0000 2011:

>> Prelude Data.List> groupBy (<) [1,2,3,2]
>> [[1,2,3,2]]

> This is wired. However if you think about the algorithm always using
> the
> first element of a list and comparing it against the next elements you
> get
>
> 1 < 2 ok, same group
> 1 < 3 dito
> 1 < 2 dito
> Thus you get [[1,2,3,2]]


OK, that works, but it seems like a strange choice ...


On 2011 Mar 4, at 01:47, Daniel Fischer wrote:

> On Friday 04 March 2011 01:18:07, Jacek Generowicz wrote:
>>
>> What am I missing?
>>
>
> That groupBy expects an equivalence relation

.. Bingo! Now it makes sense.

> (iirc, that was documented some time, seems to be gone, there's only
> a hint left at the docs for group
> "equality test").

Hrrrrmph. In my opinion, explicitly including the words "equivalence
relation" would immensely improve the documentation.


Thank you for you clarifications, gentlemen.

Brandon S Allbery KF8NH

unread,
Mar 3, 2011, 8:19:31 PM3/3/11
to haskel...@haskell.org
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 3/3/11 20:09 , Jacek Generowicz wrote:
>> 1 < 2 ok, same group
>> 1 < 3 dito
>> 1 < 2 dito
>> Thus you get [[1,2,3,2]]
>
> OK, that works, but it seems like a strange choice ...

Stability is often valued in functions like this: the order of elements is
not altered.

- --
brandon s. allbery [linux,solaris,freebsd,perl] allb...@gmail.com
system administrator [openafs,heimdal,too many hats] kf8nh
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (Darwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk1wPPIACgkQIn7hlCsL25WF3ACfZrwM2OxutJZgadhaSCcpjoEv
Bg4AnA+V/H3tfCovwwnw8qrlaw5I92C4
=WJev
-----END PGP SIGNATURE-----

Joachim Breitner

unread,
Mar 3, 2011, 11:38:05 PM3/3/11
to haskel...@haskell.org
Hi,

Am Freitag, den 04.03.2011, 01:18 +0100 schrieb Jacek Generowicz:
> It seems that I don't understand what groupBy does.
>
> I expect it to group together elements as long as adjacent ones
> satisfy the predicate, so I would expect ALL four of the following to
> give one group of 3 and a group of 1.
>
> Prelude> :m + Data.List
> Prelude Data.List> groupBy (<) "abcb"
> ["abcb"]
> Prelude Data.List> groupBy (<) "abca"
> ["abc","a"]
> Prelude Data.List> groupBy (<) [1,2,3,2]
> [[1,2,3,2]]
> Prelude Data.List> groupBy (<) [1,2,3,1]
> [[1,2,3],[1]]
>
> What am I missing?

this comes up repeatedly. Also see
http://hackage.haskell.org/trac/ghc/ticket/1408

Greetings,
Joachim

--
Joachim "nomeata" Breitner
mail: ma...@joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C
JID: nom...@joachim-breitner.de | http://www.joachim-breitner.de/
Debian Developer: nom...@debian.org

signature.asc

wren ng thornton

unread,
Mar 4, 2011, 1:01:26 AM3/4/11
to Haskell Cafe
On 3/3/11 7:18 PM, Jacek Generowicz wrote:
> Hi Cafe,
>
> It seems that I don't understand what groupBy does.
>
> I expect it to group together elements as long as adjacent ones satisfy
> the predicate, so I would expect ALL four of the following to give one
> group of 3 and a group of 1.
>
> Prelude> :m + Data.List
> Prelude Data.List> groupBy (<) "abcb"
> ["abcb"]
> Prelude Data.List> groupBy (<) "abca"
> ["abc","a"]
> Prelude Data.List> groupBy (<) [1,2,3,2]
> [[1,2,3,2]]
> Prelude Data.List> groupBy (<) [1,2,3,1]
> [[1,2,3],[1]]
>
> What am I missing?

The behavior is that it's comparing subsequent elements to the first
element of the current chunk. I'm not sure how often that'd be a
desirable behavior compared to the one you and I would expect. Of
course, the API only specifies the behavior of groupBy on equality-like
predicates IIRC. So technically either behavior is permissible...

This should be FAQed on the documentation a bit better.

--
Live well,
~wren

wren ng thornton

unread,
Mar 4, 2011, 1:02:02 AM3/4/11
to haskel...@haskell.org
On 3/3/11 8:14 PM, Brandon S Allbery KF8NH wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 3/3/11 20:09 , Jacek Generowicz wrote:
>>> 1< 2 ok, same group
>>> 1< 3 dito
>>> 1< 2 dito
>>> Thus you get [[1,2,3,2]]
>>
>> OK, that works, but it seems like a strange choice ...
>
> Stability is often valued in functions like this: the order of elements is
> not altered.

Making it stable and also comparing adjacent elements is entirely doable.

--
Live well,
~wren

Jacek Generowicz

unread,
Mar 4, 2011, 1:38:39 AM3/4/11
to Brandon S Allbery KF8NH, haskel...@haskell.org

On 2011 Mar 4, at 02:14, Brandon S Allbery KF8NH wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 3/3/11 20:09 , Jacek Generowicz wrote:
>>> 1 < 2 ok, same group
>>> 1 < 3 dito
>>> 1 < 2 dito
>>> Thus you get [[1,2,3,2]]
>>
>> OK, that works, but it seems like a strange choice ...
>
> Stability is often valued in functions like this: the order of
> elements is
> not altered.

I'm failing to see how the behaviour I expected would change the order
of elements: the elements would still come out in exactly the same
order, it is just the boundaries between the groups would be in
different places.

0 new messages