Pętla warunkowa w programie użytkowym

Question

Załóżmy, że Parser x jest analizatorem składni, który analizuje numer x. Ten parser prawdopodobnie posiada kombinator many, który analizuje zero lub więcej wystąpień czegoś (zatrzymuje się, gdy parser elementów zawiedzie).

Widzę, jak można to zrealizować, jeśli Parser tworzy monadę. Nie mogę wymyślić, jak to zrobić, jeśli Parser jest tylko Applicative Functor. Wydaje się, że nie ma sposobu, aby sprawdzić poprzedni wynik i zdecydować, co dalej (dokładnie to, co dodają monady). czego mi brakuje?

Answer 1

Alternative klasy typu zapewnia many syntezatora:

class Applicative f => Alternative f where 
    empty :: f a 
    (<|>) :: f a -> f a -> f a 
    many :: f a -> f [a] 
    some :: f a -> f [a] 

    some = some' 
    many = many' 

many' a = some' a <|> pure [] 
some' a = (:) <$> a <*> many' a 

1. many a syntezatora “ oznacza zero lub więcej ” a.
2. Kombinator some a oznacza jeden lub więcej ” a.

więc:

1. some a syntezatora zwraca listę jednego a następnie many a (tj 1 + (0 or more)).
2. Kombinator many a zwraca some a lub pustą listę (tj. (1 or more) | 0).

many syntezatora zależy od (<|>) operatora, który może być postrzegany jako podmiot domyślny w językach takich jak JavaScript. Na przykład, należy rozważyć wystąpienie Alternative z Maybe:

instance Alternative Maybe where 
    empty = Nothing 
    Nothing <|> r = r 
    l  <|> _ = l 

Zasadniczo (<|>) powinna zwrócić wartość po lewej stronie, czy to truthy. W przeciwnym razie powinien zwrócić wartość po prawej stronie.

Parser stanowi strukturę danych, która definiuje się w sposób podobny do Maybe (idea applicative lexer combinators i parsera złożone jest zasadniczo taka sama):

data Lexer a = Fail | Ok (Maybe a) (Vec (Lexer a)) 

przypadku analizowania nie, wartość Fail jest zwracany. W przeciwnym razie zwracana jest wartość Ok. Ponieważ Fail <|> pure [] to pure [], w ten sposób kombinator many wie, kiedy zatrzymać i zwrócić pustą listę.

Answer 2

many jest metodą klasy klasy (link)Alternative co sugeruje, że ogólna aplikacyjnych funktor nie zawsze mają realizację many.

Answer 3

Nie można tego zrobić, używając tylko tego, co zapewnia Applicative.Ale Alternative posiada funkcję, która daje siłę poza Applicative:

(<|>) :: f a -> f a -> f a 

Funkcja ta pozwala „łączyć” dwa Alternatives bez żadnych ograniczeń w ogóle na a. Ale jak? Coś nieodłącznie związanego z konkretnym funktorem f musi dać ci sposób, aby to zrobić.

Zazwyczaj Alternative s wymagają pojęcia awarii lub pustki. Podobnie jak w przypadku analizatorów składni, gdzie (<|>) oznacza "spróbuj to przeanalizować, jeśli się nie powiedzie, spróbuj tego innego". Ale ta "zależność od poprzedniej wartości" jest ukryta w maszynie wykonującej (<|>). Nie jest on dostępny dla zewnętrznego interfejsu.

Z (<|>) można realizować zero lub jedno-syntezatora:

optional :: Alternative f => f a -> f (Maybe a) 
optional v = Just <$> v <|> pure Nothing 

Definicje somemany są podobne, ale wymagają one funkcje wzajemnie cyklicznych.

Należy zauważyć, że istnieją Applicative s, które nie są Alternative s. Na przykład nie można ustawić funktora Identity na Alternative. Jak zaimplementować empty?