Talk:Fold (higher-order function)

Rewrite

As partially noted below, the article was rather terrible, containing numerous severe errors. (buggy scheme code, foldl and foldr being confused with respect to lazy evaluation, associativity and commutativity being confused, etc.) I've rewritten it and extended it somewhat. It is mildly Haskell-centric as far as the examples go, but Haskell can very well be treated as functional pseudocode, and very little of the content is really particular to Haskell, but applies to most any language supporting higher-order functions.

-- Cgibbard 02:22, 21 October 2006 (UTC)

Totally AGREE!!!!! But how to prevent that the bot does not revert the changes. It happened to me in other articles with minor changes. Changing everything, I wont do it, it is very annoying to be reverted automatically. — Preceding unsigned comment added by 2806:107E:C:B556:218:DEFF:FE2B:1215 (talk) 08:58, 15 August 2018 (UTC)

foldl and foldr

I see, the paragraph about foldl and foldr has nicely the facts correct and conclusions all wrong, but I don't want to think about the correct examples right now.

Concatenation is not commutative, right, but it still doesn't matter whether foldl or foldr is used, because concatenation is still associative.

Foldr "starts" from the right, right, but that's still the correct fold for infinite lists because the lazy processing starts to produce co-data from the "end" (outer scope). You can try with

foldr (:) [] [1..]
foldr (&&) True ([True,False] ++ repeat True) 

--TuukkaH 01:40, 27 August 2006 (UTC)

other high-order functions ?

Could someone add more HOFs into Wikipedia ? For example, filter is missing - http://en.wiki.x.io/wiki/Talk:Filter_%28software%29 For example, map is missed (mentioned, but not described anyhow) —The preceding unsigned comment was added by 212.176.32.19 (talk) 09:12, 15 May 2007 (UTC).

See Map (higher-order function). — Tobias Bergemann 08:46, 21 May 2007 (UTC)

At this time map was added, here is the other that you asked: filter p = foldr (\x y->if p x then x:y else y) [] — Preceding unsigned comment added by 2806:107E:C:B556:218:DEFF:FE2B:1215 (talk) 08:51, 15 August 2018 (UTC)

Python

Should the article mention that Guido wants to remove reduce[1] from Python with the next great revision or would this be off topic? — Tobias Bergemann 11:46, 30 May 2007 (UTC)

This, of course, isn't the case. As indicated by the Python (3) example, reduce was moved to functools, not removed — Masklinn (talk) 13:15, 9 October 2009 (UTC)

Fold equivalent in Lisp/Scheme?

Is there a built-in function a la fold in Lisp or Scheme? If so, it should be named, of not, that should also be noted. —Preceding unsigned comment added by 172.179.150.144 (talk) 10:09, 30 October 2007 (UTC)

Here is in a Scheme like code:

