-
Notifications
You must be signed in to change notification settings - Fork 12
Design Challenge #1
How would we compose a value with itself N times using some operator? E.g. 5 * 5 * 5 (expected output: 125), or 3 + 3 + 3 + 3 + 3 (expected output: 15).
Acceptable solutions: any way of doing it in Qi or any other language [addendum], or a suggestion for a better way to do it than Qi currently supports 😊 [Addendum: Please also include a short summary of how your implementation works -- optional but would be helpful for everyone to understand your approach]
[Posted on Discord on Jun 04 2022]
- Ben Kenobi (Qi)
- Eutro (Haskell, point-free)
- pythongirl (Dyalog APL)
- jimpjorps (Elixir, lazy streams)
- 1e1001 (Racket, tail-recursive)
- a11ce (Racket, using fold)
- 6cdh (Racket, using Church encoding)
- 1e1001 (Qi, Using Feedback - #1)
- 1e1001 (Qi, Using Feedback - #2)
(~> (5) (clos *) (fanout 3) compose apply) ;=> 125
(define (compose-val N f)
(flow (~> (clos f)
(-< (gen N) _) ;; since (fanout N) only works when N is a literal
fanout compose apply)))
((compose-val 3 *) 5) ;=> 125
Perhaps a nicer "shape" is
(define (compose-val N)
(flow (~> (-< (gen N) _)
fanout compose apply)))
((compose-val 3) (flow (* 5)))
The idea is to fanout a series of closures and compose them. It’s almost the same as folding compose over a list, or applying compose to the list, where the list is made of something like “repeat f”. The nice thing about Qi’s values and Racket’s compose is that they are all variadic, so compose composes variadic functions :). The solution should work as long as the function consumes as many values as it returns.
Update (July 2022): This solution can now be expressed as:
(define (compose-val N f)
(flow (~> (clos f)
(fanout N)
compose apply)))
f = (. replicate) . (.) . foldr1
f (*) 3 5 -- => 125
f (+) 5 3 -- => 15
How it works:
This is the point-free version of
\ op n x = foldr1 op (replicate n x)
which creates a list of n xs, then folds over them with op.
rep←{αα/αρω}
3 ×rep 5 ⍝ => 125
5 +rep 3 ⍝ => 15
Breaking down the APL:
rep←{αα/αρω} creates a operator and assigns it to the name rep. The curly brackets make a function with the variables α for left operand and ω for right operand
α ρ ω creates an array using the length from the left operand (α variable) and fills it with the right operand (ω variable) using the reshape function (ρ)
αα/ folds (/) over the array using a function provided to the left of the operator (the αα variable)
3 ×rep 5 equivalent to 5 × 5 × 5
5 +rep 3 equivalent to 3 + 3 + 3 + 3 + 3
[Additional clarification: In general,] α is for left operand and ω is for right operand and αα is for left operator operand.
defmodule Function do
def rep(f, times, start) do
Stream.iterate(start, &(f.(&1, start))) |> Enum.at(times - 1)
end
end
This makes a lazy stream that repeatedly applies f to the current accumulator and the initial value, then since if there are n elements to compose over, f is applied n-1 times, takes the n-1th element.
[Invoking it:]
Function.rep(&Kernel.*/2, 3, 5)
# = 3 * 3 * 3 * 3 * 3
Function.rep(&Kernel.+/2, 5, 3)
# = 5 + 5 + 5
where &Kernel.*/2 means "the function named * in module Kernel with arity 2", since in Elixir you can have multiple functions with the same name but different arities.
Basic tail-recursive racket version.
{define (recurse proc value count)
{define (inner count total)
(if (= count 1)
total
(inner (sub1 count) (proc value total)))}
(inner count value)}
Fold-y racket version.
(define (n-compose op val iters)
(for/fold ([acc val])
([_ (in-range (sub1 iters))])
(op acc val)))
Racket version using church encoding.
(define (rep op times val)
(((number->church (sub1 times))
(curry op val))
val))
(define (number->church x)
(define church-zero (λ (f) (λ (x) x)))
(define (church-add1 v)
(λ (f) (λ (x) (f ((v f) x)))))
(if (= x 0) church-zero
(church-add1 (number->church (- x 1)))))
{define-flow recurse
(~>
(-< (== _ _ sub1) 2>)
(feedback (while (~> 3> (> 0)))
(-< (~> (select 1 2 3)
(== _ _ sub1))
(~> (select 1 2 4)
(apply _ _ _ (list))))))}
It'd definitely be nice if you could use a flow for the N in feedback. I feel like some form of variable naming could also be nice but that probably goes against the spirit of Qi.
With the feedback I end up doing nothing to 1> and 2>, so I feel like having some way of passing those around without having to loop them would make the code structure a lot nicer.
Update (July 2022): This solution can now be expressed as:
(define-flow recurse
(~> (group 1 _ (~> X clos))
feedback))
(recurse 3 5 *)
{define (recurse proc value count)
(~> (value) (feedback (sub1 count) (proc value)))}
Update (July 2022): A minor simplification:
{define (recurse proc value count)
(~> () (feedback count (proc value)))}
Home | Developer's Guide | Calendar | Events | Projects | Meeting Notes