Functional programming recursion schemes

thewarrior · on Nov 3, 2014

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.

tome · on Nov 3, 2014

A strangely glaring error

    prod (x:xs) = x * (sum xs)

agumonkey · on Nov 3, 2014

That's why I wished anaphoric recursion was more used.

    prod (x:xs) = x * (self xs)

tome · on Nov 6, 2014

    prod' self [] = 1
    prod' self (x:xs) = x * self xs

    prod = fix prod'

TuringTest · on Nov 3, 2014

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 · on Nov 3, 2014

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

whitten · on Nov 3, 2014

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 · on Nov 3, 2014

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 · on Nov 3, 2014

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_techni...

tel · on Nov 3, 2014

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