5 ms·

Functional programming recursion schemes

31 points by llazzaro 12y ago

whitten 12y ago
It's not clear what programming language is being used in this blog entry from April 2014, but it does show a trick or two using a higher level function as input to the foldr recursive function. This feels like it has some examples of how to use it and how NOT to use it, but there is some confusion expressed by the writer as well.
- nrinaudo 12y ago
  It's not stated anywhere, but it's Haskell. Usually a safe bet when presented with a functional programming language that is not lisp-like normuses a c-like syntax.
platz 12y ago
If you really want to go down the rabbit hole on stuff like this, check out bouncy folds https://github.com/quchen/articles/blob/master/useful_techniques.md#bouncy-folds https://github.com/quchen/articles/blob/master/useful_techni...
- tel 12y ago
  Also valuable in this space is writing `foldl` in terms of `foldr` and writing operations on Hughe's lists.
tome 12y ago
A strangely glaring error prod (x:xs) = x * (sum xs)
- agumonkey 12y ago
  That's why I wished anaphoric recursion was more used. prod (x:xs) = x * (self xs)
  - tome 12y ago
    prod' self [] = 1 prod' self (x:xs) = x * self xs prod = fix prod'
TuringTest 12y ago
Maybe my Haskell is a bit rusty, but I don't get the definition of recr. What is 'f' in the following?: recr base combine (x:xs) = f x xs (recr base combine xs)
- hollerith 12y ago
  it is a typo. should be 'combine' (because, the way it is now, the presence of the 'combine' argument serves no purpose).
thewarrior 12y ago
I couldn't understand the authors implementation. I found this in prelude. So much simpler. dropWhile :: (a -> Bool) -> [a] -> [a] dropWhile p [] = [] dropWhile p xs@(x:xs') | p x = dropWhile p xs' | otherwise = xs I feel that dropWhile isn't that kind of operation fold was designed for. EDIT: I was somewhat wrong. After some googling I found this clever implementation : dropWhilePair :: (a -> Bool) -> [a] -> ([a], [a]) dropWhilePair p = foldr f v where f x (ys,xs) = (if p x then ys else x : xs, x : xs) v = ([],[]) But this returns a tuple whose first element is the answer we need.

31 points by llazzaro 12y ago

It's not clear what programming language is being used in this blog entry from April 2014, but it does show a trick or two using a higher level function as input to the foldr recursive function. This feels like it has some examples of how to use it and how NOT to use it, but there is some confusion expressed by the writer as well.

nrinaudo 12y ago
It's not stated anywhere, but it's Haskell. Usually a safe bet when presented with a functional programming language that is not lisp-like normuses a c-like syntax.

platz 12y ago

If you really want to go down the rabbit hole on stuff like this, check out bouncy folds https://github.com/quchen/articles/blob/master/useful_techniques.md#bouncy-folds https://github.com/quchen/articles/blob/master/useful_techni...

tel 12y ago
Also valuable in this space is writing `foldl` in terms of `foldr` and writing operations on Hughe's lists.

tome 12y ago

A strangely glaring error prod (x:xs) = x * (sum xs)

agumonkey 12y ago
That's why I wished anaphoric recursion was more used. prod (x:xs) = x * (self xs)
- tome 12y ago
  prod' self [] = 1 prod' self (x:xs) = x * self xs prod = fix prod'

TuringTest 12y ago

Maybe my Haskell is a bit rusty, but I don't get the definition of recr. What is 'f' in the following?: recr base combine (x:xs) = f x xs (recr base combine xs)

hollerith 12y ago
it is a typo. should be 'combine' (because, the way it is now, the presence of the 'combine' argument serves no purpose).

thewarrior 12y ago

I couldn't understand the authors implementation. I found this in prelude. So much simpler. dropWhile :: (a -> Bool) -> [a] -> [a] dropWhile p [] = [] dropWhile p xs@(x:xs') | p x = dropWhile p xs' | otherwise = xs I feel that dropWhile isn't that kind of operation fold was designed for. EDIT: I was somewhat wrong. After some googling I found this clever implementation : dropWhilePair :: (a -> Bool) -> [a] -> ([a], [a]) dropWhilePair p = foldr f v where f x (ys,xs) = (if p x then ys else x : xs, x : xs) v = ([],[]) But this returns a tuple whose first element is the answer we need.