patternMinor
Beta Reducer in Haskell
Viewed 0 times
betareducerhaskell
Problem
This is my first Haskell application, so any non-name-calling tips will be taken extremely well! It is just a beta reducer:
I want to know what I could improve on the style or how I could make the code cleaner. I have mostly problems with indentation, I never know where I can (and should) make a newline without confusing the parser.
Comment: making this was ridiculously easier than I thought. The type system actually helped me a lot.
data Term = Var Int | Lam Term | App Term Term | Num Int | Add Term Term
deriving (Show)
subs :: Int -> Term -> Term -> Term
subs depth value (Lam body) = Lam (subs (depth + 1) value body)
subs depth value (App abstraction body) = App (subs depth value abstraction) (subs depth value body)
subs depth value (Var bind)
| bind == depth = inc depth value
| otherwise = Var (bind + depth)
inc :: Int -> Term -> Term
inc depth (Var a) = Var (a + depth)
inc depth (App a b) = App (inc depth a) (inc depth b)
inc depth (Lam a) = Lam (inc depth a)
red :: Term -> Term
red (Var a) = Var a
red (Lam a) = Lam (red a)
red (App (Lam body) value) = red (subs 0 value body)
red (App a b) = (App (red a) (red b))
val = red (App (Lam (Lam (Lam (App (Var 2) (Var 1))))) (Lam (Var 77)))
main = print valI want to know what I could improve on the style or how I could make the code cleaner. I have mostly problems with indentation, I never know where I can (and should) make a newline without confusing the parser.
Comment: making this was ridiculously easier than I thought. The type system actually helped me a lot.
Solution
This looks reasonable and idiomatic to me.
I don't recognise the reduction strategy, though. Specifically, the line
looks like you're not reducing to a normal form, and you might be reducing, say, one redex in the function and one in the argument. This may be intentional on your part, but if it isn't, maybe take a look here for a brief overview of reduction strategies, or here for more detail.
I haven't looked at de Bruijn indices in a while, so I wouldn't be able to promise that your implementation is correct. Nothing untoward comes to mind, though.
About the style–and this is really nitpicking–in the
I don't recognise the reduction strategy, though. Specifically, the line
red (App a b) = App (red a) (red b)looks like you're not reducing to a normal form, and you might be reducing, say, one redex in the function and one in the argument. This may be intentional on your part, but if it isn't, maybe take a look here for a brief overview of reduction strategies, or here for more detail.
I haven't looked at de Bruijn indices in a while, so I wouldn't be able to promise that your implementation is correct. Nothing untoward comes to mind, though.
About the style–and this is really nitpicking–in the
subs definition you might use simply a instead of the cumbersome abstraction. And I'd have indented the | one more space. (See? Nitpicking.)Code Snippets
red (App a b) = App (red a) (red b)Context
StackExchange Code Review Q#44470, answer score: 3
Revisions (0)
No revisions yet.