Swapping a semaphore
In fact, we can do it following two possible patterns:
- [1,2,3,4,..] becomes [1,3,5,7...]
- [1,2,3,4,..] becomes [2,4,6,8...]
Both do the same, but they "begin the counting" the opposite way. Let us implement both of them with the same function! Of course, this function must be parametrized according to the "pattern". Two possible patterns exist, thus, we need a boolean for type for parametrization. Implementation: let us use a boolean parameter as a "flag", "semaphore":
module Alternation where
every_second :: [a] -> [a]
every_second = every_second_at False
every_second_at :: Bool -> [a] -> [a]
every_second_at _ [] = []
every_second_at True (x : xs) = x : every_second_at False xs
every_second_at False (x : xs) = every_second_at True xs
We have used an auxiliary function, bookkeeping the "flag/semaphore": it is swapping it accordingly. In fact, this auxiliary function can be regarded as a generalization of the original task. I think, that is what is called a "worker wrapper" function.
Countdown with an index
The task can be generalized even further. Why not to write a much more general function, which can be parametrized by a "modulus" m, and it "harvests" all mth elems of a list?
- every_mth 1 [1,2,3,4,...] yields [1,2,3,4...]
- every_mth 2 [1,2,3,4,...] yields [1,3,5...]
- every_mth 3 [1,2,3,4,...] yields [1,4,7...]
We can use the same ideas as before, just we have to use more complicated a "semaphore": a natural number instead of a boolean. This is a "countdown" parameter, an index i bookkeeping when it is our turn:
module Cycle where
import Nat (Nat)
every_mth :: Nat -> [a] -> [a]
every_mth 0 = undefined
every_mth m @ (i + 1) = every_mth_at m i
We use an auxiliary function (worker wrapper), bookkeeping the countdown index i:
every_mth_at :: Nat -> Nat -> [a] -> [a]
every_mth_at _ _ [] = []
every_mth_at m 0 (x : xs) = x : every_mth m xs
every_nth_at m (i + 1) (x : xs) = every_mth_at m i xs
For simplicity's sake, natural number type is "implemented" here as a mere alias:
module Nat (Nat) where
type Nat = Integer
Maybe, in a number theoretic sense, there are also cleaner alternative approaches, not exactly equivalent to the task You specified, but adjusting seems to be straightforward:
- let
every_mth 1 [0,1,2,3,4,...]
yield [0,1,2,3,4,...]
- let
every_mth 2 [0,1,2,3,4,...]
yield [0,2,4,6,8...]
- let
every_mth 3 [0,1,2,3,4,...]
yield [0,3,6,9...]
thus, it is specified here so that it should provide "incidentally" the list of multiples of the parameter, when applied to the lazy list of all natural numbers.
In its implementation, it is worth using numbers as a "zero-based" index. Instead of "every mth", we say: "use i as an index ranging 0, 1, ..., u = m-1, where u denotes the upper limit of the possible indices. This upper index can be a useful parameter in the auxiliary function, which counts down the index.
module Multiple where
import Nat (Nat)
every_mth :: Nat -> [a] -> [a]
every_mth 0 = undefined
every_mth (u + 1) = countdown u
countdown :: Nat -> [a] -> [a]
countdown = countdown_at 0
countdown_at :: Nat -> Nat -> [a] -> [a]
countdown_at _ _ [] = []
countdown_at 0 u (x : xs) = x : countdown_at u u xs
countdown_at (i + 1) u (x : xs) = countdown_at i u xs