19
\$\begingroup\$

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

\$\endgroup\$

14 Answers 14

6
\$\begingroup\$

Factor, 37 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.

\$\endgroup\$
1
  • \$\begingroup\$ but-last -> 1 head* to save a byte. \$\endgroup\$
    – chunes
    Commented Jul 30, 2021 at 1:36
6
\$\begingroup\$

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)

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
2
  • \$\begingroup\$ What happens if two successive applications give the same result? \$\endgroup\$
    – Adám
    Commented Aug 1, 2021 at 17:53
  • 1
    \$\begingroup\$ @Adám That should be ok because as long as the function is not returning an empty list the list we're "fixed pointing" on will still be growing, and will be different each iteration. \$\endgroup\$
    – Jonah
    Commented Aug 1, 2021 at 18:27
4
\$\begingroup\$

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)))
\$\endgroup\$
3
\$\begingroup\$

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[]

\$\endgroup\$
2
  • \$\begingroup\$ 35 bytes if returning an empty string from g instead of null is allowed. \$\endgroup\$
    – Shaggy
    Commented Jul 30, 2021 at 10:44
  • \$\begingroup\$ @Shaggy I’ll keep it as is, since OP use null in the post. You may save some more bytes like this: f=>g=s=>([a,b]=f(s))&&[b,...g(a)] \$\endgroup\$
    – tsh
    Commented Jul 30, 2021 at 10:52
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ It's smart. Thanks. -1 byte \$\endgroup\$
    – mazzy
    Commented Aug 3, 2021 at 8:10
2
\$\begingroup\$

Perl 5, 45 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ You can save a byte with Python 3.8. \$\endgroup\$
    – Noodle9
    Commented Jul 30, 2021 at 8:42
  • \$\begingroup\$ -4 bytes by returning an empty string from f instead of 0. \$\endgroup\$
    – Shaggy
    Commented Jul 30, 2021 at 10:47
  • \$\begingroup\$ Dunno if there's an equivalent way of doing [a,b]=f(x) in Python but, if so, you may be able to save a bit more. \$\endgroup\$
    – Shaggy
    Commented Jul 30, 2021 at 13:04
  • 1
    \$\begingroup\$ @Shaggy Unfortunately, seems like that doesn't work with := (it works normally with =, so... that's a bit weird). Thanks though \$\endgroup\$
    – hyper-neutrino
    Commented Jul 30, 2021 at 13:40
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Can you name your function u instead of unfold? \$\endgroup\$
    – user
    Commented Jul 31, 2021 at 23:20
  • 1
    \$\begingroup\$ @user facepalm yea, thought that the name unfold was required for some reason… \$\endgroup\$ Commented Jul 31, 2021 at 23:22
1
\$\begingroup\$

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

\$\endgroup\$
6
  • \$\begingroup\$ That's an interesting way to check if the list has ended. What would just if(l) or if(l-1) or something do? \$\endgroup\$
    – user
    Commented Aug 1, 2021 at 15:41
  • \$\begingroup\$ @user - I understood from the question (correct me if I'm wrong) that the output of f should be either two integers, or some other value. So I can't use any value that could be an integer (such as zero, or also FALSE) to indicate that the list has ended (which would enable if(l)), and certainly not a value of 1 (which would enable if(l-1)... \$\endgroup\$ Commented Aug 1, 2021 at 16:20
  • \$\begingroup\$ @user - Unfortunately, if(NULL) and if(NA) both give an error... \$\endgroup\$ Commented Aug 1, 2021 at 16:21
  • 1
    \$\begingroup\$ If you use 0 to indicate that the list has ended and [state, next] or [next, state] to give the next value, that should be alright. \$\endgroup\$
    – user
    Commented Aug 1, 2021 at 16:34
  • 2
    \$\begingroup\$ @user - Thanks for clarifying. I think that would still be longer, but now I've found another 'interesting' way to indicate end-of-list and save a byte... \$\endgroup\$ Commented Aug 1, 2021 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.