fork download 
  1. 1import Prelude hiding (succ)
  2. import Data.Functor
  3. import Text.Parsec
  4. import Text.Parsec.String
  5.  
  6. data Expr = V Int       -- Value (Index)
  7.           | L Expr      -- Lambda
  8.           | A Expr Expr -- Application
  9.           deriving Show
  10.  
  11. beta :: Expr -> Expr    -- reduction
  12. beta (A (L v) n)    = beta $ subst 0 v $ beta n
  13. beta (A m n)        = beta $ A (beta m) n
  14. beta e              = e
  15.  
  16. subst :: Int -> Expr -> Expr -> Expr -- substitude
  17. subst v (L w) e     = L (subst (v + 1) w e)
  18. subst v (A m n) e   = A (subst v m e) (subst v n e)
  19. subst v (V n) e | n < v  = V n
  20.                 | n == v = subst' 0 v e
  21.                 | n > v  = V (n - 1)
  22.                 where subst' t v (L w)     = L (subst' (t + 1) v w)
  23.                       subst' t v (A m n)   = A (subst' t v m) (subst' t v n)
  24.                       subst' t v (V n) | n <= t = V n
  25.                                        | n > t  = V (n + v - 1)
  26.  
  27. s = L (L (L (A (A (V 2) (V 0)) (A (V 1) (V 0)))))
  28. k = L (L (V 1))
  29. i = L (V 0)
  30.  
  31. zero = (L (L (V 0)))
  32. succ = (L (L (L (A (V 1) (A (A (V 2) (V 1)) (V 0))))))
  33. cons = (L (L (L (A (A (V 0) (V 2)) (V 1)))))
  34. car  = (L (A (V 0) (L (L (V 1)))))
  35. cdr  = (L (A (V 0) (L (L (V 0)))))
  36.  
  37.  
  38. pExpr, pTerm, pS, pK, pI, pPa :: Parser Expr
  39. pExpr = foldl1 A <$> many1 pTerm
  40. pTerm = pS <|> pK <|> pI <|> pPa
  41.  
  42. pS = char 'S' >> return s
  43. pK = char 'K' >> return k
  44. pI = char 'I' >> return i
  45. pPa = between (char '(') (char ')') pExpr
  46.  
  47. codeToExpr = parse pExpr ""
  48.  
  49. main = case codeToExpr "(SK)K" of
  50.         Left err  -> print err
  51.         Right val -> print (beta val)
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
[1 of 1] Compiling Main             ( prog.hs, prog.o )

prog.hs:1:1: parse error on input `import'
stdout 
Standard output is empty
https://ideone.com/zedoy
language:
Haskell (ghc 8.4.4)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!