What is the general scheme for writing a function in an unlimited style?

Question

I am currently working on 20 intermediate Haskell exercises , which is a pretty fun exercise. It includes the implementation of various instances of Functor and Monad types (and functions that take Functor and Monad as arguments), but with cute names like Furry and Misty to hide what we are doing (does for some interesting code) .

I am trying to make some of this in a dotless style, and I wondered if there is a general scheme for turning a point (?) Definition into an inline definition. For example, here is a class for Misty :

 class Misty m where unicorn :: a -> ma banana :: (a -> mb) -> ma -> mb 

(the unicorn and banana functions are return and >>= , if this is not obvious), and here is my apple implementation (equivalent to flip ap ):

 apple :: (Misty m) => ma -> m (a -> b) -> mb apple xf = banana (\g -> banana (unicorn . g) x) f 

In the subsequent parts of the exercises, you will implement the versions liftM , liftM2 , etc. Here are my solutions:

 appleTurnover :: (Misty m) => m (a -> b) -> ma -> mb appleTurnover = flip apple banana1 :: (Misty m) => (a -> b) -> ma -> mb banana1 = appleTurnover . unicorn banana2 :: (Misty m) => (a -> b -> c) -> ma -> mb -> mc banana2 f = appleTurnover . banana1 f banana3 :: (Misty m) => (a -> b -> c -> d) -> ma -> mb -> mc -> md banana3 fx = appleTurnover . banana2 fx banana4 :: (Misty m) => (a -> b -> c -> d -> e) -> ma -> mb -> mc -> md -> me banana4 fxy = appleTurnover . banana3 fxy 

Now, banana1 (equivalent to liftM or fmap ), I was able to implement pointfree style with the appropriate appleTurnover definition. But with the other three functions, I had to use parameters.

My question is: is there a recipe for turning such definitions into stringless definitions ?

Answer 1

As demonstrated by pointfree , any such conversion can be done automatically. However, the result is more often confused than improved. If one goal is to increase readability, and not to destroy it, then the first goal should be to determine why the expression has a certain structure, find a suitable abstraction and build things that way.

The simplest structure is simply combining things into a linear conveyor, which is a simple function. This gives us pretty far only in itself, but, as you noticed, it does not process everything.

One generalization is functions with additional arguments, which can be increased gradually. Here is one example: Define onResult = (. (.)) . Now, applying onResult n times to the initial id value, you get the composition of the function with the result of the n-ary function. Thus, we can define comp2 = onResult (.) And then write comp2 not (&&) to define the NAND operation.

Another generalization that covers the foregoing is indeed the definition of operators that apply a function to a component of a larger value. An example here would be first and second in Control.Arrow , which work with 2 tuples. Conal Elliott Semantic Editor Combinators are based on this approach.

The case is slightly different when you have a function with several arguments for some type b and a -> b function, and they need to be combined into a function with several arguments using a . For the general case of 2-ary functions, the Data.Function module provides an on combinator, which you can use to write expressions like compare `on` fst to compare two tuples in your first elements.

This is a more complex problem when one argument is used more than once, but there are significant duplicate patterns that can also be extracted. A special case here is the application of several functions to one argument, and then collecting the results with another function. This happens with the Applicative instance for functions, which allows us to write expressions like (&&) <$> (> 3) <*> (< 9) to check if the number falls into the given range.

It is important if you want to use any of this in real code, you need to think about what the expression means and how it is reflected in the structure. If you do this and then reorganize it into a dissolute style using meaningful combinators, you will often make the code more understandable than otherwise, unlike typical pointfree output.

Answer 2

Yes! One trick is to write your points in prefix notation, not infix. Then you can find new things that look like a composition of functions. Here is an example:

 banana2 f = appleTurnover . banana1 f = (.) appleTurnover (banana1 f) = ((.) appleTurnOver) . banana1 $ f banana2 = (appleTurnover .) . banana1 

The source code for pointfree contains more, but it handles many cases.

 banana4 fxy = appleTurnover . banana3 fxy = (.) appleTurnover ((banana3 fx) y) = ((.) appleTurnover) . (banana3 fx) $ y banana4 fx = ((.) appleTurnover) . (banana3 fx) = (.) ((.) appleTurnover) (banana3 fx) = ((.) ((.) appleTurnover)) ((banana3 f) x) = ((.) ((.) appleTurnover)) . (banana3 f) $ x banana4 f = ((.) ((.) appleTurnover)) . (banana3 f) = (.) ((.) ((.) appleTurnover)) (banana3 f) = ((.) ((.) ((.) appleTurnover))) (banana3 f) = ((.) ((.) ((.) appleTurnover))) . banana3 $ f banana4 = ((.) ((.) ((.) appleTurnover))) . banana3 = (((appleTurnover .) .) .) . banana3 

Answer 3

I use the following term rewrite system:

 \x -> fx ------> ffyx ----------> flip fxy \x -> f (gx) --> f . g 

This is incomplete (read why in books on combinatorial logic), but enough:

Here is a banana2:

 banana2 f = appleTurnover . banana1 f 

Rewrite as lambda:

 banana2 = \f -> appleTurnover . banana1 f 

Write (.) In the prefix style:

 banana2 = \f -> (.) appleTurnover (banana1 f) 

note that

 banana2 = \f -> ((.) appleTurnover) (banana1 f) 

Thus, rule 3 can be applied. f - (.) appleTurnover , and g - banana :

 banana2 = ((.) appleTurnover) . banana1 

Answer 4

There is a pointfree package that takes a Haskell function definition and tries to rewrite it in pointfree style. I would suggest experimenting with him to get new ideas. See this page for details; The package is available here .

Answer 5

Since the pointfree style is a combinator style, just apply the well-known combinator definitions, read them back to make a replacement:

 B fgx = f (gx) -- (.) , <$> for ((->) a) C fxy = fyx -- flip K xy = x -- const I x = x -- id S fgx = fx (gx) -- <*> , ap for ((->) a) W fx = fxx -- join (f >>= g) x = g (fx) x (f =<< g) x = f (gx) x 

At times, liftMx , liftAx , sequence , sequenceA can simplify things. I also consider foldr , unfoldr , iterate , until , etc. As the main combinators.

Often, using operator sections also helps:

 op ab = (a `op` b) = (`op` b) a = (a `op`) b 

Some templates may become familiar and therefore used directly:

 ((f .) . g) xy = f (gxy) ((. f) . g) xy = gx (fy) (((f .) .) . g) xyz = (f .) (gxy) z = f (gxyz) (((. f) .) . g) xyz = (. f) (gxy) z = gxy (fz) 

and etc.