Popularity
7.7
Growing
Activity
4.3
Declining
36
3
1

Tags: Algebra     Math

## acts alternatives and similar packages

Based on the "Algebra" category

• ### algebraic-graphs

A library for algebraic graph construction and transformation
• ### cl3

Clifford Algebra of three dimensional space.

Semilattices
• ### sparse-tensor

typesafe tensor algebra library
• ### partial-semigroup

A partial binary associative operator
• ### multi-instance

Typeclasses augmented with a phantom type parameter
• ### csa

Connection-set algebra (CSA) library
• ### tropical-geometry

A Tropical Geometry package for Haskell
• ### groups-generic

Generically derive Group instances.
• ### cl3-linear-interface

Interface to/from Cl3 and Linear.
• ### cl3-hmatrix-interface

Interface to/from Cl3 and HMatrix.
• ### linear-tests

Linear Algebra

Do you think we are missing an alternative of acts or a related project?

## Introduction

acts is a Haskell library for semigroup actions and torsors.

An act denotes the ability to apply transformations in a compositional way:

``````act g ( act h x ) = act ( g <> h ) x
``````

That is, the target of an act is not necessarily a semigroup, but can be transformed by a semigroup.

Note that this is a left act (elements of the semigroup act on the left). This library does not define right acts, but they can be emulated as left acts of the opposite semigroup by using the `Dual` newtype.

When there's a unique transformation taking one element to another element, the act is said to be a torsor:

``````act ( x --> y ) x = y
``````

## Points and vectors

Addition of points in the plane is not meaningful, but points can be translated by spatial vectors, and given any two points there is a unique translation taking the first point to the second point.

``````data Point2D a = Point2D !a !a
deriving stock ( Show, Generic )
deriving ( Act ( Vector2D a ), Torsor ( Vector2D a ) )
via Vector2D a
newtype Vector2D a = Vector2D { tip :: Point2D a }
deriving stock Show
deriving ( Semigroup, Monoid, Group )
via GenericProduct ( Point2D ( Sum a ) )
``````

Here we use `DerivingVia` and generics (with generic-data and groups-generic) to obtain the relevant instances.

``````p1, p2, p3 :: Point2D Double
p1 = Point2D 0.5 2.5
p2 = Point2D 1.0 0.0
p3 = Point2D 1.0 4.0

v1, v2 :: Vector2D Double
v1 = Vector2D ( Point2D 0.0 1.0 )
v2 = Vector2D ( Point2D 1.0 1.0 )
``````

``````> p1 <> p2
``````
``````* No instance for (Semigroup (Point2D Double))
arising from a use of `<>`
``````

``````> v1 <> v2
Vector2D {tip = Point2D 1.0 2.0}
``````

as well as reverse them:

``````> invert v1
Vector2D {tip = Point2D 0.0 (-1.0)}
``````

Two points form a vector:

``````v12, v13, v23 :: Vector2D Double
v12 = p1 --> p2
v13 = p1 --> p3
v23 = p2 --> p3
``````
``````> v12
Vector2D {tip = Point2D 0.5 (-2.5)}
``````

We can translate points by vectors:

``````> act v12 p1
Point2D 1.0 0.0
``````
``````> act ( invert v12 ) p2
Point2D 0.5 2.5
``````

Translations compose:

``````> v13
Vector2D {tip = Point2D 0.5 1.5}
``````
``````> v23 <> v12
Vector2D {tip = Point2D 0.5 1.5}
``````

As we are acting on the left, transformations compose from right to left, just like function composition:

``````act ( b --> c ) . act ( a --> b ) = act ( a --> c )
``````

This looks slightly more intuitive using `(<--)`:

``````act ( c <-- b ) . act ( b <-- a ) = act ( c <-- a )
``````

Note that in the case of translation these distinctions are irrelevant, as translations form a commutative group.

## Time

We can similarly distinguish absolute time (such as time obtained by querying the operating system) and time differences.

