{"id":35,"date":"2007-06-14T10:21:06","date_gmt":"2007-06-14T18:21:06","guid":{"rendered":"http:\/\/evanlenz.net\/blog\/2007\/06\/14\/generalizing-recursion-on-integers\/"},"modified":"2007-06-14T10:21:51","modified_gmt":"2007-06-14T18:21:51","slug":"generalizing-recursion-on-integers","status":"publish","type":"post","link":"https:\/\/evanlenz.net\/blog\/2007\/06\/14\/generalizing-recursion-on-integers\/","title":{"rendered":"Generalizing recursion on integers"},"content":{"rendered":"

I thought I’d post a brief answer to the question I raised in my last post, which was “is there an analogous higher-order function [like foldr<\/em>] for recursion on numbers?”<\/p>\n

As I pointed out, you can define product<\/em> using foldr, like this:<\/p>\n

product = foldr (*) 1<\/pre>\n
What I wanted is another function, say foldrNum<\/em>, that would allow me to define factorial<\/em> using the same idea:<\/p>\n
factorial = foldrNum (*) 1<\/pre>\n
As it turns out, all I need to do is make some slight modifications to the foldr definition, which looks like this:<\/p>\n
foldr            :: (a -> b -> b) -> b -> [a] -> b\r\nfoldr op v []     = v\r\nfoldr op v (x:xs) = op x (foldr op v xs)<\/pre>\n
I’ll keep foldrNum general enough so that, like foldr, it can return a value of any type (b<\/code>), but unlike foldr, which can process a list of any type (a<\/code>), I think it’s essential to the idea of foldrNum that it only operate on a non-negative integer, which is what the recursion is based on. First, I’ll show the definition of foldrNum I came up with. Then I’ll compare it line-by-line with foldr so that we can see exactly what’s the same and what’s different.<\/p>\n
Here’s foldrNum:<\/p>\n
foldrNum           :: (Int -> b -> b) -> b -> Int -> b\r\nfoldrNum op v 0     = v\r\nfoldrNum op v (n+1) = op (n+1) (foldrNum op v n)<\/pre>\n
The similarities are obvious, but I like to make things as obvious as possible. First, the types of each function:<\/p>\n
foldr               :: (a<\/strong>   -> b -> b) -> b -> [a]<\/strong> -> b\r\nfoldrNum            :: (Int<\/strong> -> b -> b) -> b -> Int<\/strong> -> b<\/pre>\n
Now, the base case:<\/p>\n
foldr    op v []<\/strong>     = v\r\nfoldrNum op v 0<\/strong>      = v<\/pre>\n
Finally, the recursive case:<\/p>\n
foldr    op v (x:xs)<\/strong> = op x<\/strong>     (foldr    op v xs<\/strong>)\r\nfoldrNum op v (n+1)<\/strong>  = op (n+1)<\/strong> (foldrNum op v n<\/strong>)<\/pre>\n
The natural question arising from this is “How do I generalize foldr and foldrNum, since they’re so much alike?” Joshua Ball anticipated that question in his comment on my last post<\/a>, although I confess I haven’t fully wrapped my head around his solution yet.<\/p>\n
I think this is enough for today. So many possible directions to go in. I must content myself with one small piece at a time. \ud83d\ude42<\/p>\n","protected":false},"excerpt":{"rendered":"
I thought I’d post a brief answer to the question I raised in my last post, which was “is there an analogous higher-order function [like foldr] for recursion on numbers?” As I pointed out, you can define product using foldr, like this: product = foldr (*) 1 What I wanted is another function, say foldrNum, […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[9],"tags":[],"_links":{"self":[{"href":"https:\/\/evanlenz.net\/blog\/wp-json\/wp\/v2\/posts\/35"}],"collection":[{"href":"https:\/\/evanlenz.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/evanlenz.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/evanlenz.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/evanlenz.net\/blog\/wp-json\/wp\/v2\/comments?post=35"}],"version-history":[{"count":0,"href":"https:\/\/evanlenz.net\/blog\/wp-json\/wp\/v2\/posts\/35\/revisions"}],"wp:attachment":[{"href":"https:\/\/evanlenz.net\/blog\/wp-json\/wp\/v2\/media?parent=35"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/evanlenz.net\/blog\/wp-json\/wp\/v2\/categories?post=35"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/evanlenz.net\/blog\/wp-json\/wp\/v2\/tags?post=35"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}