Забег на асимптотику.

[thesz]

Посмотрев на асимптотически интересные результаты работы регулярных выражений, решил вспомнить былое и собрать похожее на потоковых процессорах.


import System.Environment

data SP i o = N | I (i -> SP i o) | O o (SP i o)

N ||| spb = spb
spa ||| N = spa
(O o spa) ||| spb = O o (spa ||| spb)
spa ||| O o spb = O o (spa ||| spb)
I fa ||| I fb = I $ \i -> fa i ||| fb i

bindSP N _ = N
bindSP (O o spa) q = bindSP spa q ||| q o
bindSP (I f) q = I $ \i -> bindSP (f i) q

instance Monad (SP i) where
return a = O a N
(>>=) = bindSP

input = I $ \i -> O i N

item c = input >>= \i -> if i == c then return () else N

runSP (O o sp) list = o : runSP sp list
runSP (I f) (x:xs) = runSP (f x) xs
runSP _ _ = []

many p = many1 p ||| return []
many1 p = do { x <- p; xs <- many p; return (x:xs)}

matchNumber 0 p = return ()
matchNumber n p = p >> matchNumber (n-1) p

a = item 'a'

testExpr n = matchNumber n (a >> input) >> matchNumber n a

testString n = replicate n 'a'

test n = runSP (testExpr n) (testString n)

main = do
number <- fmap concat getArgs
let n = (read number) :: Int
case test n of
[] -> return ()
xs -> putStrLn $ "Something went wrong: "++show xs

Результаты прогона:
*Main> :se +s
*Main> test 10
[]
(0.02 secs, 2644724 bytes)
*Main> test 20
[]
(0.02 secs, 0 bytes)
*Main> test 30
[]
(0.00 secs, 0 bytes)
*Main> test 40
[]
(0.00 secs, 0 bytes)
*Main> test 1000
[]
(0.02 secs, 0 bytes)
*Main> test 10000
[]
(0.13 secs, 5331960 bytes)
*Main> test 100000
[]
(1.34 secs, 53661000 bytes)
*Main> test 1000000
[]
(13.19 secs, 538617652 bytes)
*Main>Время сравнения линейно.

Теперь про скорость выполнения в случае компилированного кода (ghc 6.10.1):
...>a.exe 1000000 +RTS -t
...\a.exe 1000000 +RTS -t
<>

...>a.exe 10000000 +RTS -t
...\a.exe 10000000 +RTS -t
<>

...\orel>a.exe 100000000 +RTS -t
...\a.exe 100000000 +RTS -t
<>Вуаля!

Количество потребляемой памяти O(1). Скорость работы постоянна.

PS
Поскольку там есть монадический интерфейс, то можно писать произвольные распознаватели, вплоть до контекстно-зависимых грамматик.