Preliminaries:

> module Data.Function.Stack where > import Data.Function > import Control.Monad > import Control.Monad.Instances

Let's pretend that Haskell functions receive their arguments neatly on a stack. Now suppose our arguments were given in the wrong order and we needed to shuffle them around a bit before actually making the function call. In the Haskell world this is equivalent to applying some sort of permuting combinator to the function. Here are some basic stack operations implemented as combinators:

Swap the first two arguments:

> swap :: (a -> b -> rest) -> (b -> a -> rest) > swap = flip

Duplicate the first argument:

> dup :: (a -> a -> rest) -> (a -> rest) > dup = join -- in the (r->) monad, sorry

Apply a literal argument:

> push :: a -> (a -> rest) -> rest > push = flip id

Discard an argument:

> pop :: rest -> (a -> rest) > pop = const

The type signatures can be interpreted as stack effects (which are
used in stack-based languages to describe the stack effects of
functions, or words as they are called) simply by reading them
backwards. The top of a stack is to the left (`a -> b -> rest`

is a
stack with `a`

on top) and the signature `x -> y`

means that the stack
state `y`

is turned into state `x`

.

First example:

```
(\a -> f 3 a a) = dup . push 3 $ f
```

As you can see, the stack combinators are written left-to-right in execution order. Nice.

Some additional combinators:

> dup2 :: (a -> b -> a -> rest) -> (a -> b -> rest) > dup2 f a b = f a b a

> dup3 :: (a -> b -> c -> a -> rest) -> (a -> b -> c -> rest) > dup3 f a b c = f a b c a

> rot :: (b -> c -> a -> rest) -> (a -> b -> c -> rest) > rot = dup3 . pop

> rot' :: (c -> a -> b -> rest) -> (a -> b -> c -> rest) > rot' = rot . rot

And a second example:

```
(\a b c -> f b c a 3) = (push 3) . dup3 . pop . rot $ f
```

Shuffling arguments with just these combinators can be very
laboursome. To facilitate deep transformations we introduce the
meta-combinator `deep`

:

> deep :: (x -> y) -> ((c -> x) -> (c -> y)) > deep = (.)

Which takes a stack combinator and applies it one level down:

```
deep (push True) :: (c -> Bool -> rest) -> c -> rest
```

Now we can rewrite example 2 as:

```
(\a b c -> f b c a 3) = rot . (deep . deep . deep $ push 3) $ f
```

We can also describe complicated function compositions in this language of ours by mapping Haskell functions into "words" that manipulate our ephemeral stack:

> apply :: (a -> b) -> (b -> rest) -> (a -> rest) > apply = flip (.)

> apply2 :: (a -> b -> c) -> (c -> rest) -> (a -> b -> rest) > apply2 f g = (g .) . f

Example:

```
(\a b c -> f a (a+b) (g c)) = dup . deep (apply2 (+) . deep (apply g)) $ f
```

Oh the pointfree fun!

*Thanks to ski on #haskell who gave a link to his earlier work in
the same
vein.*