Что хотел спросить.

[thesz]

Давным-давно я написал статью по разборщики на потоковых процессорах.

Так вот, работают они совершенно нелинейно. Простой разборщик наподобие \n -> prun (pmany (ptoken '1' `ppar` ptoken '2')) (replicate n '1') работает за квадратичное от n время.

Есть у меня подозрение, что это из-за того, что ppar реализован не как исключающий ppar монадных

Comments

[lomeo]

Первое что в голову приходит

из определения ppar следует, что если параметром будет Get, то обе части (fa i) `ppar` (fb i) будут считаться, если fa i НЕ Put, т.е. попробуй переставить определение так:

ppar (Put o sp) spb = Put o (sp `ppar` spb)
ppar Null sp = sp
ppar (Get fa) (Get fb) = Get (\i -> (fa i) `ppar` (fb i))
ppar sp (Put o spb) = Put o (sp `ppar` spb)
ppar sp Null = sp

и погляди что получится. А я спать.

[rvp74]

В parsec если две альтернативы имеют одинаковый head, то вторая альтернатива не рассматривается.
Что в нашем случае служит признаком разбора начала? Как я понял этим признаком служит Put.

Поэтому первую строку наверное стоит написать так:

ppar (Put o sp) _ = Put o sp

и будет также эффективно как и в parsec (но с теми же ограничениями).

[thesz]

Ага. Но вот ограничений Parsec я бы хотел избежать. ;)

[rvp74]

ограничение частично обходится с помощью try:

optLexeme p = try (fmap Just p) <|> return Nothing

declare = optLexeme (keyword "const") >> kwOneOf ["int", "short", "float"]

parser

[rvp74]

Глянул твой pseq и решил переписать все с нуля ;)

data SP a b = NullSP | Put b (SP a b) | Get (a -> SP a b)

failSP = NullSP

returnSP a = Put a NullSP

seqSP NullSP f = NullSP
seqSP (Get h) f = Get $ \a -> seqSP (h a) f
seqSP (Put b spa) f = f b `parSP` seqSP spa f

parSP :: SP a b -> SP a b -> SP a b
parSP NullSP spb = spb
parSP spa NullSP = spa
parSP (Put b spa) spb = Put b $ parSP spa spb
parSP spa (Put b spb) = Put b $ parSP spa spb
parSP (Get fa) (Get fb) = Get $ \a -> parSP (fa a) (fb a)

mapSP f NullSP = NullSP
mapSP f (Get g) = Get $ \a -> mapSP f (g a)
mapSP f (Put b sp) = Put (f b) (mapSP f sp)

instance Monad (SP a) where
return = returnSP
(>>=) = seqSP
fail _ = failSP

instance Functor (SP a) where
fmap = mapSP

readInput = Get $ returnSP

char c = do
a <- readInput

Re: parser

[thesz]

С чего бы это она отбрасывается?

Нисколечки она не отбрасывается.

Рассинхронизации не произойдет, поскольку мы сперва выдадим все возможные на данный момент результаты, а затем запросим вход.

Вообще, потоковые процессоры мне нравятся. Только я их дальше разборщиков не освоил. ;)

Re: parser

[rvp74]

В семантику <|> не должна входить выдача результа альтернативы до момента отказа первой альтернативы. Не путай с par

Re: parser

[thesz]

О! Его реализации у тебя нет. Понял.