4 kyu
Lambda term reduction
35 of 62hhelwich
Loading description...
Mathematics
Logic
Functional Programming
Algorithms
Trees
View
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
In the description, the
reduce()
method is required to return a lambda object, but the tests expect a string instead.Can you specify which tests? All the existing solutions I can see return a lambda object, and not a string...?
Don't we need to know anything about alpha-reduction to pass this kata?
You don't explain how we should "apply" terms.
I'm also thinking about it (alpha-reduction). In general, the substitution operation requires that the variable "v" bound by an abstraction "lambda v.body" shouldn't be free in a term which is to replace some variable in the abstraction body (one can say "v" should be "fresh" for the substitution term). Otherwise, an alpha-reduction should be done to avoid changes in semantics. In some random tests such a situation may appear. In my solution https://www.codewars.com/kata/reviews/55f3256f0fd3072e02000115/groups/64f846e2717c5300019e476e, I throw an error then. Anyway, if I ignore it and "force" substitution with usual rules, all tests are passed.
This was a bit more difficult than I expected on 4 kyu... I liked it, but I didn't plan to spend half of my day with debugging today. :)
Tests have been updated to use chai, and refactored. Reference solution had a rare bug, so I swapped it out before approval.
How is this kata a part of
-4
collections?? Either I don't understand the metric, or Codewars has a bug.https://github.com/codewars/codewars.com/issues/2185
Haskell translation
Needs random tests
I've added random tests.
The ß-reduction described is one step of reduction. The later tests (the Church encoded stuff) mostly require at least one extra step of reduction. However, OR TRUE FALSE crashes when I do a second step of reduction. I haven't yet figured out what the problem is. Otherwise, my solution seems to work (at least mostly) for doing that one step of reduction (I'm passing the first six blocks of tests, then it's hit-and-miss).
When, in general, is it safe to do another step of reduction? When, in general, do I need to do another step of reduction?
This is the second lambda evaluator kata I'm doing; for the first one (Lambda Calculus Evaluator) I wrote a greedy evaluator which, of course, tanked; now I have a lazy one, but it's tanking as well because it's too lazy. It's getting frustrating. :[ That's not a problem with the respective kata, I'm just missing something. But I don't know exactly what it is. There seems to be no middle ground between lazy and greedy. All my documentation research is getting me nowhere; this problem is just never mentioned.
I don't even know if I'm asking for a very bad spoiler. But any help would be appreciated. If my problem isn't clear, I'm happy to expand.
It's never safe to reduce another step, but you need to when finding yourself with abstraction value @ after reducing an application. This is not in the description.
Also not in the description is that lazy evaluation will not be necessary for this kata.