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 compositiong\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
(53 Posts)
Software developer at SAP and Denk Development, student of Applied Computer Science at Baden-Württemberg Cooperative State University. Interested in programming, math, microcontrollers, and sports.
View all author’s posts