![](/img-import/2018/05/haskell-pointfree-slice-825x350.png)
Making "Slice" Pointfree
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]
[2,3,4]
Prelude> slice 2 10 [0..9]
[2,3,4,5,6,7,8,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)$.
$$
\begin{align}
\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:
$$
\begin{align}
\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}&\\
\end{align}
$$
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)
\end{align}
$$
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