Module

Data.Bottom

Package
purescript-higher-order
Repository
matthew-hilty/purescript-higher-order

#Bottom Source

class Bottom (a :: Type)  where

The Bottom typeclass registers partially ordered types that have a least element or lower boundary.

Because the notion of minimality entails the notion of comparability, the semantics of an instance of Bottom must be consistent with the definitional requirements of a partial order. In fact, most instances of Bottom are also instances of PartialOrd (and likely Ord as well).

In such cases, when a type a is both a registered instance of Bottom and one of PartialOrd, it must satisfy the following law:

  • minimality: x >=? bottom == Just true

Likewise, if a is an instance of Bottom and also an instance of Ord, it must satisfy the following analogous law:

  • minimality: x >= bottom

However, although the semantics of Bottom-registered types must be consistent with the laws of partial ordering, a PartialOrd registration may not be possible or suitable for all Bottom instances. The implementation details of the datatype may preclude an instance declaration. Alternatively, the properties of the type may make such an instance declaration impractical.

For example, many container-like datatype operators support a total order (therefore, also a partial order) when they act on total orders. Array Int, for instance, is a total order because Int is a total order. However, the bottom element of such container types is generally independent of the type argument of the container's type constructor. The bottom element of Array a, for instance, is [] whether a is Int, String, any other Ord instance, or, conceivably, any other type at all. That is to say, Array a, for any unconstrained a, satisfies Bottom. Were a PartialOrd registration a prerequisite of Bottom- instance declarations, some choice of PartialOrd implementation satisfiable by Array a for all a would be necessary. Such an implementation might be the following:

-- # 1
instance partialOrdArray :: PartialOrd (Array a) where
  pCompare x y
    | null x, null y -> Just EQ
    | null x         -> Just LT
    | null y         -> Just GT
    | otherwise      -> Nothing

This choice is, however, rather coarse for likely uses of partially orderable arrays. Arrays often contain values of types satisfying Ord, and a better PartialOrd definition for these kinds of arrays might be the following:

-- # 2
instance partialOrdArray :: Ord a => PartialOrd (Array a) where
  pCompare x y = Just $ compare x y

The existence of two reasonable PartialOrd definitions for Array a suggests that preferring more-granular definitions whenever possible, while using #1 above as a backup implementation would be a useful general strategy. Instance chaining is the standard technique in PureScript to effect this kind of typeclass-instance contingency. However, the current strategy of instance resolution by the PureScript compiler rules out instance chaining in cases like this. Because both declarations in the would-be chain (see below) share the same head (namely, Array), the second definition (the backup definition) would not be checked or attempted.

instance partialOrdArray :: Ord a => PartialOrd (Array a) where
  pCompare x y = Just $ compare x y
else instance partialOrdArray :: PartialOrd (Array a) where
  pCompare x y
    | null x, null y -> Just EQ
    | null x         -> Just LT
    | null y         -> Just GT
    | otherwise      -> Nothing

Therefore, to make Bottom registrations of unconstrained Array a and other similar types possible, without also mandating compiler-ignored (and possibly idle) PartialOrd definitions, the Bottom typeclass does not declare PartialOrd as a prerequisite superclass.

Members

Instances

Modules
Data.Bottom
Data.Operator.Bottom
Data.Operator.Eq
Data.Operator.Generic.Rep
Data.Operator.Ord
Data.Operator.PartialOrd
Data.Operator.Top
Data.PartialOrd
Data.Top