Haskell Function Composition - (a -> b) -> (a -> c) -> (b -> c -> d) -> (a -> d)

7
votes

I would like to learn how the following would be done in point-free: 

withinBounds :: [Int] -> Bool
withinBounds xs = (all (>= 0) xs) && (all (<= 8) xs)

I understand that it is superior to write it this way for readability/sanity's sake, but I'd like to learn more about how I can compose functions. I've been scratching my head as to how I can do this. The whole (expanded?) type signature is 

[Int] -> ([Int] -> Bool) -> ([Int] -> Bool) -> (Bool -> Bool -> Bool) -> Bool

The type signature of the composition I'm trying to get to is

(a -> b) -> (a -> c) -> (b -> c -> d) -> (a -> d)

I wrote the following as notes in a bastard-lambda form. If there is a way to somewhat simplify the problem with the lambda calculus, it'd be great if that could be explained too:

\L@[] ->  \f1@([] -> Bool) -> \f2@([] -> Bool) -> \f3@(Bool -> Bool -> Bool) -> f3.(f1.L).(f2.L)

In the above, . is application, @ is capturing (so f3 is another name for (Bool -> Bool -> Bool)). Many thanks.

Edit: I know this is not the most optimal or reusable code, and I know turning this into point-free makes it worse in terms of readability etc. To clarify, I am asking how I can turn it into point-free because I want to learn more about haskell and composition.

Edit2: A really good SO answer on point-free

4
haskelllambdafunction-compositionpointfree
Your withinBounds is not composable, it is better to write the check for a single element and then call all on that. In fact, I would probably just inline all withinBounds where withinBounds is for a single element. - Benjamin Gruenbaum
Thanks. Is there a tell-tale sign of the function not being composable? (for example the input being required in multiple places in the body?) - MIJOTHY
@MIJOTHY: usually, if the type is more general, it's likely more reusable, e.g. withinBounds :: Ord e => (e, e) -> e -> Bool; withinBounds (a,b) x = a <= x && x <= b. Now your original function is simply all (withinBounds (0,8)). Furthermore, I can use this as predicate for a filter: filter (withinBounds (4,100)) [1..103]. - Zeta
Yeah I can understand how general = more reusable, but I was wondering if there is a certain way to tell whether a function can be written in point-free (using the composition operator) or not. Perhaps my usage of 'composable' is wrong. So to rephrase the question with the more general version you wrote, could I write withinBounds (a,b) x = a <= x && x <= b in point-free? - MIJOTHY
@MIJOTHY: Oh, sorry, I forgot to tell you. There is the pointfree package on Hackage, lambdabot on #haskell, and pointfree.io. That being said, I usually move parameters around till I end up with a eta-reducible function, e.g. stackoverflow.com/a/36542287/1139697. - Zeta

4 Answers

9
votes

You could use the fact that function is Applicative. and write withinBounds this way:

withinBounds = pure (&&) <*> all (>= 0) <*> all (<= 8)

Or this way:

withinBounds = (&&) <$> all (>= 0) <*> all (<= 8)

You could read about Applicatives here and here

9
votes

There's a class that's basically dedicated for point-free compositions† with multiple “channels”: Arrow. If you're determined to make everything point-free then this is IMO the way to go. The ugly bit about this is that you constantly need to uncurry functions:

import Control.Arrow

withinBounds = all (>=0) &&& all (<=8) >>> uncurry (&&)

How this works is best understood with a diagram:

      all (>=0) ────
       ╱                ╲
──── &&&            >>>  uncurry (&&) ───
       ╲                ╱
      all (<=8) ────

†Arrow works in a generalised setting; not just for Hask-functions but for any suitable category. But it's useful enough to apply it just to functions.

2
votes

Doing an end-run around the whole question, I think I would probably write it this way:

import Data.Ix
withinBounds = all (inRange (0, 8))

Of course, that's punting a bit, since then one would naturally ask how to implement inRange in a pointfree way. If you absolutely couldn't use inRange, then I would implement it inline this way:

withinBounds = all (liftA2 (&&) (>=0) (<=8))

This uses the reader applicative to supply a single argument to two functions. liftA2 is your requested combining function, though with arguments flipped:

requested :: (a -> b) -> (a -> c) -> (b -> c -> d) -> (a -> d)
liftA2    :: (b -> c -> d) -> (a -> b) -> (a -> c) -> (a -> d)
-2
votes

Notice that x<=8 if and only if 8-x>=0, so, using only prelude, we can write

withinBounds :: [Int] -> Bool
withinBounds = all $ (all (>=0)) . (zipWith (+) [0,8]) . (zipWith (*) [1,-1]) . (replicate 2)

Basically I just map x to [x,x] then to [x,8-x] and then I require these two to be >=0 simultaneously.

Of course, as pointed out in the comments, you can also make a,b parameters so as to reuse them later.

Hope this helps.