The regex-type package

[Tags:bsd3, library]

Regular expression matching of Haskell types using nondeterministic finite automata.


[Skip to Readme]

Properties

Versions 0.1.0.0
Dependencies base (>=4.8 && <=4.9) [details]
License BSD3
Author Csongor Kiss
Maintainer kiss.csongor.kiss@gmail.com
Category Data
Home page https://github.com/kcsongor/regex-type
Source repository head: git clone https://github.com/kcsongor/regex-type
Uploaded Fri Apr 1 18:57:03 UTC 2016 by kcsongor
Distributions NixOS:0.1.0.0
Downloads 54 total (5 in the last 30 days)
Votes
0 []
Status Docs available [build log]
Last success reported on 2016-04-01 [all 1 reports]

Modules

[Index]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees

Readme for regex-type

Readme for regex-type-0.1.0.0

regex-type

Regular expression matching of Haskell types using nondeterministic finite automata

This is a playground for writing type-level code using TypeFamilies.

Some examples that work:

-- encode the following regex: (Int | Char | (Bool -> Bool)) (String | (Int -> Bool))
regex :: ('[a, b] ~= ((Int :| Char :| (Bool -> Bool)) :> (String :| (Int -> Bool)))) => a -> b
regex = undefined

-- The type of these functions all match the regular expression defined in the type of regex
-- so they all typecheck
test1 :: Int -> String
test1 = regex

test2 :: Int -> Int -> Bool
test2 = regex

test3 :: Char -> String
test3 = regex

test4 :: Char -> Int -> Bool
test4 = regex

test5 :: (Bool -> Bool) -> Int -> Bool
test5 = regex

test6 :: (Bool -> Bool) -> String
test6 = regex

-- This doesn't satisfy the regex, and thus a type error occurs
test_wrong :: Int -> Bool
test_wrong = regex


-- Doesn't typecheck because the list doesn't satisfy the (Int*) regex.
test_wrong2 :: ('[Int, Int, Int, Int, Char] ~= (Rep Int)) => a -> a
test_wrong2 = id

-- test7 can only be called with a ~ Int
test7 :: ('[Int, Int, Int, Int, a] ~= (Rep Int)) => a -> a
test7 = id

TODO:

  • Improve performance
  • Make it a proper library
  • Try converting the NFA to a DFA. I don't know if this will make it faster overall, as I suspect the automaton is reconstructed every time, which means an exponential complexity on each check with the DFA. Maybe an on-demand construction?
  • Figure out if it's actually useful for anything