26

In arrow do notation, you can use the rec keyword to write recursive definitions. So for example:

rec
    name <- function -< input
    input <- otherFunction -< name

How can this ever evaluate? It seems like it would just go into an infinite loop or something. I know it evaluates to the loop arrow combinator, but I don't understand how that works either.

EDIT: that powers example is really helpful. How would you write that with do notation, though? I assume you would need to use rec.

Michael Petrotta
  • 59,888
  • 27
  • 145
  • 179
Jeff Burka
  • 2,571
  • 1
  • 17
  • 30

2 Answers2

28

This bit of magic works due to haskells laziness. As you might know, Haskell evaluates a value when needed, not when defined. Thus, this works if you don't need the value fed in directly, or maybe later.

rec is implemented using the loop function of ArrowLoop. It is defined as followed:

class Arrow a => ArrowLoop a where
        loop :: a (b,d) (c,d) -> a b c

instance ArrowLoop (->) where
        loop f b = let (c,d) = f (b,d) in c

You can see: The output is just fed back as the input. It will be calculated just once, because Haskell will only evaluate d when it's needed.

Here's an actual example of how to use the loop combinator directly. This function calculates all the powers of it's argument:

powers = loop $ \(x,l) -> (l,x:map(*x)l)

(You could also write it like this instead: powers x = fix $ (x :) . map (*x))

How does it works? Well, the infinite list of powers is in the l argument. The evaluation looks like this:

powers = loop $ \(x,l) -> (l,x:map(*x)l) ==>
powers b = let (c,d) = (\(x,l) -> (l,x:map(*x)l)) (b,d) in c ==>
powers b = let (c,d) = (d,b:map(*b)d) in d ==> -- Now  we apply 2 as an argument
powers 2 = let (c,d) = (d,2:map(*2)d) in d ==>
         = let (c,(2:d)) = (d,2:map(*2)d) in c ==>
         = let (c,(2:4:d)) = ((2:d),2:map(*2)(2:d)) in c ==>
         = let (c,(2:4:8:d)) = ((2:4:d),2:map(*2)(2:4:d)) in  ==> -- and so on
fuz
  • 88,405
  • 25
  • 200
  • 352
  • I understand that, but where does it get the first output sample? Is there a base case defined somewhere, because I haven't seen that. If neither input or name are provided in my example, how can that ever evaluate? Or does one of those two have to be provided? – Jeff Burka Mar 23 '11 at 13:58
  • 3
    The trick is, that Haskell won't evaluate unused arguments. It's just that control flow isn't necessary the same as you think. – fuz Mar 23 '11 at 15:20
  • 2
    The 'f (b,_)' must only use the input 'b' when calculating the output 'd'. 'f' may use both 'b' and 'd' when building 'c' so long as it does not force the evaluation of 'd' to cause it to hang. You can think of it like this: when 'c' is forced it causes 'd' to be computed from 'b' and then 'c' to be computed from 'b' and 'd'. – Chris Kuklewicz Mar 23 '11 at 20:50
  • 2
    @Chris Kuklewicz: Not always. Think about a function like this: `f = loop $ \(x,l) -> (l,x:map(*x)l)`. This will evaluate, as you only use the *already defined* elements of `l`. – fuz Mar 23 '11 at 20:58
  • 4
    @JeffBurka I'm not sure this is a great example for do notation, but I think the powers example is approximately equivalent to: `powers = proc x -> do { rec { l <- id -< x:map(*x)l }; returnA -< l }` – Sam Bickley Jun 16 '16 at 03:46
14

Here is a real-ish example:

loop f b = let (c,d) = f (b,d) in c

f (b,d) = (drop (d-2) b, length b)

main = print (loop f "Hello World")

This program outputs "ld". The function 'loop f' takes one input 'b' and creates one output 'c'. What 'f' is doing is studying 'b' to produce 'length b' which is getting returned to loop and bound to 'd'.

In 'loop' this 'd=length b' is fed into the 'f' where it is used in the calculation in drop.

This is useful for tricks like building an immutable doubly linked list (which may also be circular). It is also useful for traversing 'b' once to both produce some analytic 'd' (such as length or biggest element) and to build a new structure 'c' that depends on 'd'. The laziness avoids having to traverse 'b' twice.

Chris Kuklewicz
  • 8,123
  • 22
  • 33