(define (reduce f e xs)
   (cond ((isCons? xs) (f (car xs) (reduce f e (cdr xs))))
         (#t e) ) )

Data structures other than linkd lists

Shouldn't there be some discussion of how folds apply to other data structures than linked lists (trees, etc)? I don't really know enough to make the edits, but I'm sure I've seen something about folding trees somewhere. 79.72.112.167 (talk) 22:06, 3 February 2008 (UTC)

Just parameterize the constructors of the data type, and replace each constructor by the corresponding parameter.

Well, that does fall under Catamorphism already... 99.247.248.73 (talk) 20:09, 9 August 2008 (UTC)

introduction

can someone rewrite it in the 'plain' language, which would be understandable to non technical people.

moving an example from the beginning 'Folds on lists' to the introduction would be nice.

216.80.119.92 (talk) 01:37, 23 August 2008 (UTC)

Amazon preview and copivio

Foldrn implementation in Folds_for_non-empty_lists can be seen in Amazon's preview of the cited book. Is it enough to allow its inclusion here, or is it still considered copivio? -- WillNess (talk) 16:17, 15 November 2011 (UTC)

I'll assume that it is and will remove the implementation code. WillNess (talk) 10:12, 18 November 2011 (UTC)

Compile time fold expression support for C++ 17

It appears that C++ 17 will add support compile time fold expressions.

Folding proposal: https://isocpp.org/files/papers/n4295.html

Adoption announcement: https://isocpp.org/blog/2014/11/new-papers-adopted-for-cpp17

Example usage: http://baptiste-wicht.com/posts/2015/05/cpp17-fold-expressions.html — Preceding unsigned comment added by 144.15.255.227 (talk) 20:27, 9 November 2016 (UTC)

How unnecessarily complicate are OO languages.

It is very easy to write a fold for list in C provided that you defined a list abstract data type.

B foldAB(B (*f)(A x, B y), B e, AList xs)
{ return (isCons(xs)) ? f(car(xs),foldAB(f,e,cdr(xs)) : e ; }

I admit that is not polymorphic, I know that any C++ programmer can rewrite it as a template or something like that, (I don't use OO languages). Anyway just compare with the C++ code in the link. — Preceding unsigned comment added by 2806:107E:C:B556:218:DEFF:FE2B:1215 (talk) 08:23, 15 August 2018 (UTC)

Java

Neither stream.reduce(func) nor stream.reduce(init, func) are real folds:

• They only work if the result-type is the same as the value-type. So it is more akin to Haskells foldl1
• It is not guaranteed that the order is preserved thus it only works if the binary operation is distributive. This becomes apparent when creating tree structures on parallel streams.

This beeing said, there is a way to get real foldl behavior. The stream interface also provides U reduce(U identity, BiFunction<U, ? super T, U> accumulator, BinaryOperator combiner) which is almost foldl if it weren't for the combiner. The combiner is only called if the stream is parallel though. So stream.sequential().reduce(init, func, (l, r) -> { throw new UnsupportedOperationException(); }). This works but you shouldn't do this ... ever.

Is this enough to remove the table entries for java? — Preceding unsigned comment added by P.dargel (talk • contribs) 14:11, 26 June 2017 (UTC)

Great, lots of errors! Wikipedia is not an unloyal competitor for commercial sources. Keep Wikipedia censored and being the laugh of everyone and a not trusted source

This article has no reason to exist, a fold function is just a higher order function on inductive data types. which replace each constructor by a given parameter. For lists, foldr f e, replace each cons (:) by f and each nil ([]) by e. That's all. That function is very old in LISP, although is called reduce.

The tree-like folds section is totally obscure and non-sense. Those are incomplete functions to transform a list into a tree,

I suppose that the intention of such part is to build a tree like this example:

data BT a = BF (BT a) (BT a) | BN a deriving (Eq,Show,Ord)

Main> foldi BF (BN 0) (map BN [1..5])
BF (BN 1) (BF (BF (BN 2) (BN 3)) (BF (BF (BN 4) (BN 5)) (BN 0)))

This is a wrong example, a similar method can be used to build balanced trees, but that is not part of the subject.

Good Luck enthusiast authors, keep writing articles about subjects that you have not yet understood! Keep everybody confused!

I could erase everything to fix this article, however, why should I make that effort, if a bot will revert my changes automatically?

If you want to do it! As I said before the fold functions map constructors of inductive types to other functions. A fold can be seen as a generalization of recursive functions, as such many recursive functions like map, filter, length, etc., can be written in terms of fold.

Ah! You can fold any inductive type, like naturals and trees, can you guess how? I leave it as homework, good luck for the brave volunteer who want to fix this article, I hope that the bot doesn't revert the change!

When this attitude changes, I will help! Bye!

What's the difference between this and Reduction Operator

If nothing else, the articles should refer to each other with explanations to prevent confusion. Notrium (talk) 18:34, 15 June 2020 (UTC)

The language example table should probably be fully deleted

Most of the examples of foldr in the table are not a right fold. They are simply reversing the array and applying a left fold. There is not enough space in the table to make an actual foldr implementation for all of the languages. Starnche (talk) 01:15, 26 May 2024 (UTC)