Timo Denk's Blog

Making "Slice" Pointfree

· Timo Denk

Let the Haskell function slice be defined as

slice :: Int -> Int -> [a] -> [a]
slice from len xs = take len (drop from xs)

It takes to integral values, marking the beginning and the length of a sub-list, which is sliced out of the third parameter (a list). Applied to strings, this function may be known as substring. Here are some examples, illustrating what it does:

Prelude> slice 2 3 [0..9]
Prelude> slice 2 10 [0..9]

The goal is, to make slice pointfree, i.e. write it as slice = ..., and thereby illustrate the systematic approach of doing so.

The initial situation is the definition

$$ \begin{align}&\text{slice from len xs} = \text{take len }(\text{drop from xs}).&(1)\end{align} $$

The right-most argument, namely xs must be removed first. In order to do that, the function definition must take a form where xs is at the rightmost position, preceded by a $, since — as can bee seen when looking at the more generalized version $(\text{i})$ — it allows for simplification, i.e. $(\text{i})\Rightarrow(\text{ii})$:

$$ \begin{align}
&&\text{f }\alpha &= F\text{ \$ }\alpha&(\text{i})\\
\Rightarrow&&\text{f } &= F,&(\text{ii}) \end{align} $$

where $\alpha$ is a parameter and $F$ is a function definition for the function f that does not contain $\alpha$.

Bringing $(1)$ into the form $(\text{i})$ can be achieved by explicitly stating the composition $g(h(x))$ that it contains:

$$ \begin{align}
\text{slice from len xs} &
=\underbrace{\text{take len}}_{g}\text{ }(\underbrace{\text{drop from}}_{h}\text{ }\underbrace{\text{xs}}_{x})&\\ &=\underbrace{(\text{take len})}_{g}\text{ . }\underbrace{(\text{drop from})}_{h}\text{ \$ }\underbrace{\text{xs}}_{x}&\\ \text{slice from len}&
=\underbrace{(\text{take len})}_{g}\text{ . }\underbrace{(\text{drop from})}_{h}&\\\\ &=\text{(.) }(\text{take len})\text{ }(\text{drop from})&(2) \end{align} $$

The next parameter which we want to remove is called len. It appears in $(2)$ as an argument to take. Since take len is the first argument to (.), but we need it on the right-most side, we are going to apply flip :: (a -> b -> c) -> b -> a -> c to (.). Afterwards the function composition can be explicitly stated, as we did when transforming from $(1)$ to $(2)$.

\text{slice from len}&=\text{(.) }(\text{take len})\text{ }(\text{drop from})&\\ &=\underbrace{\text{flip (.) }(\text{drop from})}_{g}\text{ }(\underbrace{\text{take}}_{h}\text{ }\underbrace{\text{len}}_{x})&\\
&=\text{(.) }\underbrace{\left(\text{flip (.) }(\text{drop from})\right)}_{g}\text{ }\underbrace{\text{take}}_{h}\text{ \$ }\underbrace{\text{len}}_{x}&\\
\text{slice from}&=\text{(.) }\underbrace{\left(\text{flip (.) }(\text{drop from})\right)}_{g}\text{ }\underbrace{\text{take}}_{h}&(3)
\end{align} $$

Only the parameter from is remaining. First, we move it further to the right:

\text{slice from}&=\text{(.) }\underbrace{\left(\text{flip (.) }(\text{drop from})\right)}_{g}\text{ }\underbrace{\text{take}}_{h}&\\
\text{slice from}&=\text{flip (.) }\underbrace{\text{take}}_{h}\text{ }\underbrace{\left(\text{flip (.) }(\text{drop from})\right)}_{g}&\\

Just to explicitly state the function composition $g\left(h\left(i\left(x\right)\right)\right)$:

\begin{align} \text{slice from}&=\underbrace{\text{flip (.) }\text{take}}_{g}\text{ }\left(\underbrace{\text{flip (.) }}_{h}(\underbrace{\text{drop}}_{i}\text{ }\underbrace{\text{from}}_{x})\right)&\\
&=\underbrace{\text{flip (.) }\text{take}}_{g}\text{ . }\underbrace{\text{flip (.) }}_{h}\text{ . }\underbrace{\text{drop}}_{i}\text{ \$ }\underbrace{\text{from}}_{x}&\\
\text{slice}&=\underbrace{\text{flip (.) }\text{take}}_{g}\text{ . }\underbrace{\text{flip (.) }}_{h}\text{ . }\underbrace{\text{drop}}_{i}&(4)

Here is the pointfree solution $(4)$ in Haskell syntax:

slice' :: Int -> Int -> [a] -> [a]
slice' = flip (.) take . flip (.) . drop

Without a sound strategy (flipping parameters and searching for function compositions) the solution might look more verbose:

slice'' :: Int -> Int -> [a] -> [a]
slice'' = flip $ flip (.) ((.)(.)(.) (flip take) drop) . flip flip