Main.hs 1.28 KB
Newer Older
sof's avatar
sof committed
1 2 3
-- !!! Wentworth's version of a program to generate
-- !!! all the expansions of a generalised regular expression
-- !!!
4
--
5 6
-- RJE: Modified so it only outputs the number of characters in the output,
-- rather that the output itself, thus avoiding having to generate such a
rje's avatar
rje committed
7 8
-- huge output file to get a reasonable execution time.

9 10
module Main (main) where

11
import Data.Char
Sebastian Graf's avatar
Sebastian Graf committed
12
import Control.Monad (replicateM_)
13
import System.Environment
Sebastian Graf's avatar
Sebastian Graf committed
14
import NofibUtils (hash)
sof's avatar
sof committed
15

Sebastian Graf's avatar
Sebastian Graf committed
16
main = replicateM_ 500 $ do
17
  (regex:_) <- getArgs
Sebastian Graf's avatar
Sebastian Graf committed
18
  print (hash (concat (expand regex)))
rje's avatar
rje committed
19 20 21

numchars :: [String] -> Int
numchars l = sum $ map length l
22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

expand []	= [""]
expand ('<':x)	= numericRule x
expand ('[':x)	= alphabeticRule x
expand x	= constantRule x

constantRule (c:rest) = [ c:z | z <- expand rest ]

alphabeticRule (a:'-':b:']':rest)
  | a <= b  	= [c:z | c <- [a..b],	      z <- expand rest]
  | otherwise	= [c:z | c <- reverse [b..a], z <- expand rest]

numericRule x
  = [ pad (show i) ++ z
	| i <- if u < v then [u..v] else [u,u-1..v]
	, z <- expand s ]
  where
    (p,_:q) = span (/= '-') x
    (r,_:s) = span (/= '>') q
    (u,v)   = (mknum p, mknum r)
sof's avatar
sof committed
42
    mknum s = foldl (\ u c -> u * 10 + (ord c - ord '0')) 0 s
43 44
    pad s   = [ '0' | i <- [1 .. (width-(length s))]] ++ s
    width   = max (length (show u)) (length (show v))