Czy można wyrazić chainl1 za pomocą aplikacji?

Question

Czy można wyrazić kombinator chainl1 z Parsec nie używając instancji Monad zdefiniowanej przez parsec?

chainl1 p op = 
    do x <- p 
    rest x 
    where 
    rest x = do f <- op 
       y <- p 
       rest (f x y) 
      <|> return x 

Answer 1

Tak, to jest:

chainl1 p op = foldl (flip ($)) <$> p <*> many (flip <$> op <*> p) 

Chodzi o to, że trzeba przeanalizować p (op p)* i ocenić go jako (...(((p) op p) op p)...).

To może pomóc rozszerzyć definicję trochę:

chainl1 p op = foldl (\x f -> f x) <$> p <*> many ((\f y -> flip f y) <$> op <*> p) 

Jak par op i p są analizowane wyniki są stosowane natychmiast, ale ponieważ p jest prawo operand op, potrzebuje flip.

Tak więc typ wyniku many (flip <$> op <*> p) to f [a -> a]. Ta lista funkcji jest następnie stosowana od lewej do prawej na wartości początkowej p przez foldl.

Answer 2

brzydki ale równoważne Applicative definicja:

chainl1 p op = 
    p <**> 
    rest 
    where 
    rest = flip <$> op <*> 
      p <**> 
      pure (.) <*> rest 
     <|> pure id 

Zamiast przejścia po lewej stronie argumentu x wyraźnie do prawej op, op „s to aplikacyjnych formie„łańcuchy”częściowo stosowane do ich prawy- Argument boczny (stąd flip <$> op <*> p) poprzez podniesiony kombinator (.), a następnie zastosowanie najbardziej po lewej p poprzez (<**>) do wynikowego rest :: Alternative f => f (a -> a).