I've never actually used ArrowLoop before, loop is pretty cool.
Here is a factorial implemented using loop:
fact :: Integer -> Integer
fact =
loop $ \(n, f) ->
( f n 1
, \i acc ->
if i > 0
then f (i - 1) (i * acc)
else acc)
Let's give it a try:
λ> fact <$> [1..11]
[1,2,6,24,120,720,5040,40320,362880,3628800,39916800]
I don't know if I can answer the first question you have, but for the 3rd one it's obviously possible. For the concepts that could help you, I think the fix point is the one you are looking for. For example you can start by trying this ;)
λ> import Data.Function
λ> fix error
Once you press enough Ctrl+C you can write factorial using fix point:
λ> let fact = fix $ \ f i -> if i > 1 then i * f (i - 1) else i
λ> fact <$> [1..11]
[1,2,6,24,120,720,5040,40320,362880,3628800,39916800]
Edit
It seems like a bit of expansion on the answer could be helpful.
First of all let's look at an alternative and better (due to tail recursion) implementation of fact using fix, so we can see how it compares with our implementation using loop:
factFix :: Integer -> Integer
factFix n =
fix
(\f ->
\i acc ->
if i > 0
then f (i - 1) (i * acc)
else acc)
n
1
We can see it is not far off. In both cases we get f as an argument and we return back a function that uses that f, in fact, the returned non-recursive function is identical in both cases. Just for clarity let's extract it an reuse in both places:
factNoRec :: (Ord p, Num p) => (p -> p -> p) -> p -> p -> p
factNoRec f i acc =
if i > 0
then f (i - 1) (i * acc)
else acc
factLoop :: Integer -> Integer
factLoop n = loop (\(k, f) -> (f k 1, factNoRec f)) n
factFix :: Integer -> Integer
factFix n = fix (\f -> factNoRec f) n 1
Hopefully now it is much more apparent that they are really related concepts.
Looking into implementations of fix and loop (at least for functions, cause there are also mfix and loop for Kleisli) provides even more insight into their relation:
λ> fix f = let x = f x in x
λ> loop f b = let (c,d) = f (b,d) in c
They are really close to each other.
How about type signatures:
λ> :t fix
fix :: (t -> t) -> t
λ> :t loop
loop :: ((b, d) -> (c, d)) -> b -> c
Those look different. But if you do a bit of unification in the fact case you'll see that fix and loop acquire types:
λ> :t fix :: ((a -> b -> c) -> (a -> b -> c)) -> a -> b -> c
λ> :t loop :: ((b, a -> b -> c) -> (c, a -> b -> c)) -> b -> c
All of a b and c become all Integer in the end, but looking at type variables instead gives a better insight into what's going on. And really what's going on is just recursion by the means of fixed point combinators.
dcan be a function type – Barogramidas the terminating value, yet, the problem with accumulation still holds. Or did you mean something else by that? – VashtivashtiaArrowCircuitandnewtype SF a b = SF { runSF :: [a] -> [b] }from “Programming with Arrows”, this could be written asfact = last . runSF factA . enumFromTo 1 . succ where factA = proc x -> do { rec { acc <- delay 1 -< x * acc }; returnA -< acc }, which I’m pretty sure does essentially the same thing asfact = product . enumFromTo 1but with a bit more allocation. – CalabriaArrow.loopunderliesrec, it means, it should be possible indeed. Now we simply need to rewrite the recursive notation, usingArrow.loop. – Vashtivashtiafix? BTW this can be done using justArrowLoop, we don't actually require anything likedelay. – Barogramfact = fix $ \ f n -> if n > 1 then n * f (n - 1) else 1, as far as I can tell. I should’ve thought about it, right. – Vashtivashtiafact = fix (\ f acc i -> if i > 1 then f (i*acc) (i-1) else acc) 1. – Apollus