Rekursive Tokenizer in Haskell

Question

Ich arbeite eine Aufgabe in Haskell, um für Tests vorzubereiten. Die aktuelle Task fragt nach der folgenden Formel eine Zeichenfolge in Token: Bei der Ausführung von "tokenize str separely remove" sollte es eine Liste von Zeichenfolgen ausgeben. Jedes Zeichen in "str", das in der Zeichenfolge "separate" erscheint, sollte eine Zeichenfolge aus einem Zeichen sein. Jedes Zeichen in "str", das in der Zeichenfolge "remove" erscheint, sollte entfernt werden. Zeichen, die nicht in separater oder remove erscheinen, sollten zusammen gebündelt werden.

Beispiel zeigt, dass

tokenize "a + b* 12-def" "+-*" " " 

ausgeben sollte

["a", "+", "b", "*", "12", "-", "def"] 

meinen aktueller Code unter

tokenize :: String -> String -> String -> [String] 
tokenize [] _ _ = [] 
tokenize [x] _ _ = [[x]] 
tokenize (x:xs) a b  | x `elem` a = [x] : tokenize xs a b 
         | x `elem` b = tokenize xs a b 
         | otherwise = (x:head rest) : tail rest 
           where 
             rest = tokenize xs a b 

Es funktioniert zu einem gewissen Grad, das Problem, dass es zu sein, die Betreiber im Beispiel ist mit dem vorhergehenden Buchstaben gebündelt.

wie diese

["a+","b*","12-","def"] 

trotz der Betreiber in der separaten Zeichenfolge sein.

Answer 1

Zunächst einmal tokenize [x] _ _ ist wahrscheinlich nicht das, was Sie wollen, denn tokenize "a" "" "a" endet als ["a"], wenn es wahrscheinlich [] sein sollte. Zweitens, rufen Sie nicht die Trenn- und Entfernungslisten String s auf. Sie sind nur [Char] s. Es gibt keinen Unterschied darunter, weil type String = [Char], aber der Sinn eines Synonyms ist, eine semantische Bedeutung klarer zu machen, und Sie verwenden nicht wirklich Ihre String s als String s, so dass Ihre Funktion es nicht wert ist. Außerdem sollten Sie die Argumente zu tokenize seps rems str mischen, weil das Currrying einfacher macht. Schließlich möchten Sie wahrscheinlich Data.Set anstelle von [Char] verwenden, aber ich werde es hier nicht verwenden, um näher an der Frage zu bleiben.

Das Problem selbst ist | otherwise = (x:head rest) : tail rest, die ein beliebiges Sonderzeichen auf das nächste Token anheft, auch wenn dieses Token angeblich ein Trennzeichen ist. In Ihrem Fall ist ein Beispiel dafür, wenn head rest = "+" und x = 'a', und Sie ihnen beitreten, so dass Sie "a+" haben. Du musst weiter wachen.

(auch: Ihre Einbuchtung verkorkste: where Klauseln auf gesamte Gleichung binden, so dass es sichtbar durch alle Wachen Sie so eingekerbt ist, dass das ist klar..)

tokenize :: [Char] -> [Char] -> String -> [String] 
tokenize _ _ "" = [] 
tokenize seps rems (x:xs) 
    | x `elem` rems      = rest 
    | x `elem` seps      = [x]:rest 
    -- Pattern guard: if rest has a single-char token on top and that token is a sep... 
    | ([sep]:_) <- rest, sep `elem` seps = [x]:rest 
    -- Otherwise, if rest has a token on top (which isn't a sep), grow it 
    | (growing:rest') <- rest   = (x:growing):rest' 
    -- Or else make a new token (when rest = []) 
    | otherwise       = [x]:rest 
    where rest = tokenize xs seps rems 

Sie können verwenden Sie auch filter:

tokenize seps rems = tokenize' . filter (not . flip elem rems) 
    where tokenize' "" = [] 
     tokenize' (x:xs) 
      | x `elem` seps      = [x]:rest 
      | ([sep]:_) <- rest, sep `elem` seps = [x]:rest 
      | (growing:rest') <- rest   = (x:growing):rest' 
      | otherwise       = [x]:rest 
      where rest = tokenize' xs