``````newtype Seconds   = Seconds { getSeconds :: Double }
deriving stock Show
deriving ( Act TimeDelta, Torsor TimeDelta )
via TimeDelta
newtype TimeDelta = TimeDelta { timeDeltaInSeconds :: Seconds }
deriving stock Show
deriving ( Semigroup, Monoid, Group )
via Sum Double
``````

The distinction is useful to prevent mixing up absolute times with time differences, so that one doesn't accidentally add two absolute times together:

``````> Seconds 3 <> Seconds 4
``````
``````* No instance for (Semigroup Seconds) arising from a use of `<>`
``````

This might seem trivial in isolation, but in the middle of a complex application it can be very helpful to have the compiler enforce this distinction, so that one doesn't have to e.g. remember whether the time value one has elsewhere stored in an `IORef` is absolute or relative.

Having to manually unwrap the `TimeDelta` newtype at use-sites would prove to be quite inconvenient; instead the interface this library provides comes in handy:

``````> act ( TimeDelta ( Seconds 3 ) ) ( Seconds 4 )
Seconds {getSeconds = 7.0}
``````
``````> Seconds 3 --> Seconds 4 :: TimeDelta
TimeDelta {timeDeltaInSeconds = Seconds {getSeconds = 1.0}}
``````

This can be used for instance to tick down a timer after some time has elapsed:

``````countdownTimer :: Seconds -> Seconds -> TimeDelta -> TimeDelta
countdownTimer startTime endTime timeRemaining =
act ( endTime --> startTime ) timeRemaining
``````

## Musical intervals

Acts.Examples.MusicalIntervals demonstrates the application of this library to musical intervals.

In summary:

• Musical note names are a torsor under the cyclic group of order 7
``````  -- Cyclic group of order 7.
type C7 = Sum ( Finite 7 ) -- 'Finite' from the 'finite-typelits' package

data NoteName = C | D | E | F | G | A | B
deriving stock    ( Eq, Show, Generic )
deriving anyclass Finitary
deriving ( Act C7, Torsor C7 )
via Finitely NoteName
``````

In this case we use the finitary package to derive the action, using the newtype `Finitely`.

• Musical notes are a torsor under musical intervals, meaning that:

• we can transpose notes by musical intervals
``````diminished7th :: [ Interval ]
diminished7th = [ Interval 1 Natural, Interval 3 Flat, Interval 5 Flat, Interval 7 DoubleFlat ]

> map ( `act` Note G Sharp 3 ) diminished7th
[ "G#3", "B3", "D4", "F4" ]
``````
• we can compute intervals between notes
``````> Note F Natural 3 --> Note B Natural 3 :: Interval
Interval 4 Sharp
"augmented 4th up"

> Note E Flat 4 --> Note C Flat 6 :: Interval
Interval 13 Flat
"minor 13th up"
``````

## Comparison with existing libraries

The main purpose of this library is to provide convenient functionality for torsors. Other packages such as torsor, vector-space, simple-affine-space and Linear.Affine concentrate on affine spaces (as reflected in their syntax), and as a result don't naturally cover the use case of finite actions (such as the action of a cyclic group on musical notes given above).

The other design choice of this library is to focus on using newtypes and let users choose instances with `DerivingVia`, trying to re-use newtypes from the `base` library when possible.
This works around some difficulties with overlapping instances (although it is hardly a robust or comprehensive solution).
To compare with other libraries that define semigroup actions (but not torsors):

• semigroup-actions uses a similar approach, but the use of a newtype for the action of a semigroup on itself precludes many useful usages of `DerivingVia` (such as the affine space and time examples given above).
• monoid-extras also defines newtypes for instances, but these aren't easily usable with `DerivingVia` as they focus on the first (instead of last) type parameter.

This library is also careful to distinguish left and right actions, with the `Dual` newtype:

``````instance ( Semigroup s, Act s a, Act t b ) => Act ( Dual s, t ) ( a -> b ) where
act ( Dual s, t ) p = act t . p . act s
``````

This captures the fact that, if `a` has a left action by `s`, and `b` a left action by `t`, then `a -> b` has a right action by `s` and a left action by `t`.