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.
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 ..