Portability | Haskell98 + CPP + GeneralizedNewtypeDeriving |
---|---|

Stability | provisional |

Maintainer | wren@community.haskell.org |

Safe Haskell | Trustworthy |

Enumerate the rationals in Calkin--Wilf order. That is, when we
give enumeration a well-specified meaning (as Prelude.SafeEnum
does) this renders instances for `Ratio`

problematic. `Ratio`

instances *can* be provided so long as the base type is integral
and enumerable; but they must be done in an obscure order that
does not coincide with the `Ord`

instance for `Ratio`

. Since
this is not what people may expect, we only provide an instance
for the newtype `CalkinWilf`

, not for `Ratio`

itself.

- Jeremy Gibbons, David Lester, and Richard Bird (2006).
*Enumerating the Rationals*. JFP 16(3):281--291. DOI:10.1017/S0956796806005880 http://www.cs.ox.ac.uk/jeremy.gibbons/publications/rationals.pdf

- newtype CalkinWilf a = CalkinWilf (Ratio a)
- unCalkinWilf :: CalkinWilf a -> Ratio a

# Documentation

newtype CalkinWilf a Source

Enumerate the rationals in Calkin--Wilf order. The enumeration is symmetric about zero, ensuring that all the negative rationals come before zero and all the positive rationals come after zero.

BUG: while the `succeeds`

, `precedes`

, `toEnum`

, and `fromEnum`

methods are correct, they are horribly inefficient. This can be
rectified (or at least mitigated), but this remains to be done.

CalkinWilf (Ratio a) |

Integral a => Enum (CalkinWilf a) | |

Eq a => Eq (CalkinWilf a) | |

Integral a => Fractional (CalkinWilf a) | |

Integral a => Num (CalkinWilf a) | |

Integral a => Ord (CalkinWilf a) | |

(Integral a, Read a) => Read (CalkinWilf a) | |

Integral a => Real (CalkinWilf a) | |

Integral a => RealFrac (CalkinWilf a) | |

(Integral a, Show a) => Show (CalkinWilf a) | |

Integral a => Enum (CalkinWilf a) | |

Integral a => DownwardEnum (CalkinWilf a) | |

Integral a => UpwardEnum (CalkinWilf a) |

unCalkinWilf :: CalkinWilf a -> Ratio aSource