finite: Finite ranges via types

[ library, mit, types ] [ Propose Tags ]

A framework for capturing finite ranges with types, where the sizes of the ranges are not fixed statically at compile time, but instead are passed at run-time via implicit parameters.

This is especially useful for objects of bounded size, e.g. finite automata, where the number of elements being part of the object, e.g. the number of states, is well-defined in the context of the object.


[Skip to Readme]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

Versions [RSS] 1.4.1.1, 1.4.1.2
Dependencies array (>=0.5 && <0.6), base (>=4.7 && <4.15), containers (>=0.5 && <0.7), hashable (>=1.2), QuickCheck, template-haskell (>=2.11) [details]
License MIT
Author Felix Klein <klein@react.uni-saarland.de>
Maintainer Felix Klein <klein@react.uni-saarland.de>
Category Types
Source repo head: git clone https://github.com/kleinreact/finite
Uploaded by kleinreact at 2021-01-25T12:02:07Z
Distributions
Downloads 378 total (18 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2021-01-25 [all 1 reports]

Readme for finite-1.4.1.2

[back to package description]

Finite

The library provides the Haskell class Finite, which allows to associate types with finite ranges of elements in the context of a bounding environment. The purpose of the class is to simplify the handling of objects of bounded size, e.g. finite-state machines, where the number of elements can be defined in the context of the object, e.g. the number of states.

Main Features

  • Easy access to the object's elements via types.

  • Efficient bidirectional mappings between indices and the elements.

  • Implicit total orderings on the elements.

  • Powerset Support.

  • Extension of a single context to a range of contexts via collections.

  • Easy passing of the context via implict parameters.

  • Generics Support: Finite range types can be easily constructed out of other finite range types using Haskell's data constructor.

  • Template Haskell: Easy creation of basic finite instances using short Haskell templates, as well as the extension of existing types to more feature rich parameter spaces.

Example: Finite-State Machines

import Finite
import Finite.TH

-- create two new basic types for the states and labels of the FSM
newInstance "State"
newInstance "Label"

-- FSM data type
data FSM =
  FSM
    { states :: Int
    , labels :: Int
    , transition :: State -> Label -> State
    , accepting :: State -> Bool
    , labelName :: Label -> String
    }

-- connect the types with corresponding bounds, as defined by the FSM
baseInstance [t|FSM|] [|states|] "State"
baseInstance [t|FSM|] [|labels|] "Label"

-- FSM Show instance for demonstrating the features of 'Finite'
instance Show FSM where
  show fsm =
    -- set the context
    let ?bounds = fsm in
    -- show the data
    unlines $
      [ "The FSM has " ++ show (elements ((#) :: T State)) ++ " states."
      ] ++
      [ "Labels:"
      ] ++
      [ "  (" ++ show (index l) ++ ") " ++ labelName fsm l
      | l <- values
      ] ++
      [ "Transitions:"
      ] ++
      [ "  " ++ show (index s) ++ " -- " ++ labelName fsm l ++
        " --> " ++ show (index (transition fsm s l))
      | s <- values
      , l <- values
      ] ++
      [ "Accepting:"
      ] ++
      [ "  " ++ show (map index $ filter (accepting fsm) values)
      ]