Function composition in boolean operators

Question

I don't have much FP experience and I think I'm just missing a key insight from someone more versed. I'm writing a small, embedded, functional, strictly- and invariantly-typed language.

I'll be using Haskell-like syntax in this question.

The following signatures are for predefined functions with types that are what you'd expect:

and :: bool -> bool -> bool  -- boolean and
lt  :: int -> int -> bool    -- less than
gt  :: int -> int -> bool    -- greater than
len :: list -> int           -- list length

My job is to compose these functions (and constants) to form an expression which has the following signature:

λ :: list -> bool

The result of which is whether a list has a length between 1 and 99.

Constraints: This language (currently) only supports function application and function composition. No lambda expressions, no higher-order functions.

This is how far I've gotten:

and . ((gt 0) . len) :: list -> bool -> bool

This takes a list, checks if it's length is greater than 0, then a boolean and returns the "and" of both arguments.

But now I'm stuck. How would you continue from here in traditional functional languages? Is there a way to express a solution without lambdas/closures?

I'm open to add new features to the language, as long as it remains underpowered and simple.

In Haskell you could write f x = ((gt 0) len x) && ((lt 100) len x). Do you accept that in your language ? — V. Semeria
@leftaroundabout no functions that take other functions as arguments. — thwd
Your language already has one higher-order function: composition. — chepner
I believe that, with that list of primitives, you can never use an argument twice. Everything there looks strictly linear: you use it, you lose it. This is known, I think, to greatly reduce the expressive power of the language. You need some duplicator, like S in combinatory logic or &&& in arrows. Or let x = e in .... — chi

Alexey Romanov Alexey Romanov · Accepted Answer · 2016-09-01T09:57:13

This is called pointfree style and there is a nice tool on the web for transforming Haskell code to it. Converting f xs = (length xs > 0) && (length xs < 100) gives f = ap ((&&) . (> 0) . length) ((< 100) . length). So you are just missing the ap function (see also Understanding `ap` in a point-free function in Haskell). For your application it should have type (a -> b -> c) -> (a -> b) -> (a -> c) and be built-in along with ..

Function composition in boolean operators

1 Answers