Unfold a list using a function

Question

Task

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):

1. Apply f to s.
2. If the result
   • is empty, we're done building the list!
   • Otherwise, the result should contain the next state t and the next element e of the list.
     1. Add e to the list
     2. Set s to t and 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.

Example

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 = 137 and the result is []
• digit = 2, nextState = 27. The result is now the list [2] and s is 27.
• digit = 2, nextState = 5. The result is now the list [2, 2] and s is 5.
• digit = 0, nextState = 1. The result is now the list [2, 2, 0] and s is 1.
• digit = 1, nextState = 0. The result is now the list [2, 2, 0, 1] and s is 0.
• Since s is 0, we return the list [2, 2, 0, 1]

Reversed, that's [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).

Answer 1

Factor, ³⁷ 36 bytes

[ collector [ follow ] dip 1 head* ]

Try it online!

-1 byte thanks to @chunes

Takes initial-value and quotation on the stack, and returns a vector. The input quotation should return next-state next-value on the stack, or f f to terminate.

some-quot collector [ high-order-func ] dip is a pattern to snatch the top of the stack of every call of some-quot into a vector. Unfortunately, it collects the top of the stack before follow can detect that the loop has ended, so the resulting vector has a dummy element at the end. 1 head* removes it.

Answer 2

APL (Dyalog Unicode), 32 29 bytes

Full program, prompting for s and then for f.

¯1↓r⊣⎕{1↓r,∘⊃←⍺⍺⍵}⍣{⍬≡⍺}⎕⊣r←⍬

Try it online!

r←⍬ initialise the result variable to the empty list

⎕⊣ dismiss that in favour of s from stdin

⎕{…}⍣{⍬≡⍺} get f from std and use it as follows until the result is the empty list:

 ⍺⍺⍵ apply f to the current s (returning [e,t] or [])

 r,∘⊃← extend r with the first value from that (e or 0)

 1↓ drop the first value from that (leaving [t] or [])

r⊣ discard that (i.e. the last computed value, i.e. []) in favour of r

¯1↓ drop the last value (0)

Answer 3

K (ngn/k), 22 bytes

{-1_1_*'|'{x}(y@*:)\x}

Try it online!

call with f[n,s].

s should return an array (nextState;digit) and return a falsy value when it's supposed to end.

I can remove {x} but that would make the function stop on a repeated state. Although that is unlikely, it doesn't seem right to reject that.

Explanation

{-1_1_*'|'{x}(y@*:)\x}
                   \x
                       iterate on first arg, producing array
             (y@*:)    apply second arg(function) to the first elem of the iteration
          {x}          stop if the iteration is falsy
        |'             reverse each array
      *'               take first element of each
 -1_1_                 remove first and last element

Answer 4

Wolfram Language (Mathematica), 26 bytes

f=#@#2/.{a_,b_}:>b<>#~f~a&

Try it online!

Input [f, s]. Returns a StringJoin of elements. Expects an empty list to indicate the list has ended.

To output a list, +6 bytes:

f=#@#2/.{a_,b_}:>{b,##&@@#~f~a}&

Try it online!

Answer 5

J, 27 bytes

1 :'[:(#~2|i.@#)(,u@{:)^:_'

Try it online!

This is J adverb, which modifies a verb returning (new element, new state) to create the required unfold verb.

• (,u@{:)^:_ Keep appending unfold's results until a fixed point, re-applying the verb to the last element on every iteration.
• [:(#~2|i.@#) Keep only odd indexed elements, ie, the elements only, and discard the states and the starting value.

Answer 6

tinylisp, 46 bytes

(d U(q((S F)(i(F S)(c(h(t(F S)))(U(h(F S))F))(

Try it online!

Ungolfed

Implements the spec directly:

(load library)

(def unfold
  (lambda (val func)
    (if (func val)
      (cons
        (head (tail (func val)))
        (unfold (head (func val)) func))
      nil)))

This approach is pretty inelegant: it's not tail-recursive, and it calls the function three times at each step. If I were going to implement unfold for the standard library, it would look more like this (using a helper function _unfold):

(def _unfold
  (lambda (func return-val accum)
    (if return-val
      (_unfold func
        (func (head return-val))
        (cons (head (tail return-val)) accum))
      (reverse accum))))

(def unfold
  (lambda (func val)
    (_unfold func (func val) nil)))

Answer 7

JavaScript, 37 bytes

f=>g=s=>(a=f(s))?[a[1],...g(a[0])]:[]

Try it online!

((state: T) => [next_state: T, val: S]?) => (state: T) => S[]

Answer 8

Jelly, 7 bytes

Ṫv@¥ƬFḊ

Try it online!

A dyadic link taking the start value as its left argument and the Jelly code for the relevant function to unfold as its right. It expects the return value of this link to be an empty list if we’re done, otherwise a list of [next value for result, next value for function]. Returns a list of integers.

Answer 9

Haskell, 22 bytes

f#x=do(s,v)<-f x;v:f#s

Try it online!

Function is expected to return a list [(state, value)] or an empty list. (Footer converts from the conventional/expected use of Maybe.)

f#x=                      Define a function (#) on arguments f and x, returning
    do     <-f x;         the concatenation for each element of f called on x
      (s,v)               providing the new state and value
                 v:       of the value prepended to
                   f#s    (f#) called on the new state.

Was this before I remembered MonadFail is a thing (never mind I'm not even using it anymore):

Haskell, 26 bytes

f#x|s:v<-f x=v++f#s|1>0=[]

Try it online!

Function is expected to return a list [state, value] or an empty list.

Answer 10

PowerShell Core, 36 bytes

for($k,$a=$args;$a){$a,$u=&$k $a;$u}

Try it online!

Takes two parameters, a function $k and the initial value $a

-1 byte thanks to mazzy!

Answer 11

Perl 5, 45 bytes

sub u{@f=$_[1]->(@_);@f?(pop@f,u(@f,pop)):()}

Try it online!

Answer 12

Python 3.8 (pre-release), 42 bytes

u=lambda f,x:(r:=f(x))and[r[1],*u(f,r[0])]

Try it online!

-1 byte thanks to Noodle9
-4 bytes thanks to Shaggy

Assumes falsy output for the end case and a pair otherwise (any subscriptable value with at least two elements). Since a list of falsy values is still truthy, this works perfectly fine.

Answer 13

Racket, #lang racket, 57 bytes

(define(u s f)(match(f s)[`(,z,x)(cons x(u z f))][_'()]))

Try it online!

The function f can return anything other than a list of two values to indicate stop.

---

Not the most interesting racket solution: no tail-call recursion, so is bounded by memory usage. It would be more fun (and not difficult) to write a #lang that supplies unfold as part of its runtime—then there would be a 0-byte solution :)

We (unexpectedly?) save a few bytes by eliminating spaces between ,z,x and _'() in match clauses. I expected each to coalesce into a single identifier, but (un)quoting took precedence. The remaining whitespace (6 spaces, by my count) is required.

Answer 14

R, 43 42 bytes

u=function(s,l=f(s))if(1/l)c(l[2],u(l[1]))

Try it online!

Recursive function using helper function f to to the unfolding.

f must output the fixed non-integer value Inf to represent that the list has ended (a more natural value in R would be NULL or NA, but the functions is.null() and is.na() are each much less golfy than the simple test 1/x [truthy for all integers, falsy only for Inf])