Haskell's and Scala's standard libraries have an
unfold function that builds a list from an initial state
s and a function
f. This is done with the following steps (explained in an imperative way to be simpler):
- If the result
- is empty, we're done building the list!
- Otherwise, the result should contain the next state
tand the next element
eof the list.
eto the list
tand go back to step 1
Here, we will only be considering lists made of integers.
s will be an integer,
f will take an integer as input, and the result of your
unfold function will be a list of integers. The output of
f will either be
- A fixed value representing that the list has ended
- A class of values (distinct from the fixed value above) that hold an integer representing the next state and an integer representing the next element.
Let's take the example of converting a number to base 5. The initial state would be the number to convert. The output would be a list of the digits in base 5, but reversed. The function would look something like this:
function f(s) if s equals 0 return null else digit = s mod 5 nextState = s ÷ 5 (÷ is integer division here) return [nextState, digit]
Using this function and an example initial state of 137, we go through the following steps:
s = 137and the result is
digit = 2,
nextState = 27. The result is now the list
digit = 2,
nextState = 5. The result is now the list
digit = 0,
nextState = 1. The result is now the list
[2, 2, 0]and
digit = 1,
nextState = 0. The result is now the list
[2, 2, 0, 1]and
sis 0, we return the list
[2, 2, 0, 1]
[1, 0, 2, 2] or
1022, which, in base 5, equals 137. Note that this algorithm does not work with 0 or negative integers.
Here is an implementation in Scala.
As a test case, your
unfold function should be able to convert positive integers from a base 10 to another base (as a reversed list of digits).