haskellfunctorapplicative# Can we always use <$> in Haskell to define functions "point free"?

I have been learning just how powerful the `<$>`

and `<*>`

operators are in Haskell, and how it is possible to define some functions without parameters where they would normally be needed. I followed these steps to change my `doThing`

function and gradually remove its three parameters:

```
1) doThing x y z = (x + y) * z
2) doThing x y = ((x + y) *)
3) doThing x = (*) <$> (x +)
4) doThing = ((*) <$>) <$> (+)
```

All of these functions take three numbers `x`

, `y`

, and `z`

, and compute `(x + y) * z`

. I know it's not pretty nor a good programming practice in a practical sense, but I still wonder whether it's possible that *any* mathematical expression with N variables can be described as a function without explicitly naming those N variables. I have tried more complicated expressions without much success; even the 4th step above is hard for me to wrap my head around.

Solution

Yes, it is always possible. Here's one particularly simple algorithm:

```
[[\x -> x]] ~> id
[[\x -> e]] ~> const e -- when x does not appear in e
[[\x -> e1 e2]] ~> [[\x -> e1]] <*> [[\x -> e2]]
```

For example, here's how that might look for eliminating `z`

from your expression.

```
\x y -> [[\z -> (x + y) * z]]
~> \x y -> [[\z -> (*) (x + y)]] <*> [[\z -> z]]
~> \x y -> const ((*) (x + y)) <*> id
```

We can then go again, this time eliminating `y`

.

```
\x -> [[\y -> const ((*) (x + y)) <*> id]]
~> \x -> [[\y -> (<*>) (const ((*) (x + y)))]] <*> [[\y -> id]]
~> \x -> ([[\y -> (<*>)]] <*> [[\y -> const ((*) (x + y))]] ) <*> const id
~> \x -> (const (<*>) <*> ([[\y -> const]] <*> [[\y -> (*) (x + y)]] )) <*> const id
~> \x -> (const (<*>) <*> (const const <*> ([[\y -> (*)]] <*> [[\y -> x + y]] ))) <*> const id
~> \x -> (const (<*>) <*> (const const <*> (const (*) <*> ([[\y -> (+) x]] <*> [[\y -> y]])))) <*> const id
~> \x -> (const (<*>) <*> (const const <*> (const (*) <*> (const ((+) x) <*> id )))) <*> const id
```

We could go again, to eliminate `x`

, but this is already messy enough. The point is that this can all be done purely mechanically, without requiring insight from the person (or machine) doing the point free translation.

For fun, here's the final form if you follow this algorithm:

```
const (<*>) <*> (const ((<*>) (const (<*>))) <*> (const ((<*>) (const const)) <*> (const ((<*>) (const (*))) <*> (const (<*>) <*> (const const <*> (const (+) <*> id)) <*> const id)))) <*> const (const id)
```

It's obvious that this algorithm is geared towards simplicity over readability of the result!

Full listing for the code to generate that answer:

```
{-# LANGUAGE LambdaCase #-}
type Var = String
data Term
= S | K | I
| Variable Var
| Lambda Var Term
| App Term Term
deriving (Eq, Ord, Read, Show)
free :: Var -> Term -> Bool
free v = \case
Variable v' -> v == v'
Lambda v' t -> v /= v' && free v t
App t t' -> free v t || free v t'
_ -> False
translate :: Term -> Term
translate = \case
Lambda v t -> case t of
_ | not (free v t) -> App K t
Variable{} -> I
App e1 e2 -> App (App S (translate (Lambda v e1))) (translate (Lambda v e2))
Lambda{} -> translate (Lambda v (translate t))
_ -> error "The impossible happened: variable is not free, but term is not a variable, app, or lambda"
App t t' -> App (translate t) (translate t')
t -> t
doThing :: Term
doThing = Lambda "x" . Lambda "y" . Lambda "z" $
App
(App
(Variable "(*)")
(App
(App (Variable "(+)") (Variable "x"))
(Variable "y")
)
)
(Variable "z")
pp :: Term -> String
pp = \case
S -> "(<*>)"
K -> "const"
I -> "id"
Variable v -> v
Lambda v t -> "\\" ++ v ++ " -> " ++ pp t
App (App S t) t' -> ""
++ case t of
Lambda{} -> "(" ++ pp t ++ ")"
_ -> pp t
++ " <*> "
++ case t' of
App (App S _) _ -> "(" ++ pp t' ++ ")"
_ -> pp t'
App t t' -> ""
++ case t of
Lambda{} -> "(" ++ pp t ++ ")"
_ -> pp t
++ " "
++ case t' of
App{} -> "(" ++ pp t' ++ ")"
_ -> pp t'
```

- Scotty: No instance for MonadIO ScottyT (arising from a use of ‘liftIO’)
- How can I implement a splay tree that performs the zig operation last, not first?
- Lack of Finite Element Method implementations in Haskell - Any specific reasons?
- What is fusion in Haskell?
- General approach for combining multiple foldrs over the accumulator type?
- using Lens for nested folds with a threaded accumulator
- What is the difference between . (dot) and $ (dollar sign)?
- understand haskell logic behind odd's and even's index lists
- Java tagged union / sum types
- Is indentation in Haskell like in Python?
- Unicode console I/O in Haskell on Windows
- Code formatting not working with Pandoc in Haskell
- How can I use `liftIO` with State to print values inside that Monad?
- Module X appears in multiple packages
- High order function returning result and modified itself
- Parsec not parsing newline character
- Enable -Woverflowed-literals for custom numeric types
- How to format UTCTime as ISO 8601 in Haskell
- Haskell Depth-First Graph Traversal has Infinite Loop
- Non-exhaustive patterns in function defined in GHCi
- How to run an individual test with Stack and Haskell Test.Framework?
- Persisting drawn frames in Gloss
- How do I convert from unixtime to a date/time in Haskell?
- Partially processing a conduit using another conduit
- State Monad - HASKELL
- How to load cabal script with import of hidden package in cabal repl?
- Applicative Functor - Haskell
- Haskells bind operator and the >> operator and their relation
- How to use forEach with multiple traversables?
- Telling Haskell compiler that two types are compatible