group package:base

The group function takes a list and returns a list of lists such that the concatenation of the result is equal to the argument. Moreover, each sublist in the result is non-empty, all elements are equal to the first one, and consecutive equal elements of the input end up in the same element of the output list. group is a special case of groupBy, which allows the programmer to supply their own equality test. It's often preferable to use Data.List.NonEmpty.group, which provides type-level guarantees of non-emptiness of inner lists. A common idiom to squash repeating elements map head . group is better served by map Data.List.NonEmpty.head . Data.List.NonEmpty.group because it avoids partial functions.

Examples

>>> group "Mississippi"
["M","i","ss","i","ss","i","pp","i"]

>>> group [1, 1, 1, 2, 2, 3, 4, 5, 5]
[[1,1,1],[2,2],[3],[4],[5,5]]

The group function takes a stream and returns a list of streams such that flattening the resulting list is equal to the argument. Moreover, each stream in the resulting list contains only equal elements, and consecutive equal elements of the input end up in the same stream of the output list. For example, in list notation:

>>> group "Mississippi"
['M' :| "",'i' :| "",'s' :| "s",'i' :| "",'s' :| "s",'i' :| "",'p' :| "p",'i' :| ""]

The groupBy function is the non-overloaded version of group. When a supplied relation is not transitive, it is important to remember that equality is checked against the first element in the group, not against the nearest neighbour:

>>> groupBy (\a b -> b - a < 5) [0..19]
[[0,1,2,3,4],[5,6,7,8,9],[10,11,12,13,14],[15,16,17,18,19]]

It's often preferable to use Data.List.NonEmpty.groupBy, which provides type-level guarantees of non-emptiness of inner lists.

Examples

>>> groupBy (/=) [1, 1, 1, 2, 3, 1, 4, 4, 5]
[[1],[1],[1,2,3],[1,4,4,5]]

>>> groupBy (>) [1, 3, 5, 1, 4, 2, 6, 5, 4]
[[1],[3],[5,1,4,2],[6,5,4]]

>>> groupBy (const not) [True, False, True, False, False, False, True]
[[True,False],[True,False,False,False],[True]]

group1 operates like group, but uses the knowledge that its input is non-empty to produce guaranteed non-empty output.

groupAllWith operates like groupWith, but sorts the list first so that each equivalence class has, at most, one list in the output

groupAllWith1 is to groupWith1 as groupAllWith is to groupWith

groupBy operates like group, but uses the provided equality predicate instead of ==.

groupBy1 is to group1 as groupBy is to group.

groupWith operates like group, but uses the provided projection when comparing for equality

groupWith1 is to group1 as groupWith is to group

The groupWith function uses the user supplied function which projects an element out of every list element in order to first sort the input list and then to form groups by equality on these projected elements

The class of semigroups (types with an associative binary operation). Instances should satisfy the following:

• Associativity x <> (y <> z) = (x <> y) <> z

You can alternatively define sconcat instead of (<>), in which case the laws are:

• Unit sconcat (pure x) = x
• Multiplication sconcat (join xss) = sconcat (fmap sconcat xss)

A type a is a Semigroup if it provides an associative function (<>) that lets you combine any two values of type a into one. Where being associative means that the following must always hold:

(a <> b) <> c == a <> (b <> c)

Examples

The Min Semigroup instance for Int is defined to always pick the smaller number:

>>> Min 1 <> Min 2 <> Min 3 <> Min 4 :: Min Int
Min {getMin = 1}

If we need to combine multiple values we can use the sconcat function to do so. We need to ensure however that we have at least one value to operate on, since otherwise our result would be undefined. It is for this reason that sconcat uses Data.List.NonEmpty.NonEmpty - a list that can never be empty:

>>> (1 :| [])
1 :| []

• - equivalent to [1] but guaranteed to be non-empty.

>>> (1 :| [2, 3, 4])
1 :| [2,3,4]

• - equivalent to [1,2,3,4] but guaranteed to be non-empty.

Equipped with this guaranteed to be non-empty data structure, we can combine values using sconcat and a Semigroup of our choosing. We can try the Min and Max instances of Int which pick the smallest, or largest number respectively:

>>> sconcat (1 :| [2, 3, 4]) :: Min Int
Min {getMin = 1}

>>> sconcat (1 :| [2, 3, 4]) :: Max Int
Max {getMax = 4}

String concatenation is another example of a Semigroup instance:

>>> "foo" <> "bar"
"foobar"

A Semigroup is a generalization of a Monoid. Yet unlike the Semigroup, the Monoid requires the presence of a neutral element (mempty) in addition to the associative operator. The requirement for a neutral element prevents many types from being a full Monoid, like Data.List.NonEmpty.NonEmpty. Note that the use of (<>) in this module conflicts with an operator with the same name that is being exported by Data.Monoid. However, this package re-exports (most of) the contents of Data.Monoid, so to use semigroups and monoids in the same package just

import Data.Semigroup