3

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.

1 Answer 1

5

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'
5
  • The question actually asked about <$>, not <*>. Sep 13 at 13:47
  • 1
    @leftaroundabout Okay. <$> is not enough. But I interpreted the question as whether point-free was always possible, not whether <$> was the only thing needed for that. Sep 13 at 14:04
  • This is so impressive! It definitely ends up being more complicated than I anticipated, but I wonder if you could convert <$> to SKI and then look through that long doThing expression you generated to see if it could replace any parts of it, then replace with the <$>. Or any other operator for that matter, as a means to simplify the big expression. Thank you for the algorithm, I tried it out manually and it helped me get an idea for how the variables are eliminated. Sep 13 at 18:00
  • 1
    @FuzzyCat444 Yes, there are algorithms that produce much svelter point-free-ifications. They are harder to understand, but I'm sure you can find info about them if you Google around a bit. Sep 13 at 18:42
  • 1
    @FuzzyCat444 For example, here is the collection of rewrite rules that lambdabot's point-free plugin uses to reduce the size of its results. Sep 13 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.