Functional while loops – no, really! | Bill Wadge's Blog

submited by
Style Pass
2021-06-24 05:30:07

As I’ve explained I invented and implemented a small functional language (PYFL) to test out some ideas. In particular one idea is the (oxymoronic) functional while loop.

Functional programming involves churning out endless tail recursions, as most of you know. A typical tail recursion is finding the sum of the squares of the elements of a list:

This definition follows a common pattern (technically, a schema) in which the general case is some function of the head of list l and the result of applying the function being defined to the tail of l. We could express the schema as

A more challenging example is removing the duplicates in the argument so that nodups(l) has the same elements as l but with each appearing only once. Eventually we come up with

The only trouble is that nodups removes the first copies of an element and as a result they are not in the original order: nodups([1 3 5 3]) is [1 5 3]. If we want to preserve the original order as well, the schema fails us.

Leave a Comment