Applicative Parser of Lambda Exprs, Haskell

Language: Layout:

--ghc 8.0.2

import Control.Applicative

main = print $ parse parseLe "(lx.(x) (ly.y)) (ly.(x) (x))"

newtype Parser a = P (String -> [(a, String)])
parse :: Parser a -> String -> [(a, String)]
parse (P p) inp = p inp

instance Functor Parser where
  -- fmap :: (a -> b) -> Parser a -> Parser b
  fmap g p = P (\inp -> map (\(v,out) -> (g v, out)) (parse p inp))

instance Applicative Parser where
  -- pure :: a -> Parser a
  pure v = P (\inp -> [(v,inp)])
  -- <*> :: Parser (a -> b) -> Parser a -> Parser b
  pg <*> px = P (\inp -> [(f v, sv) | (f, sf) <- parse pg $ inp, (v, sv) <- parse px $ sf])

instance Alternative Parser where
  empty = P (const [])
  px <|> py = P (\s -> (parse px s) ++ (parse py s))

findSuccessParse :: [(a,String)] -> Maybe a
findSuccessParse [] = Nothing
findSuccessParse ((h,t):xs) = if (t == "") then (Just h) else (findSuccessParse xs)

parseString :: String -> Parser a -> Maybe a
parseString s (P p) = (findSuccessParse (p s))

predP :: (Char -> Bool) -> Parser Char
predP p = P f
  where
    f "" = []
    f (c : cs) | p c = [(c, cs)]
               | otherwise = []

stringP :: String -> Parser String
stringP s = P f
  where
    f s1 | s == s1 = [(s, "")]
         | otherwise = []

isDigit :: Char -> Bool
isDigit c = ((c >= '0') && (c <= '9'))

digitParser = (predP isDigit)
    
numberParser = (some digitParser)

charP = predP . (==)

data Le = VarExpr Char | Lambb Char Le | App Le Le deriving (Eq, Show)

parseLe :: Parser Le
parseLe = parseLetter <|> parseLambda <|> parseApp

parseLambda =
  charP 'l' *>
    (Lambb <$> (predP isLet) <*>
                (charP '.' *> parseLe))

parseApp =
  charP '(' *>
    (App <$> parseLe
    <*> (charP ')' *> charP ' '*> charP '('*> 
    parseLe))<* charP ')'

parseLetter = VarExpr <$> (predP isLet)

isLet x | (x>='a' && x<='z') = True
        | otherwise = False

Show compiler warnings [ + ] Compiler args [ + ] Show input
Compilation time: 0.82 sec, absolute running time: 0.16 sec, cpu time: 0.01 sec, memory peak: 5 Mb, absolute service time: 1,18 sec