(->) instance for ArrowApply and laziness
Hi all, Could someone help me understand how the (->) instance for ArrowApply works? It looks like this:
instance ArrowLoop (->) where loop f b = let (c,d) = f (b,d) in c
This models recursion for arrows and I need help understanding how it does that. I have a strong feeling it has to do with the magic value 'd'. I've read the Patterson tutorial but I still don't grok it. Thanks! -deech
On Thu, 2010-04-01 at 09:32 -0500, aditya siram wrote:
Hi all, Could someone help me understand how the (->) instance for ArrowApply works? It looks like this:
instance ArrowLoop (->) where loop f b = let (c,d) = f (b,d) in c
This models recursion for arrows and I need help understanding how it does that. I have a strong feeling it has to do with the magic value 'd'. I've read the Patterson tutorial but I still don't grok it.
Thanks! -deech
f may be not strict in d (i.e. it may not require evaluate d to calculate result). For example if you want to create graph with cycle you can write: date Node a = Node a [Node] myGraph x = let n = Node x [n] in n Which is roughly equivalent to imperative: Node n = new Node(); n.addEdgeTo(n); return n; It is valid as constructors are not (usually) strict in arguments. Similarly you can write it as: myGraph = loop ((id &&& (:[])) <<< uncurry Node) or: myGraph = proc (x) -> do rec n <- uncurry Node -< (n, [n]) returnA -< n Usually I find let in more useful then (m)fix/loop but if code generalise for other monads/arrows this instance is needed. Regards
aditya siram wrote:
Hi all, Could someone help me understand how the (->) instance for ArrowApply works? It looks like this:
instance ArrowLoop (->) where loop f b = let (c,d) = f (b,d) in c
This models recursion for arrows and I need help understanding how it does that. I have a strong feeling it has to do with the magic value 'd'. I've read the Patterson tutorial but I still don't grok it.
It's similar to how fix works: http://en.wikibooks.org/wiki/Haskell/Fix_and_recursion Here various definitions of the factorial as example: 1) Definition factorial n = product [1..n] 2) Recursive definition factorial 0 = 1 factorial n = n * factorial (n-1) 3) Recursion with the fixed point combinator fix fix f = let knot = f knot in knot factorial = fix fac where fac f 0 = 1 fac f n = n * f (n-1) 4) Recursion with loop factorial = loop helper where fac f 0 = 1 fac f n = n * f (n-1) helper (n,knot) = (knot n, fac knot) Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com
Thank you. This was incredibly helpful.
-deech
On 4/2/10, Heinrich Apfelmus
aditya siram wrote:
Hi all, Could someone help me understand how the (->) instance for ArrowApply works? It looks like this:
instance ArrowLoop (->) where loop f b = let (c,d) = f (b,d) in c
This models recursion for arrows and I need help understanding how it does that. I have a strong feeling it has to do with the magic value 'd'. I've read the Patterson tutorial but I still don't grok it.
It's similar to how fix works:
http://en.wikibooks.org/wiki/Haskell/Fix_and_recursion
Here various definitions of the factorial as example:
1) Definition
factorial n = product [1..n]
2) Recursive definition
factorial 0 = 1 factorial n = n * factorial (n-1)
3) Recursion with the fixed point combinator fix
fix f = let knot = f knot in knot
factorial = fix fac where fac f 0 = 1 fac f n = n * f (n-1)
4) Recursion with loop
factorial = loop helper where fac f 0 = 1 fac f n = n * f (n-1)
helper (n,knot) = (knot n, fac knot)
Regards, Heinrich Apfelmus
-- http://apfelmus.nfshost.com
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
aditya siram wrote:
Heinrich Apfelmus wrote:
It's similar to how fix works:
http://en.wikibooks.org/wiki/Haskell/Fix_and_recursion
Here various definitions of the factorial as example:
Thank you. This was incredibly helpful. -deech
Anytime. :) There's also a humorous but enlightening list of increasingly complex implementations of the factorial function: The Evolution of a Haskell Programmer. http://www.willamette.edu/~fruehr/haskell/evolution.html The version with fix corresponds to the "Boy Scout Haskell programmer". Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com
participants (3)
-
aditya siram -
Heinrich Apfelmus -
Maciej Piechotka