How can I parse the left associative notation of SKI combinator calculus

user_6185427 0
Viewed 148

I've tried a bunch of stuff, and they always seem to result in one of 2 things:

  • Program hangs forever (infinite left recursion)
  • Right associativity (right recursion)

My only idea now is just to parse from the end of the string instead of the beginning, but do to the list nature of haskell's strings, that would require either traversing the list for every charachter, or parsing a reversed string. Neither option sound good.

Here's the relevant bits from my current code (which is right associative). I've tried left recursion, but it just ends up in an infinite loop.

{-# LANGUAGE PatternGuards #-}

data C = S | K | I deriving (Read,Show,Eq)
data T = N T T | C C deriving Eq

parse :: String -> T
parse s | (e,rest) <- parseStep s = if rest == "" then e else N e (parse rest)

parseStep :: String -> (T,String)
parseStep ('(':s) = parseParen s 
parseStep (c:s) = (C $ read [c],s)

parseParen (c:')':s) = (C $ read [c],s)
parseParen s = parseStep s
haskell
1 Answers

Figured it out thanks to luqui's comment:

parse :: String -> T
parse = foldTs . parseList

foldTs :: [T] -> T
foldTs (t:ts) = foldl N t ts

parseList :: String -> [T]
parseList "" = []
parseList s = let (x,r) = parseStep s in x:parseList r

parseStep :: String -> (T,String)
parseStep ('(':s) = let (ts,r) = parseParenList s in (foldTs ts,r)
parseStep (c:s) = (C $ read [c],s)


parseParenList :: String -> ([T],String)
parseParenList (')':s) = ([],s)
parseParenList s =
  let
    (x,r) = parseStep s
    (xs,r') = parseParenList r
  in (x:xs,r')
user_61854270
Related