Strip `FALSE` prefix from Boolean list using the y-combinator? Stumped

Viewed 78

Given a list, e.g. (f: f FALSE (g: g FALSE (h: h TRUE FALSE))), write an operator that removes all leading FALSEs and returns only the tail that starts with TRUE. For this example the operator should return just (h: h TRUE FALSE).

This is an exercise, in fact a level, in this game called "functional" that I've become obsessed with. In the previous level we were required to generalized \Omega into the y-combinator so I imagine that this level requires the y-combinator in order to handle a FALSE prefix of arbitrary length.

I'm able to handle a single FALSE prefix with (b: c: IF b (f: f b c) c). Imagining that operator as f I'm guessing the answer should look something like (b: c: IF b (f: f b c) (Y c)). The game is rejecting that answer complaining about "no reduction (grew too big)".

I'm clearly baffled by the y-combinator. Can someone show me how to use it correctly?

Also, what is this crazy syntax the game is using? I don't see it used anywhere else.

As requested, a link to functional's page on Steam is here. I also recently uncovered a link the projects page on github here.

1 Answers

Try this: Y(f: x: (FST x) x (f(SND x))).

By using Y-combinator, it returns the whole list (x) if the head (FST x) is TRUE and recursively calls itself taking the tail (SND x) as an argument otherwise.

Related